Campus Event Calendar
Event Entry
What and Who
Partial Colorings of Unimodular Hypergraphs
Benjamin Doerr
Max-Planck-Institut für Informatik - D 1
AG1 Mittagsseminar (own work)
Born, raised and educated with moderate success in Munich, Kiel and Saarbruecken.
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, 21 November 2006
13:30
30 Minutes
E1 4
024
Saarbrücken
Abstract
A \emph{hypergraph} $\HH = (V, \EE)$ consists of a (here) finite set $V$ of vertices and a set $\EE \subseteq 2^V$ of (hyper-)edges.
It is called \emph{unimodular} if each induced subhypergraph has an almost balanced coloring, that is, if for each $V_0 \subseteq V$ there is a two-coloring $\chi : V_0 \to \{1,2\}$ such that for all $E \in \EE$, $\big| |E \cap V_0 \cap \chi^{-1}(1)| - |E \cap V_0 \cap \chi^{-1}(2)|\big| \le 1$.
In simple words: These hypergraph can be colored as balanced as possible taking into account that an odd cardinality hyperedge cannot be colored perfectly balanced.
An interesting question is whether we can avoid such imbalances (caused by the 'odd' vertex) by not coloring all the vertices. This is known a partial coloring and is, in fact, the heart of Beck's partial coloring method.
In contrast to the above sketched nice behaviour of unimodular hypergraph, this is not possible for all unimodular hypergraphs. A non-trivial counter-example is the hypergraph of all intervals of length $3$ and $5$ in $[n]:= \{1, \ldots, n\}$, $n \in \N$ sufficiently large. On the other hand, $k$--uniform unimodular hypergraphs (all hyperedges contain exactly $k$ vertices) do have this property if $k \ge 2$.
In this talk, I give more details on this problem, present a simple, though strange, characterization of when partial coloring is possible, and claim (without proof) that this result is a key argument in my STACS submission.
It is called \emph{unimodular} if each induced subhypergraph has an almost balanced coloring, that is, if for each $V_0 \subseteq V$ there is a two-coloring $\chi : V_0 \to \{1,2\}$ such that for all $E \in \EE$, $\big| |E \cap V_0 \cap \chi^{-1}(1)| - |E \cap V_0 \cap \chi^{-1}(2)|\big| \le 1$.
In simple words: These hypergraph can be colored as balanced as possible taking into account that an odd cardinality hyperedge cannot be colored perfectly balanced.
An interesting question is whether we can avoid such imbalances (caused by the 'odd' vertex) by not coloring all the vertices. This is known a partial coloring and is, in fact, the heart of Beck's partial coloring method.
In contrast to the above sketched nice behaviour of unimodular hypergraph, this is not possible for all unimodular hypergraphs. A non-trivial counter-example is the hypergraph of all intervals of length $3$ and $5$ in $[n]:= \{1, \ldots, n\}$, $n \in \N$ sufficiently large. On the other hand, $k$--uniform unimodular hypergraphs (all hyperedges contain exactly $k$ vertices) do have this property if $k \ge 2$.
In this talk, I give more details on this problem, present a simple, though strange, characterization of when partial coloring is possible, and claim (without proof) that this result is a key argument in my STACS submission.
Contact
Benjamin Doerr
--email hidden
passcode not visible
logged in users only
Benjamin Doerr, 10/23/2006 18:30
Benjamin Doerr, 10/05/2006 10:41
Benjamin Doerr, 10/03/2006 19:08
Benjamin Doerr, 10/03/2006 19:05 -- Created document.
Benjamin Doerr, 10/05/2006 10:41
Benjamin Doerr, 10/03/2006 19:08
Benjamin Doerr, 10/03/2006 19:05 -- Created document.