François G. Dorais

Topics
• Combinatorics
• Set Theory

Uncountable perfect graphs

I have been fascinated with perfect graphs for many years. These graphs are very intensely studied in finite combinatorics and new wonderful properties of finite perfect graphs are discovered on a regular basis. However, it is still unclear whether or how these wonderful properties might extend to the countable and uncountable cases. There are several deep questions about this. One of the most interesting question is the consistency of Galvin’s Conjecture. I recently wrote a paper on this question (Dorais 2013). Since I believe this and related questions deserve more attention, here is a brief survey of known results around Galvin’s Conjecture.

Perfection has to do with some cardinal characteristics of graphs. Throughout the following, $G$ will denote a graph with vertex set $V$. If $X \subseteq V$, then $G_X$ will denote the induced subgraph of $G$ with vertex set $X$. The four cardinal characteristics of a graph $G$ that we need are:

• The clique number is $\omega(G) = \sup \set{\card{X}:\text{\(X\) is a clique of \(G\)}}.$
• The stability number is $\alpha(G) = \sup\set{\card{X}:\text{\(X\) is an anticlique of \(G\)}}.$
• The chromatic number $\chi(G)$ is the smallest size of a cover of $V$ by anticliques.
• The clique-cover number $\theta(G)$ is the smallest size of a cover of $V$ by cliques.

We have the following obvious inequalities between these cardinals

When does equality hold?

It’s not hard to see that in the case of an odd cycle $C_{2n+1}$ with $n \geq 2$, we have

and

By duality, we also have strict inequalities for the complement $\overline{C}_{2n+1}$ of an odd cycle for $n \geq 2$. In the 1960’s, Claude Berge conjectured that odd cycles and their complements were the minimal finite graphs for which the equalities $\omega = \chi$ and $\alpha = \theta$ fails. This conjecture became known as the Strong Perfect Graph Conjecture, which remained open for a long time until Chudnovsky, Robertson, Seymour and Thomas (2006) finally proved the conjecture in 2002. Since then, Berge’s conjecture has become:

Strong Perfect Graph Theorem (Lovász 1972; Lovász 1972; Chudnovsky–Robertson–Seymour–Thomas 2006). The following are equivalent for every graph $G$:

1. $G$ contains no induced copies of the odd cycle $C_{2n+1}$ nor its complement $\overline{C}_{2n+1}$ for $n \geq 2$.
2. $\omega(G_X) = \chi(G_X)$ for every finite $X \subseteq V$.
3. $\alpha(G_X) = \theta(G_X)$ for every finite $X \subseteq V$.
4. $\alpha(G_X)\omega(G_X) \geq \card{X}$ for every finite $X \subseteq V$.

A graph $G$ with these properties is called a perfect graph. Several classes of graphs are known to be perfect:

• Bipartite graphs are perfect.
• Line graphs of bipartite graphs are perfect.
• Comparability graphs are perfect.
• Interval graphs are perfect.
• Chordal graphs are perfect.

All of these families make sense for infinite graphs. It is natural to ask whether the equalities $\omega = \chi$ and $\alpha = \theta$ continue to hold in the uncountable case.

Both equalities are trivial for infinite bipartite graphs. The fact that $\alpha = \theta$ for line graphs of bipartite graphs are perfect is known as König’s Duality Theorem; it is a deep result of Aharoni (1984) that this result continues to hold in the uncountable case. Unfortunately, the equalities $\omega = \chi$ and $\alpha = \theta$ can fail very badly for uncountable perfect graphs. For example, Perles (1963) observed that if $\kappa$ is an infinite cardinal then the comparability graph of the product ordering $\kappa\times\kappa$ has no infinite anticliques but cannot be covered by fewer than $\kappa$ cliques.

There is an alternative way to think of the equalities $\omega = \chi$ and $\alpha = \theta$ which is much more promising in the uncountable case.

Theorem. Suppose $G$ is a perfect graph and $k$ is a positive integer.

1. $\chi(G) \leq k$ if and only if $\chi(G_X) \leq k$ for every $X \in [V]^{k+1}$.
2. $\theta(G) \leq k$ if and only if $\theta(G_X) \leq k$ for every $X \in [V]^{k+1}$.

Proof. The two statements are dual, so I will only prove the first. The forward implication is trivial. For the backward implication, note that the fact that $\chi(G_X) \leq k$ for every $X \in [V]^{k+1}$ means that $G$ has no clique of size $k+1$. Therefore, $\omega(G) \leq k$ and hence $\chi(G_X) \leq k$ for every finite $X \subseteq V$. By compactness, it follows that $\chi(G) \leq k$. QED

It is natural to ask whether this result continues to hold when $k$ is replaced by an infinite cardinal $\kappa$, and $k+1$ is replaced by its cardinal successor $\kappa^+$. Since compactness plays a key role in the above proof, this type of generalization is intimately tied with infinitary generalizations of compactness. It is therefore expected that large cardinals will play a role in determining whether such generalizations are plausible or not. (Todorcevic 2011) is an excellent survey of the type of compactness issues involved here.

The first case $\kappa = \aleph_0$, $\kappa^+ = \aleph_1$ is already interesting to look at. This leads us to a pair of conjectures:

• In 1968, Fred Galvin conjectured that if $G$ is a comparability graph then $\theta(G) \leq \aleph_0$ if and only if $\theta(G_X) \leq \aleph_0$ for every $X \in [V]^{\aleph_1}$.
• In 1981, Richard Rado conjectured that if $G$ is an interval graph then $\chi(G) \leq \aleph_0$ if and only if $\chi(G_X) \leq \aleph_0$ for every $X \in [V]^{\aleph_1}$.

