Paperlane

no. 17 · Wednesday 18 November 2026

Equivalence of Small and Large Quasi-kernels

Sam Spiro

math.CO · 11 pp

Abstract

A quasi-kernel of a digraph $D$ is an independent set which can reach every vertex of $D$ by a directed path of length at most 2. The Small Quasi-kernel Conjecture states that every $n$-vertex source-free digraph $D$ contains a quasi-kernel $Q$ with $|Q|\le n/2$, and the Large Quasi-kernel Conjecture states that every $n$-vertex digraph $D$ contains a quasi-kernel $Q$ with $|N^+[Q]|\ge n/2$. Our main result shows for any $\frac{1}{2}<β<1$ an equivalence between the following two statements: \[\textrm{Every }n\textrm{-vertex source-free digraph contains a quasi-kernel with } |Q|\le n-Ω(n^β).\] \[\textrm{Every }n\textrm{-vertex digraph contains a quasi-kernel with } |N^+[Q]|\ge Ω(n^{2-\frac{1}β}).\] That is, any sublinear bound for one problem is equivalent to a corresponding sublinear bound for the other. This combined with previous work establishing an equivalence for linear bounds shows that the two problems are largely equivalent to each other. We additionally give a slight refinement to the recent breakthrough of Rutschmann for these problems which, together with the result above, gives the best known bounds of $n-Ω(n^{3/4})$ and $Ω(n^{2/3})$ for the Small and Large Quasi-kernel Conjectures, respectively. Our proofs are due to ChatGPT's Astra 6; the writing is all our own.

comments
11 pages. The proofs are due to Astra 6, the writing is our own. Comments welcome!
fields
Combinatorics
pdf ↗ page arXiv:2611.22881 ↗