Can you prove that hypergraphs with n-1 edges are partially 2 colorable? - MathOverflow

Can you prove that hypergraphs with n-1 edges are partially 2 colorable?

2011-07-27T11:32:18Z

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.

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?

The motivation is this 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.

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.

Answer by Andrew D. King for Can you prove that hypergraphs with n-1 edges are partially 2 colorable?

2011-07-27T13:55:17Z

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.

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''$.

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.

If $G'$ is not connected we do the same thing with each connected component.

Answer by Ilya Bogdanov for Can you prove that hypergraphs with n-1 edges are partially 2 colorable?

2011-11-09T16:19:16Z

Here is a different approach, also using a theorem; I do not know if it is elementary in your view.

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<0$ in blue; you are done.

Right now I do not understand how to extend this argument for $k$-coloring...

Answer by Oliver Kullmann for Can you prove that hypergraphs with n-1 edges are partially 2 colorable?

2012-03-12T01:34:21Z

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

Paul D. Seymour, On the two-colouring of hypergraphs, The Quarterly Journal of Mathematics (Oxford University Press), 1974, Volume 25, Pages 303-312.

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 http://www.cs.swan.ac.uk/~csoliver/papers.html#Handbook2009MUAUT (see Subsections 11.4.5 and 11.12 for connections to the problem at hand). An article extending Seymour's result is http://cs.swan.ac.uk/~csoliver/papers.html#SNSSAT2007