Campus Event Calendar
Event Entry
What and Who
DiscMathMeeting: Battlezone (Mahmoud Fouz: ``Linear and Hereditary Discrepancies'')
Mahmoud Fouz
Max-Planck-Institut für Informatik - D 1
Meeting
Got a bachelor degree from us.
AG 1, AG 2, AG 3, AG 4, AG 5, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 24 October 2006
14:30
-- Not specified --
E1 4
3rd floor rotunda
Saarbrücken
Abstract
Another DiscMathMeeting Battlezone. Here's the abstract of the talk, but recall that the talk is only half the event.
The discrepancy of a hypergraph measures how balanced it can be colored in two colors. The generalization to arbitrary numbers of colors has lead to surprising results. Although a couple of classical results could be generalized to the multi-color case, it turned out that there is no general relationship between the discrepancies of a hypergraph in different numbers of colors.
This dichotomy could be solved by considering a stronger notion of discrepancies - the hereditary discrepancy.
In this talk, I will give a quick introduction into discrepancies of hypergraphs and show (just main proof idea) that the hereditary discrepancies for a hypergraph in different numbers of colors differ only by factors depending linearly on the respective numbers of colors, i.e., for any hypergraph $\mathcal{H}$ and arbitrary numbers $a,b \in \mathbb{N}_{\geq 2}$ of colors, we have
\begin{equation*}
\text{herdisc}(\mathcal{H},b)\leq O(a)\text{herdisc}(\mathcal{H},a).
\end{equation*}
The discrepancy of a hypergraph measures how balanced it can be colored in two colors. The generalization to arbitrary numbers of colors has lead to surprising results. Although a couple of classical results could be generalized to the multi-color case, it turned out that there is no general relationship between the discrepancies of a hypergraph in different numbers of colors.
This dichotomy could be solved by considering a stronger notion of discrepancies - the hereditary discrepancy.
In this talk, I will give a quick introduction into discrepancies of hypergraphs and show (just main proof idea) that the hereditary discrepancies for a hypergraph in different numbers of colors differ only by factors depending linearly on the respective numbers of colors, i.e., for any hypergraph $\mathcal{H}$ and arbitrary numbers $a,b \in \mathbb{N}_{\geq 2}$ of colors, we have
\begin{equation*}
\text{herdisc}(\mathcal{H},b)\leq O(a)\text{herdisc}(\mathcal{H},a).
\end{equation*}
Contact
Benjamin Doerr
--email hidden
passcode not visible
logged in users only
Benjamin Doerr, 10/16/2006 22:52 -- Created document.