Can you prove that hypergraphs with n-1 edges are partially 2 colorable? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T23:09:32Z http://mathoverflow.net/feeds/question/71393 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/71393/can-you-prove-that-hypergraphs-with-n-1-edges-are-partially-2-colorable Can you prove that hypergraphs with n-1 edges are partially 2 colorable? domotorp 2011-07-27T11:32:18Z 2012-03-12T01:34:21Z <p>I can. But my proof uses a theorem (which I do not reveal yet to avoid influencing you) and it feels like an overkill, so I wonder if there is a simple proof. Now the problem.</p> <p>Suppose we have a hypergraph on n vertices with n-1 edges. Can we color some (at least one) of its vertices with red and blue such that every hyperedge either contains both colors, or all of its vertices are uncolored?</p> <p>The motivation is <a href="http://lemon.cs.elte.hu/egres/open/Problem_of_the_month_May_2011" rel="nofollow">this</a> question. In fact, one can similarly define partial k-polychromatic coloring, where every hypergraph with less than n/(k-1) edges seems to be partially k-colorable, if my proof is correct. Note also that these bounds are tight as shown by disjoint edges of size k-1. And this cannot be improved by requiring some lower bound on the size of each hyperedge, as we observed yesterday with my usual set of friends, Cory, Dani, Keszegh, Nathan and Patkos.</p> <p>Please do not post links to Beck-Fiala and other well-known, similar theorems! At the moment I am only interested in a short, elementary proof of my question.</p> http://mathoverflow.net/questions/71393/can-you-prove-that-hypergraphs-with-n-1-edges-are-partially-2-colorable/71401#71401 Answer by Andrew D. King for Can you prove that hypergraphs with n-1 edges are partially 2 colorable? Andrew D. King 2011-07-27T13:55:17Z 2011-07-27T13:55:17Z <p>Let $E_1,\ldots, E_j$ be the sets of edges spanning vertex sets $S_1,\ldots,S_j$ such that for each $i$ in $[j]$, $|S_j|\leq |E_j|$. Let $S'$ and $E'$ be their respective unions. We will leave $S'$ uncoloured.</p> <p>Let $G'$ be the subhypergraph of $G$ reached by deleting $S'$ (here if an edge of $G$ partially intersects $G$, it may still exist in $G'$). Observe that in $G'$, there is no set of $k$ edges spanning at most $k$ vertices for any $k$. For now assume that $G'$ is connected. Take some vertex $v$ of $G'$ and delete it to reach $G''$. By Hall's theorem, we can now find an injection from the vertices of $G''$ to the (nonempty) edges of $G''$.</p> <p>We can now find a spanning tree ordering of the edges of $G'$ with the root being some vertex of $G''$ that is in an edge with $v$. Give $v$ colour $1$. We traverse the tree in, say, DFS ordering, and when we come to an edge $e$, we choose for its matched vertex $v_e$ a colour that will make $e$ dichromatic.</p> <p>If $G'$ is not connected we do the same thing with each connected component.</p> http://mathoverflow.net/questions/71393/can-you-prove-that-hypergraphs-with-n-1-edges-are-partially-2-colorable/80495#80495 Answer by Ilya Bogdanov for Can you prove that hypergraphs with n-1 edges are partially 2 colorable? Ilya Bogdanov 2011-11-09T16:19:16Z 2011-11-09T16:19:16Z <p>Here is a different approach, also using a theorem; I do not know if it is elementary in your view.</p> <p>Let $A$ be a set of $n$ vertices, and let $B_1,\dots,B_{n-1}$ be its subsets. Introduce $n$ variables $x_a$ ($a\in A$) and consider a system of $n-1$ linear equations of the form $\sum_{a\in B_i} x_a=0$. It has a nonzero solution $(x^0_a)_{a\in A}$. Now paint all the vertices $a:x_a^0>0$ in red, and $a:x_a^0&lt;0$ in blue; you are done.</p> <p>Right now I do not understand how to extend this argument for $k$-coloring...</p> http://mathoverflow.net/questions/71393/can-you-prove-that-hypergraphs-with-n-1-edges-are-partially-2-colorable/90956#90956 Answer by Oliver Kullmann for Can you prove that hypergraphs with n-1 edges are partially 2 colorable? Oliver Kullmann 2012-03-12T01:34:21Z 2012-03-12T01:34:21Z <p>The proof of the statement of the question is implicitly contained, along the lines of the proof by Ilya Bogdanov, in Paul Seymour's MSc thesis, where the relevant part is published in</p> <blockquote> <p>Paul D. Seymour, On the two-colouring of hypergraphs, The Quarterly Journal of Mathematics (Oxford University Press), 1974, Volume 25, Pages 303-312.</p> </blockquote> <p>If the hypergraph 2-colouring problem is translated (in the canonical way) into a satisfiability problem (SAT problem), then the statement is precisely that there exists a so-called "autarky". The theory of autarkies is outlined in my Handbook of Satisfiability article on autarkies, available at <a href="http://www.cs.swan.ac.uk/~csoliver/papers.html#Handbook2009MUAUT" rel="nofollow">http://www.cs.swan.ac.uk/~csoliver/papers.html#Handbook2009MUAUT</a> (see Subsections 11.4.5 and 11.12 for connections to the problem at hand). An article extending Seymour's result is <a href="http://cs.swan.ac.uk/~csoliver/papers.html#SNSSAT2007" rel="nofollow">http://cs.swan.ac.uk/~csoliver/papers.html#SNSSAT2007</a></p>