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 consists of the same vertices as but a subset of the edges of . The number of edges containing a given vertex is its degree, and the maximum degree in a hypergraph is denoted . The chromatic index of is the fewest number of colours needed to colour the edges of so that edges with the same colour are disjoint. A hypergraph is normal if for every partial hypergraph of . A graph is perfect if the chromatic number of any induced subgraph of is the same as the clique number of .

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

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

**Theorem 2.** is normal iff is perfect; …

It seems clear that when is normal then is perfect. However, the reverse implication is less clear. Consider . For or 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 having the Helly property as guaranteed by 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 to obtain normal , 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 be a hypergraph with the Helly property. is normal iff 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 nor 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)

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 |

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

Pingback by Hypergraph decompositions used in TCS? | Question and Answer — 9 November 2013 @ 6:24 |