Tomon's incomparability-graph blowup conjecture

Let k3k\ge 3, let ε>0\varepsilon>0, and let GG be an nn-vertex incomparability graph. Here ϱ2(G)\varrho_2(G) denotes the edge density of GG, and Kk[t]K_k[t] denotes the complete kk-partite graph with kk parts of size tt. Tomon's conjecture. If

ϱ2(G)>11k1+ε,\varrho_2(G)>1-\frac{1}{k-1}+\varepsilon,

then GG contains a copy of

Kk[cn(logn)s],K_k\bigg[\frac{cn}{(\log n)^s}\bigg],

where c=c(ε,k)>0c=c(\varepsilon,k)>0 and s=log2ks=\lceil\log_2 k\rceil. This refines the known result with the weaker density threshold 119(k1)+ε1-\frac{1}{9(k-1)}+\varepsilon; whether the conjectured threshold guarantees the stated blowup remains open.

Sources & referencesView supporting material

Primary source

Domagoj Bradač, Hong Liu, Zhuo Wu and Zixiang Xu, “Clique density vs blowups”, arXiv:2410.07098 (2024).

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.