30 May 2009

Three results

Filed under: Commentary — András Salamon @ 16:36

Three fascinating results that appear to have no connection other than being rather surprising.

First, the chromatic number of the plane. The number of colours required for colouring the real plane, where no two points unit distance apart may be the same colour, is known to be either 4, 5, 6, or 7. Shelah and Soifer noted in 2003 that the actual value relates to the proposed axiom LM of set theory that requires that every set of reals is Lebesgue measurable. Specifically, the chromatic number of the plane is 4 with the usual ZF axioms of set theory, augmented with the Axiom of Choice. This was shown by Erdős and de Bruijn in 1951. However, the chromatic number of the plane is at least 5 in ZF together with LM and a weaker version of AOC, the Principle of Dependent Choices that Bernays proposed in 1942. So the Axiom of Choice does impact the real world, after all, at least for some definition of “real world”!

The second result is a problem that only requires a poly-logarithmic number of nondeterministic steps for a polynomial-time solution, and which has a deterministic runtime upper bound that is almost, but not quite, polynomial. A hitting set X of a hypergraph H (also known as a transversal of H) intersects each edge of H. A minimal transversal contains no strict subset that is a transversal. The hypergraph of all minimal transversals of a hypergraph H is its transversal hypergraph. TRANS-HYP is the problem of deciding, given two hypergraphs H and H’, whether H’ is the transversal hypergraph of H. TRANS-HYP is in co-NP but not obviously in NP. Fredman and Khachiyan showed that it is possible to recognize the transversal hypergraph of a given H in time O(n^{\log n}), where n is the size of the input. (This result was actually expressed in terms of recognition of duals of monotone Boolean functions.) The surprising result is that it is possible to show that a given hypergraph is not a transversal hypergraph of another in polynomial time using only O(\log^2 n/\log \log n) nondeterministic steps. This was shown by Eiter, Gottlob, Makino and independently by Kavvadias and Stavropoulos, in 2002-3. If one is allowed a polynomial number of nondeterministic steps then of course one can capture NP, while a logarithmic number of nondeterministic steps captures P. This important problem therefore occupies a surprising place in the bounded nondeterminism hierarchy (which was last surveyed by Goldsmith, Levy, Mundhenk in 1997). A succinct overview of the state of the art is the paper by Eiter, Makino, Gottlob published in 2008.

Finally, an upcoming paper. Michael Mitzenmacher has briefly discussed the STOC 2009 programme; following on, I would recommend the recent paper by Moser and Tardos; it presents a beautiful and short algorithmic proof of the Lovász Local Lemma in a very general form, and appears to supersede the (excellent) paper of Moser at STOC. But back to the paper I actually wanted to highlight: in among the STOC 2009 abstracts there was the intriguing comment in the abstract of a paper by Kawarabayashi and Reed discussing their algorithm deciding the Hadwiger Conjecture. For the special case k=5 this algorithm apparently implies the Four-Colour Theorem. Since the abstract seems to indicate that the detailed case analysis of the previous constructive proofs is largely avoided, I await the full paper with great anticipation. (Edit: the full paper has corrected the sentence. The result seems to be an important step forward in proving the Hadwiger Conjecture, but it doesn’t supply a short proof for the 4CT, alas.)


1 Comment »

  1. […] Algorithms for Constraint Satisfaction Problems, to be presented at CSR 2010 in June, suggests that Moser’s algorithm presented at STOC 2009 might be worth looking at it in more detail, as another possible […]

    Pingback by Immediate SAT restarts? « Constraints — 23 March 2010 @ 20:28 | Reply

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at

%d bloggers like this: