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

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\mathrm{/}2}}$ for all $s\ge 6$. This implies ${\sup }_{s\ge 1}w(s{)}^{1\mathrm{/}s}=4$, as conjectured by Kohayakawa (1991). His recursive construction then gives induced paths of order $\mathrm{\Omega }(4^r\mathrm{/}{r}^{5\mathrm{/}2})$ in the Kneser graph $KG(2r+1,r)$ and yields $$\max \{\text{cc}(\overline{P_n}),\text{cc}(\overline{C_n})\}\le {\log }_{2}n+\frac{5}{2}{\log }_2{\log }_{2}n+O(1)\mathrm{.}$$ Together with the known lower bounds, this settles a conjecture of de Caen, Gregory, and Pullman (1985) and gives $$\text{cc}(\overline{P_n})={\log }_{2}n+\mathrm{\Theta }({\log }_2{\log }_{2}n),\text{cc}(\overline{C_n})={\log }_{2}n+\mathrm{\Theta }({\log }_2{\log }_{2}n)\mathrm{.}$$ 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.