Xiao and Katona's clique-covering conjecture

Let tk1(n)t_{k-1}(n) denote the maximum number of edges in a Kk1K_{k-1}-free graph on nn vertices, and let τk(G)\tau_k(G) be the minimum size of a vertex set meeting every copy of KkK_k in GG. For a balanced partition V1Vk1V_1\cup\cdots\cup V_{k-1} of [n][n], assume V1Vk1|V_1|\geq\cdots\geq|V_{k-1}|. Xiao and Katona's conjecture. For fixed integers k4k\geq4 (and as stated in the source, s>t1s>t\geq1), every graph GG on nn vertices with tk1(n)+1t_{k-1}(n)+1 edges and τk(G)2\tau_k(G)\geq2 contains at least

(V1+V22)i=3k1Vi\left(|V_1|+|V_2|-2\right)\prod_{i=3}^{k-1}|V_i|

copies of KkK_k. The paper states that it gives a counterexample to one Xiao–Katona conjecture and proves a modified version, so this original conjecture is refuted.

Sources & referencesView supporting material

Primary source

Xizhi Liu and Dhruv Mubayi, “On a generalized Erdős-Rademacher problem”, arXiv:2005.07224 (2020).

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.