Note that Galvin’s Conjecture implies Rado’s Conjecture since the complement of an interval graph is a comparability graph.

It turns out that both conjectures are consistently false. However, Rado’s Conjecture was shown to be consistent relative to a supercompact cardinal by Todorcevic (1983). Recently, I extended Todorcevic’s result to the class of all chordal graphs.

Theorem (Dorais 2013). It is consistent relative to the existence of a supercompact cardinal that

holds for every chordal graph $G$.

The dual statement for chordal graphs had already been proved by Stan Wagon.

Theorem (Wagon 1978). If $G$ is a chordal graph, then

In fact, Wagon showed that if $G$ is an uncountable chordal graph with $\alpha(G) \leq \aleph_0$ and $\theta(G) \geq \aleph_1$, then $G$ must contain the comparability graph of a Suslin tree. Since Suslin trees have size $\aleph_1$, the result follows immediately. However, note that if Suslin’s Hypothesis is true then the equality $\alpha = \theta$ continues to hold up to $\aleph_1$.

Towards Galvin’s conjecture, the best unconditional result is due to Uri Abraham.

Theorem (Abraham 1987). If $G$ is a comparability graph without infinite anticliques, then

To prove this, Abraham looked at Perles’s example $\omega_1 \times \omega_1$. He then generalized this example and showed that all graphs $G$ without infinite anticliques such that $\theta(G) \geq \aleph_1$ must contain an induced subgraph of Perles type. Since graphs of Perles type have size $\aleph_1$, the result follows immediately.

Another step towards Galvin’s conjecture is due to Stevo Todorcevic, who showed that Rado’s conjecture is equivalent to the restriction of Galvin’s conjecture to finite-dimensional comparability graphs.

Theorem (Todorcevic 2011). It is consistent relative to the existence of a supercompact cardinal that

holds for every finite-dimensional comparability graph $G$.

This follows from a remark without proof in (Todorcevic 2011). However, I had obtained an independent proof of this fact sometime ago, you can find my proof in (Dorais 2013).

It appears that not much is known about the dual of Galvin’s Conjecture.

Theorem (Dorais 2013). It is consistent relative to the existence of a supercompact cardinal that

holds for every two-dimensional comparability graph $G$.

In fact, I show that the dual of Galvin’s Conjecture restricted to two-dimensional comparability graphs is equivalent to Rado’s Conjecture. Since trees are two-dimensional, this includes an earlier result of Todorcevic (1983). The consistency of the dual of Galvin’s Conjecture restricted to three-dimensional comparability graphs appears to be open.

It follows from results of (Todorcevic 1983) that Rado’s Conjecture is the equivalent to the statement that a comparability graph $G$ can be covered by countably many sets $V_0,V_1,\dots$ such that each $G_{V_i}$ has no infinite clique if and only if this is true for every $G_X$ with $X \in [V]^{\aleph_1}$. Therefore, the dual of Abraham’s Theorem would suffice to establish the consistency of the dual of Galvin’s Conjecture.

References

1. U. Abraham, 1987: A note on Dilworth’s theorem in the infinite case, Order 4, no. 2, 107–125.

   • mr: 0916489

   • zbl: 0629.06002

   • doi: 10.1007/BF00337691

2. R. Aharoni, 1984: König’s duality theorem for infinite bipartite graphs, J. London Math. Soc. (2) 29, no. 1, 1–12.

   • mr: 0734985

   • zbl: 0505.05049

   • doi: 10.1112/jlms/s2-29.1.1

3. M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, 2006: The strong perfect graph theorem, Ann. of Math. (2) 164, no. 1, 51–229.

   • mr: 2233847

   • zbl: 1112.05042

   • doi: 10.4007/annals.2006.164.51

4. F. G. Dorais, 2013: A note on conjectures of F. Galvin and R. Rado, Canad. Math. Bull. 56, 317–325.

   • mr: 3043059

   • zbl: 1315.03077

   • arxiv: 1110.6563

   • doi: 10.4153/CMB-2011-192-8

5. L. Lovász, 1972: A characterization of perfect graphs, J. Combinatorial Theory Ser. B 13, 95–98.

   • mr: 0309780

   • zbl: 0241.05107

   • doi: 10.1016/0095-8956(72)90045-7

6. L. Lovász, 1972: Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2, no. 3, 253–267.

   • mr: 0302480

   • zbl: 0239.05111

   • doi: 10.1016/0012-365X(72)90006-4

7. M. A. Perles, 1963: On Dilworth’s theorem in the infinite case, Israel J. Math. 1, 108–109.

   • mr: 0168497

   • zbl: 0115.01703

   • doi: 10.1007/BF02759806

8. S. Todorcevic, 2011: Combinatorial dichotomies in set theory, Bull. Symbolic Logic 17, no. 1, 1–72.

   • mr: 2760116

   • zbl: 1230.03075

   • doi: 10.2178/bsl/1294186662

9. S. Todorcevic, 1983: On a conjecture of R. Rado, J. London Math. Soc. (2) 27, no. 1, 1–8.

   • mr: 0620672

   • zbl: 0463.06001

   • doi: 10.1016/0012-365X(81)90208-9

10. S. Wagon, 1978: Infinite triangulated graphs, Discrete Math. 22, no. 2, 183–189.

    • mr: 0523302

    • zbl: 0382.05047

    • doi: 10.1016/0012-365X(78)90123-1

Originally posted on November 6, 2011, by François G. Dorais. To the extent possible under law, François G. Dorais has waived all copyright and neigboring rights to this work.

Comments

• François G. Dorais wrote on November 17, 2011, at 02:48

  David Eppstein just wrote a post where he generalizes chordal graphs to the infinite case in a manner much different than I do. It is interesting to compare the two…

  ---