Equivalence of Small and Large Quasi-kernels

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.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-17
DOI
https://doi.org/10.48550/arxiv.2611.22881
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Equivalence of Small and Large Quasi-kernels

Sam Spiro
arXiv (Cornell University)
Advanced Graph Theory Research
preprint

Equivalence of Small and Large Quasi-kernels

Sam Spiro
preprint en

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.

arXiv (Cornell University)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon