## 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.