{"id":"arxiv/2608.11132","url":"https://arxiv.org/abs/2608.11132","tags":["math.CO"],"score":0,"title":"Kohayakawa's conjecture and clique coverings of complements of paths and cycles","domain":"math.CO","source":"arxiv","authors":["Bo Ning"],"reviews":0,"subject":"math.CO","summary":"For $s\\ge1$, 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\\geq 6$. This implies $\\sup_{s\\ge1}w(s)^{1/s}=4$, as conjectured by Kohayakawa (1991). His recursive construction then gives induced paths of order $Ω(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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-11","reactions":{}}