The clique-density conjecture for complements of string graphs

From papers

Let s1s\ge 1, let ε>0\varepsilon>0, and let GG be the complement of a string graph. Here ϱ4s+1(G)\varrho_{4s+1}(G) denotes the density of copies of K4s+1K_{4s+1} in GG, and Ks+1[t]K_{s+1}[t] denotes the complete (s+1)(s+1)-partite graph with parts of size tt. The string-graph clique-density conjecture. If

ϱ4s+1(G)>0,\varrho_{4s+1}(G)>0,

then GG contains a copy of Ks+1[δn]K_{s+1}[\delta n], where δ=δ(ε)>0\delta=\delta(\varepsilon)>0. This proposes replacing the positive edge-density hypothesis in the known string-graph result by positive clique density; the conjecture remains open.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.