Constraints

4 April 2011

Beware normal hypergraph landmine

Filed under: Commentary — András Salamon @ 0:02
Tags:

In a classic 1972 paper László Lovász proved the (little) Perfect Graph Theorem, that the complement of every perfect graph is perfect. Another theorem from this paper links normal hypergraphs and perfect graphs. Perhaps this discussion will help someone avoid unnecessary grey hairs.

A partial hypergraph of a hypergraph H consists of the same vertices as H but a subset of the edges of H. The number of edges containing a given vertex is its degree, and the maximum degree in a hypergraph is denoted \Delta(H). The chromatic index \chi'(H) of H is the fewest number of colours needed to colour the edges of H so that edges with the same colour are disjoint. A hypergraph H is normal if \chi'(H') = \Delta(H') for every partial hypergraph H' of H. A graph G is perfect if the chromatic number of any induced subgraph G' of G is the same as the clique number of G'.

Given a hypergraph H, its edge graph G(H) has as vertices the edges of H, and two edges of H are adjacent in G(H) if they intersect.

This is what the paper says, both in the original 1972 version as well as the verbatim 2006 reprint:

Theorem 2. H is normal iff G(H) is perfect; …

It seems clear that when H is normal then G(H) is perfect. However, the reverse implication is less clear. Consider H = K_k. For k=3 or k=4 these hypergraphs (which happen to be graphs) are not normal, yet their edge graphs are perfect. The implication from normal to perfect seems to rely on H having the Helly property as guaranteed by H being normal, whereupon equation (8) from the paper can then be used. There seems to be no obvious way to invert the logic starting with perfect G(H) to obtain normal H, and the two apparent counterexamples also indicate something wrong.

Surely these counterexamples would have been dealt with in the reprinted version? This paper has been cited hundreds of times, this is not some obscure result.

However, the main result of the paper is Theorem 3, which has other well-known proofs, for instance see Diestel’s Graph Theory, 3rd edition. Perhaps Theorem 2 had been overlooked?

After wasting some more time, I found a scan of a reprint version of this paper from 1984 on the author’s webpage.  Since I was out of ideas, I checked it just in case. It turns out to have a different title and to have some small but material differences in the text. This is what Theorem 2 looks like in this version:

Theorem 2. Let H be a hypergraph with the Helly property. H is normal iff G(H) is perfect; …

Adding this condition to the theorem obviously makes it work in the other direction too, as well as dispensing with the counterexamples (neither K_3 nor K_4 have the Helly property).

I’m relieved to have found the correct statement of the theorem, and hope others can avoid being misled by this typo. Serves me right for relying on the provenance provided by a journal reprint…

For reference, the corrected version of this paper is L. Lovász, Normal Hypergraphs and the Weak Perfect Graph Conjecture, North-Holland Mathematics Studies 88 29–42, 1984.  (scan)

About these ads

2 Comments »

  1. I’ve been reading about similar things recently. You may be interested in the fact that “Hypergraphs” by C. Berge quotes the correct version of this theorem, as a corollary to a big list of equivalent statements about normal hypergraphs (Theorem 16, p.195 and Corollary 1, p.197). The book is quite well written.

    Comment by Evgenij — 22 June 2012 @ 0:28 | Reply

  2. […] Beware normal hypergraph landmine, Andras […]

    Pingback by Hypergraph decompositions used in TCS? | Question and Answer — 9 November 2013 @ 6:24 | 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:

WordPress.com Logo

You are commenting using your WordPress.com 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

The Rubric Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: