Kohayakawa's conjecture and clique coverings of complements of paths and cycles

Abstract

For $s\ge 1$, let $G_s$ be the bipartite graph between the $s$-subsets and the $(s-1)$-subsets of $[2s]$, where adjacency means disjointness, and let $w(s)$ be the maximum number of $s$-subsets on an induced path in $G_s$. We prove $w(s)\ge \frac{4^s}{2048s^{5/2}}$ for all $s\ge 6$. This implies ${\sup }_{s\ge 1}w(s{)}^{1/s}=4$, as conjectured by Kohayakawa (1991). His recursive construction then gives induced paths of order $\Omega (4^r/r^{5/2})$ in the Kneser graph $KG(2r+1,r)$ and yields \[ \max\{\cc(\overline{P_n}),\ \cc(\overline{C_n})\} \le \log_2 n+\frac52\log_2\log_2 n+O(1). \] Together with the known lower bounds, this settles a conjecture of de Caen, Gregory, and Pullman (1985) and gives \[ \cc(\overline{P_n})=\log_2 n+Θ(\log_2\log_2 n), \qquad \cc(\overline{C_n})=\log_2 n+Θ(\log_2\log_2 n). \] We also give an independent proof of the latter order estimates. It uses a Hamiltonicity result of Kneser graphs and a key lemma proved by the Lovász local lemma.

15 pages