Feige–Pauzner conjecture for enabling graphs

The Feige–Pauzner conjecture asserts that the largest size guaranteed simultaneously for a clique and an independent set through every vertex is $\left\lfloor n/4\right\rfloor+1$. Feige and Pauzner formulated the conjecture after establishing near-sharp bounds.

Known results

• Feige and Pauzner showed $n(k,k)\ge 4k-O(k^{2/3})$.
• A 2025 preprint established the construction $k(n)\ge n/4+1$ when $n$ is divisible by $4$, an upper bound of $n/4+O(n^{2/3})$, and computational confirmation for $n\le 12$.

April 22, 2026 claimed proof

The preprint “Sharp bounds for covering with large cliques and independent sets” claims that, for $k_1,k_2\ge 2$, $n(k_1,k_2)\ge(\sqrt{k_1-1}+\sqrt{k_2-1})^2$, with equality when the right-hand side is an integer. It says the case $k_1=k_2=k$ immediately proves the conjecture; this claim remains unverified.

Current status (as of September 2026): A preprint claims the conjecture is proved, but the result is not independently verified; absent confirmation, the proof remains an unverified claim.