Kohayakawa's conjecture and clique coverings of complements of paths and cycles
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.11132
curl -X POST /api/v1/records/arxiv/2608.11132/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.11132/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'