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)
Advertisement
Like this:
Be the first to like this post.
Beware normal hypergraph landmine
Tags: papers
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)
Like this: