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.


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.

  • 1
    $\begingroup$ Good! I was a little worried that Hall's theorem was the theorem you wanted to avoid. $\endgroup$ – Andrew D. King Jul 27 '11 at 19:22
  • $\begingroup$ Nice argument, Andrew. $\endgroup$ – Louigi Addario-Berry Jul 28 '11 at 2:28
  • $\begingroup$ No, actually I used Borsuk-Ulam... Now I wonder if there is a connection between the two, as for both there is an incremental proof. $\endgroup$ – domotorp Jul 28 '11 at 6:28

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

  • $\begingroup$ It is great to hear about another connection, unfortunately I did not manage to digest autakries yet... $\endgroup$ – domotorp Mar 12 '12 at 15:15

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.