← All problems

Erdős Problem #920 — Chromatic lower bounds for KkK_k-free graphs

57 years old · traced to

For integers k≥4k\geq 4 and n≥1n\geq 1, let fk(n)f_k(n) be the maximum chromatic number among finite simple graphs GG with exactly nn vertices that contain no clique of order kk (that is, no subgraph isomorphic to KkK_k): Erdős Problem #920

fk(n)=max⁡{χ(G):∣V(G)∣=n, Kk⊈G}.f_k(n)=\max\{\chi(G): |V(G)|=n,\ K_k\not\subseteq G\}.

Erdős Problem #920

The question is whether, for every fixed integer k≥4k\geq 4, there are constants ak,bk>0a_k,b_k>0 such that for all sufficiently large integers nn, Erdős Problem #920

fk(n)≥ak n1−1/(k−1)(log⁡n)bk.f_k(n)\geq a_k\,\frac{n^{1-1/(k-1)}}{(\log n)^{b_k}}.

Erdős Problem #920

Here aka_k and bkb_k may depend on kk; the exponent bkb_k is the constant denoted ckc_k in the original question. Erdős Problem #920

Background

This extremal function asks how large chromatic complexity can remain when a fixed clique is forbidden. The problem is attributed to Erdős [Er69b]. Graver and Yackel established the upper bound, for fixed k≥3k\geq 3, Erdős Problem #920 Graver and Yackel (1968)

fk(n)≪(nlog⁡log⁡nlog⁡n)1−1/(k−1).f_k(n)\ll \left(n\frac{\log\log n}{\log n}\right)^{1-1/(k-1)}.

Erdős Problem #920 Graver and Yackel (1968)

Thus the question seeks a lower bound close in its power of nn to this known upper bound, allowing a power of a logarithm. Erdős Problem #920 Graver and Yackel (1968)

Off-diagonal Ramsey bounds provide a route to lower bounds for fkf_k. In the case k=4k=4, a graph on nn vertices with no K4K_4 and independence number less than mm has chromatic number at least n/(m−1)n/(m-1). Mattheus and Verstraete's lower bound for R(4,m)R(4,m) supplies graphs of this kind at the scale needed for the bound stated below. Erdős Problem #920 Some recent results in Ramsey theory

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.