Overview
This research addresses Kohayakawa's conjecture from 1991 concerning the maximum number of $s$-subsets on an induced path in a specific bipartite graph. The study provides a lower bound for this maximum number, $w(s)$, which subsequently confirms the conjecture. Additionally, these findings are applied to determine the clique covering numbers of complements of paths and cycles, settling a conjecture proposed by de Caen, Gregory, and Pullman in 1985.
Research Context
The work centers on $G_s$, a bipartite graph constructed for $s \ge 1$. In $G_s$, the bipartition consists of $s$-subsets and $(s-1)$-subsets of the set $[2s]$. Adjacency between these subsets is defined by disjointness. A key quantity under investigation is $w(s)$, which represents the maximum number of $s$-subsets that can exist on an induced path within $G_s$. Kohayakawa's conjecture (1991) posited a specific asymptotic behavior for $w(s)$, specifically $\sup_{s \ge 1}w(s)^{1/s}=4$. The clique covering number, denoted $\cc(H)$ for a graph $H$, is another central concept. Prior work by de Caen, Gregory, and Pullman in 1985 involved a conjecture regarding the clique covering numbers of complements of paths ($\overline{P_n}$) and complements of cycles ($\overline{C_n}$).
Approach
The research establishes a lower bound for $w(s)$. The proof for this lower bound applies for $s \ge 6$. The resolution of Kohayakawa's conjecture then relies on this established lower bound for $w(s)$ and its implication for the supremum of $w(s)^{1/s}$.
To address the conjecture by de Caen, Gregory, and Pullman, the authors leverage Kohayakawa's recursive construction. This construction uses the properties of $G_s$ to derive induced paths of a specific order in Kneser graphs. Specifically, induced paths of order $\Omega(4^r/r^{5/2})$ are generated in the Kneser graph $KG(2r+1,r)$.
The findings from the Kneser graph paths are then used to derive upper bounds for the clique covering numbers:
$\max\{\cc(\overline{P_n}),\ \cc(\overline{C_n})\} \le \log_2 n+\frac52\log_2\log_2 n+O(1)$
These upper bounds are combined with existing lower bounds to specify the exact asymptotic behavior of $\cc(\overline{P_n})$ and $\cc(\overline{C_n})$.
An independent proof is also provided for the order estimates of $\cc(\overline{P_n})$ and $\cc(\overline{C_n})$. This alternative proof incorporates a Hamiltonicity result pertaining to Kneser graphs and utilizes a key lemma. The key lemma itself was proved using the Lovász local lemma.
Findings
- For all $s \ge 6$, the maximum number of $s$-subsets on an induced path in $G_s$, denoted $w(s)$, satisfies the inequality $w(s) \ge \frac{4^s}{2048s^{5/2}}$.
- This lower bound for $w(s)$ implies that $\sup_{s \ge 1}w(s)^{1/s}=4$, thereby settling Kohayakawa's conjecture (1991).
- Kohayakawa's recursive construction, combined with the established result for $w(s)$, yields induced paths of order $\Omega(4^r/r^{5/2})$ in the Kneser graph $KG(2r+1,r)$.
- The maximum of the clique covering numbers for complements of paths and cycles is bounded as $\max\{\cc(\overline{P_n}),\ \cc(\overline{C_n})\} \le \log_2 n+\frac52\log_2\log_2 n+O(1)$.
- Together with known lower bounds, these results settle a conjecture by de Caen, Gregory, and Pullman (1985).
- The clique covering numbers are determined to be $\cc(\overline{P_n})=\log_2 n+\Theta(\log_2\log_2 n)$ and $\cc(\overline{C_n})=\log_2 n+\Theta(\log_2\log_2 n)$.
- An independent proof also establishes these order estimates for $\cc(\overline{P_n})$ and $\cc(\overline{C_n})$, utilizing a Hamiltonicity result of Kneser graphs and a lemma proved via the Lovász local lemma.