Notes of Jacob Fox’s lecture

Chromatic number, clique subdivisions and the conjectures of Hajós and Erdös-Fajtlowicz

Joint with Choongbum Lee and Benny Sudakow.

1. Hajós conjecture

Let {\chi(G)} be the chromatic number of a graph and {\omega(G)} the clique number.

Basic conjecture: {\chi(G)\geq\omega(G)}.

Converse is false (see 5-cycle) but a variant may hold.

Hajós conjecture, 1961: If a graph contains no subdivision of {K_{t+1}}, then it is {t}-colorable.

It is a strengthening of Hadwiger’s conjecture an the 4-color theorem.

Disproved by Catlin in 1979 for {t\geq 6}. Erdös-Fajtlowicz realized that almost all graphs are strong counter-examples. Let {\sigma(G)=} maximum {t} for which {G} contains a subdivision of {K_t}.

Theorem 1 (Erdös-Fajtlowicz 1981) The random graph {G(n,\frac{1}{2})} almost surely satisfies

\displaystyle  \begin{array}{rcl}  \chi(G)=\Theta(\frac{n}{\log n}),\quad \sigma(G)=\Theta(\sqrt{n}). \end{array}

We wonder how bad the conjecture can fail.

Definition 2 {H(n)=} maximum of {\chi(G)/\sigma(G)} over all {n}-vertex graphs.

Erdös-Fajtlowicz showed that

\displaystyle  \begin{array}{rcl}  H(n)>c\,\frac{n^{1/2}}{\log n}, \end{array}

and conjectured that this is the maximum possible. This is what we prove.

Theorem 3 (Fox-Lee-Sudakov)

\displaystyle  \begin{array}{rcl}  H(n)=\Theta(\frac{n^{1/2}}{\log n}). \end{array}

1.1. Independence number and clique subdivision

The following are used in the proof.

Definition 4 {f(n,\alpha)=} minimum of {\sigma(G)} over all {n}-vertex graphs with independence number {\alpha}.

Theorem 5 (Fox-Lee-Sudakov)

\displaystyle  \begin{array}{rcl}  f(n,\alpha)&\geq&\Omega(n^{\frac{\alpha}{2\alpha-1}})\quad \textrm{ if }\alpha < 2\log n.\\ f(n,\alpha)&\geq&\Omega(\sqrt{\frac{n}{a\log a}})\quad \textrm{if }\alpha =a\log n,~a\geq 2. \end{array}

This is tight for {\alpha=2}. Examples achieving

\displaystyle  \begin{array}{rcl}  f(n,2)=\Theta(n^{2/3}) \end{array}

are due to Alon (pseudo-random triangle free graphs).

1.2. Tools

In the dense case, we rely on

Theorem 6 (Bollobás-Thomason, Komlós-Szemerédi) Let {e(G)} denote the number of edges in {G}. Then

\displaystyle e(G)\geq 256 t^2 n \Rightarrow \sigma(G)\geq t.

In the sparse case, in the complement of a maximum independant set, there is a large subset all of whose independent sets are pretty small.

1.3. Conjectures

For fixed {\alpha}, is it true that

\displaystyle  \begin{array}{rcl}  f(n,\alpha)=\Theta(n^{\frac{\alpha}{2\alpha-1}}) ~? \end{array}

We know it only for {\alpha=2}.

If {\chi(G)=k}, is it true that

\displaystyle  \begin{array}{rcl}  \sigma(G)\geq c\sqrt{k\log k}~? \end{array}

It is a matter of gaining a log factor on Bollobás-Thomason, Komlós-Szemerédi.

1.4. Questions from the audience

Is there a simpler proof without the log factor ? Answer: yes, using Bollobás-Thomason, Komlós-Szemerédi.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

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