WorksMathematics
Equivalence of Small and Large Quasi-kernels
Abstract
A quasi-kernel of a digraph is an independent set which can reach every vertex of by a directed path of length at most 2. The Small Quasi-kernel Conjecture states that every -vertex source-free digraph contains a quasi-kernel with , and the Large Quasi-kernel Conjecture states that every -vertex digraph contains a quasi-kernel with . Our main result shows for any an equivalence between the following two statements: 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 and for the Small and Large Quasi-kernel Conjectures, respectively. Our proofs are due to ChatGPT's Astra 6; the writing is all our own.
Introduction
This paper concerns problems about (finite) digraphs, for which we recall a few definitions. Given vertices , of a digraph , we define to be the length of a shortest directed path from to , and for a set of vertices we define . We say a set of vertices is independent if there exist no arcs between two vertices of . The main definition for this paper is the following.
Definition 1. A set of vertices of a digraph is said to be a quasi-kernel if (1) is an independent set and (2) for all (that is, every vertex can be reached from by a directed path of length at most 2).
It was shown by Chvátal and Lovász [3] that every digraph has a quasi-kernel. Because of this, it is natural to ask extremal problems about the set of quasi-kernels for a given digraph. One conjecture in this direction is the Small Quasi-kernel Conjecture due to P.L. Erdős and Székely from 1976 (though it only formally appeared later on [4]). Recall that a digraph is source-free if it contains no vertices with in-degree 0.
Conjecture 1.1 (Small Quasi-kernel Conjecture). Every -vertex source-free digraph contains a quasi-kernel with .
We recently posed a variant of this problem which asks for the existence of “large” quasi-kernels. For this we recall that for a digraph and a set we write
and we denote these sets simply by and whenever is clear from context.
Conjecture 1.2 (Large Quasi-kernel Conjecture). Every -vertex digraph contains a quasi-kernel with .
The Small and Large Quasi-kernel Conjectures are equivalent in a strong sense: for all , proving every -vertex source-free digraph has a quasi-kernel with is equivalent to proving every -vertex digraph has a quasi-kernel with . The forward direction of this was shown in [7], the reverse was shown recently by Ai, Gutin, Liu, and Meng [1] with a somewhat weaker relationship in the constants being proven earlier by Ai, Liu, and Peng [2].
The Small Quasi-kernel Conjecture has been solved for various classes of digraphs, and we refer the reader to the nice survey by P.L. Erdős, Győri, Mezei, Salia, and Tyomkyn [5] for a more thorough overview of these and related results.
Our focus in this paper is in proving bounds for quasi-kernels which hold for arbitrary digraphs. In recent breakthrough work, Rutschmann [6] improved the best known lower bound for the Large Quasi-kernel Conjecture to for all -vertex digraphs. Additionally, he proved a general transference theorem from the Large Quasi-kernel Conjecture to the Small Quasi-kernel Conjecture, thereby establishing a corresponding upper bound of the form for the Small Quasi-kernel Conjecture as well.
The main result of this paper is a stronger transference theorem between the conjectures which shows that establishing sublinear bounds for one problem is equivalent to establishing a corresponding sublinear bound for the other.
Theorem 1.3. The following statements are equivalent for any real number :
(a) There exists some such that every -vertex digraph has a quasi-kernel with
(b) There exists some such that every -vertex source-free digraph has a quasi-kernel with
Substituting recovers the version of this result stated in the abstract.
Theorem 1.3 combined with the Large Quasi-kernel bound of Rutschmann gives an improved Small Quasi-kernel bound of . The second result of our paper slightly refines Rutschmann’s argument to get rid of the terms in both exponents.
Theorem 1.4. Every -vertex digraph has a quasi-kernel with
and every -vertex source-free digraph has a quasi-kernel with
The constants of this theorem are far from optimized.
AI Declaration. Every proof in this paper is due to ChatGPT’s Astra 6, though most of its ideas appeared previously in entirely human generated papers [2, 6, 7]. Notably, we prompted Astra several times to go beyond the bound of for the Large Quasi-kernel Conjecture, but it failed to do so until the paper of Rutschmann’s appeared. While Theorem 1.4 gives the best known bounds for these problems, we emphasize that the main ideas all originate with Rutschmann. Every word of this paper was written by the author and we take full responsibility for its mathematical contents.
Acknowledgments. Access to ChatGPT Astra was provided to us by the ChatGPT for Academic Researchers program. We thank Peter L. Erdős for helpful comments.
Preliminaries
In what follows, we recall the basic digraph notation where to mean the digraph obtained by deleting every vertex of from , as well as to mean the digraph obtained by deleting every vertex not in from .
Our proof of Theorem 1.4 as well as part of our proof of Theorem 1.3 requires us to construct quasi-kernels satisfying certain conditions. This is accomplished through the following lemma, which is a straightforward adaptation of the original proof by Chvátal and Lovász [3] showing quasi-kernels exist.
Lemma 2.1. Let be a digraph and an independent set of . For every quasi-kernel of , there exists a quasi-kernel satisfying
and
Proof. Take . Since the set is independent by construction. The set reaches every vertex of within two steps, and by definition reaches every vertex of within one step and hence every vertex of within two steps. This proves is a quasi-kernel, and by construction it satisfies all of the conditions of the lemma.
Iteratively applying this lemma gives the following.
Corollary 2.2. Let be a sequence of digraphs obtained by having for some independent set of .
(a) For every quasi-kernel of , there exists a quasi-kernel of with .
(b) There exists a quasi-kernel of with .
Proof. We prove (a) by induction on . The case is immediate. For assume we have proven the result for . By Lemma Lemma 2.1 there exists a quasi-kernel of containing , and applying the inductive hypothesis to gives a quasi-kernel of containing .
We prove (b) via showing by reverse induction on that there exists a quasi-kernel of with . The case follows by taking any quasi-kernel of (which exist either by Chvátal and Lovász [3] or by applying Lemma Lemma 2.1). For assume we have already inductively constructed . We can then apply Lemma Lemma 2.1 with respect to and to obtain a quasi-kernel of which satisfies
This establishes the inductive step, proving the result.
We note that Corollary Corollary 2.2 more or less appears in the work of Rutschmann [6] with the digraphs being referred to as CL-subgraphs due to its inspiration from the proof of Chvátal and Lovász.
In addition to these facts about digraphs, we will frequently use without comment the fact that the function for is concave, and hence
for all and .
Proof of Theorem 1.3
We begin by proving small quasi-kernels imply large quasi-kernels. The argument is essentially a more careful analysis of our proof from [7] showing the Small Quasi-kernel Conjecture implies the Large Quasi-kernel Conjecture.
Lemma 3.1. If and are real numbers such that every -vertex source-free digraph has a quasi-kernel with ; then every -vertex digraph has a quasi-kernel with .
Proof. Assume for contradiction that the result is false and choose a counterexample with as small as possible.
Claim 3.2. The digraph does not contain sources.
Proof. Assume had a source and let . Because is a minimal counterexample, there exists a quasi-kernel of with . Observe that is a quasi-kernel of since is a source and . In total,
with this last inequality using that . This contradicts being a counterexample, proving the result.
Let be the maximum size of amongst all quasi-kernels of , and with some foresight we take
Now define a digraph by taking each vertex and adding new vertices together with the arcs for all ; that is, we form by attaching directed leaves to each vertex in the original digraph . Let be a smallest quasikernel of , noting by hypothesis that
It is not difficult to verify that is a quasikernel of and that contains every vertex with (as otherwise would not be a quasikernel for ). These observations imply
with the last step using the definition of . Rearranging this and using gives
Rearranging this yields
which in turn gives
giving the result.
We next prove that large quasi-kernels imply small quasi-kernels. Our proof is based in spirit off the argument of Ai, Liu, and Peng [2 Proposition 4] showing large quasi-kernels (at the linear scale) imply small quasi-kernels. Roughly, their argument works by taking a smallest quasi-kernel , decomposing it into sets in some way, constructing a weighted subgraph with weights based on how many vertices of are covered, finding a large quasi-kernel of , and finally showing that if is large then we can use to replace with a smaller set while maintaining the quasi-kernel condition. This gives a contradiction, showing that we can not have large.
Roughly, our refinement of this approach gets rid of the weighting on and the singular and replaces it with a small set of quasi-kernels whose neighborhoods cover in the following sense.
Lemma 3.3. If are real numbers such that every -vertex digraph has a quasi-kernel with ; then for every digraph there exist quasi-kernels of satisfying and .
Proof. Let . Iteratively, if is not the empty digraph then let be a quasi-kernel of satisfying and let .
We claim that this process stops at for some . Indeed, let . By construction , which together with concavity implies
Since the sequence decreases by at least at each step and since its initial term is , it follows that this process can continue for at most steps as desired.
Since each is in particular an independent set of , it follows that the digraphs satisfy the conditions of Corollary 2.2, and as such Corollary 2.2(a) implies there exist quasi-kernels of with for all . By construction
so this establishes the result. □
We now use this to prove large quasi-kernels imply small quasi-kernels.
Lemma 3.4. If are real numbers such that every -vertex digraph has a quasi-kernel with ; then every -vertex source-free digraph has a quasi-kernel with .
Proof. Let be an -vertex source-free digraph and let be a quasi-kernel of minimum size.
Claim 3.5. There exists with and with .
Proof. By definition for each there exists some with , and taking gives the result. □ Fix such a and define the sets
where is meant to stand for the vertices which are “far” from . Claim 3.5 gives some control over and it remains to bound . To do this, for each let
Claim 3.6. If is a quasi-kernel of , then .
Proof. Define the set
We claim is a quasi-kernel of . Indeed, , being quasi-kernels implies there are no arcs within or , there are no arcs from to by definition of , and there are no arcs from to either or by definition. We have that reaches all of within two steps by definition of being a quasi-kernel of , that reaches all of within two steps by definition of , and that reaches all of within one step and hence all of by definition of . In total reaches all of which equals since is a quasi-kernel.
Now because we chose to be a minimum quasi-kernel this implies
and rearranging gives the desired bound. As an aside, the role of in this argument is analogous to the strictly smaller quasi-kernel mentioned in our comparison with the work of Ai, Liu, and Peng [2].
Crucially, we observe that for every there exists some with . Indeed because is source-free there exists some with . We can not have since this is an independent set, and if we had then would be a strictly smaller quasi-kernel due to Claim 3.5 guaranteeing every vertex which could be reached by continues to be reached by , and this would contradict us defining to be a smallest quasi-kernel.
With this all in mind, let be the quasi-kernels of guaranteed by Lemma 3.3. Because the sets cover all of , the observation above implies for each there exists some with containing an in-neighbor of , which in turn implies . It follows that
Putting everything together, we find
Rearranging this and using gives
proving the result.
We now put these pieces together to formally prove our equivalence result.
Proof of Theorem 1.3. Let . First assume (a) holds, meaning there exists some such that every -vertex digraph has a quasi-kernel with . This assumption continues to hold if we replace with a smaller positive number, so we may assume without loss of generality that . It follows from Lemma 3.4 that (b) holds with .
Now assume (b) holds, meaning there exists some such that every -vertex source-free digraph has a quasi-kernel with . Again we may assume , so it follows from applying Lemma 3.1 with that (a) holds with , proving the result.
Proof of Theorem 1.4
At a high-level, our proof showing every digraph has a quasi-kernel with large works by starting with and then iteratively defining to be a large quasi-kernel of and taking . If we can show this process terminates after a small number of steps, then necessarily some must be large, which by Corollary 2.2 implies there exists some quasi-kernel of which has large. The simplest way to show this process takes a small number of steps would be to show each is large, but this is seemingly as hard as proving the theorem in the first place. To get around this, we instead show is large in terms of for some “nice” set of vertices , from which we will be able to lift the bound with replaced by throughout.
Following Rutschmann [6], we say a vertex in a digraph is eligible if there exists some quasi-kernel of which contains . Let denote the set of eligible vertices of and let
where the maximum ranges over all quasi-kernels of . Intuitively, measures how many eligible vertices we can remove from by deleting some set like how we discussed in the sketch at the start of this section. Our main technical result gives an effective lower bound on this amount of removal.
Lemma 4.1. Every digraph has
Proof. The result is trivial when is the empty digraph, so from now on we assume has at least one vertex which implies .
The key idea of the proof will be to bound the number of arcs of which have both endpoints in , and we denote this quantity by . We first observe
since by definition for any due to the quasi-kernel containing . The remainder of the proof is dedicated towards lower bounding , the rough idea for which is to find a large number of disjoint sets which have many arcs from vertices of . For this the following will be helpful.
Claim 4.2. Let be any sequence of digraphs with and for some independent set of . If is a quasi-kernel of , then
Proof. By Corollary 2.2(a) there exists a quasi-kernel of which contains . This immediately implies as well as
Note that if then the bound of the lemma trivially holds, so we may assume . Define
Let . Iteratively assume we have defined a digraph . Let . Iteratively given that we have defined , let be an inclusion-maximal quasi-kernel of and set . By Corollary 2.2(b) there exists a quasi-kernel of which satisfies . We then define and we stop this process upon defining .
Observe that each is a digraph of the form from Claim 4.2. It follows then that for each quasi-kernel of we have and . Similarly we have for all . Thus as we construct our and digraphs by deleting either or , we iteratively are removing at most vertices from , which means for all we have
with the second inequality using that is obtained by deleting sets of the form and the last inequality used by definition. Observe that each is a maximal independent set in since it is an inclusion-maximal quasi-kernel. This in particular means every vertex in has an arc to some vertex in , and the number of such vertices lying in is at least
Thus every set has at least arcs from vertices of . Finally, we note that each of the sets are pairwise disjoint; this is evident for , and for with say this follows from being formed by deleting which contains . Since each set lies in , putting all this together with the previous observation implies
The definition of implies , and plugging this in and rearranging gives
Taking cube roots on both sides and dividing by 8 gives the result.
We conclude with our main proof of the section.
Proof of Theorem 1.4. The upper bound on for source-free digraphs will follow from applying Lemma 3.4 with and , so it remains to prove the lower bound on .
Let . Iteratively given , let be a quasi-kernel of satisfying and define . Let be the smallest integer such that is empty.
For ease of notation let and . By how we defined , we have by Lemma 2.1 that every quasi-kernel of is contained in a quasi-kernel of , meaning . In particular this implies . Now Lemma 4.1 implies for all , and using this together with concavity implies
Since the sequence decreases by at least and since for all , we conclude that this process must stop at
Now let be the maximum size of amongst all quasi-kernels of . Because the are of the form from Corollary 2.2, for every quasi-kernel of there exists a quasi-kernel of which necessarily satisfies
Since the sets partition by construction, we necessarily have . We also observe by definition of and that , so Lemma 4.1 implies
Putting all this together gives
and rearranging gives , proving the result.
References
- [1]J. Ai, G. Gutin, X. Liu, and X. Meng. Small and large quasi-kernels: a weighted transfer theorem. arXiv preprint arXiv:2610.23487, 2026.arxiv.org/abs/2610.23487
- [2]J. Ai, X. Liu, and F. Peng. A variable version of the quasi-kernel conjecture. arXiv preprint arXiv:2406.04887, 2024.arxiv.org/abs/2406.04887
- [3]V. Chvátal and L. Lovász. Every directed graph has a semi-kernel. In Hypergraph Seminar: Ohio State University 1972, pages 175–175. Springer, 2006.
- [4]P. L. Erdős. Two conjectures on quasi-kernels, open problems no. 4. in fete of combinatorics and computer science. Bolyai Society Mathematical Studies, 3:11–48, 2010.
- [5]P. L. Erdős, E. Győri, T. R. Mezei, N. Salia, and M. Tyomkyn. On the small quasi-kernel conjecture—a survey. In Information Theory and Related Fields: Festschrift in Memory of Ning Cai, pages 98–110. Springer, 2025.DOI
- [6]D. Rutschmann. Small and large quasi-kernels in general digraphs. arXiv preprint arXiv:2610.29659, 2026.arxiv.org/abs/2610.29659
- [7]S. Spiro. Generalized quasikernels in digraphs. European Journal of Combinatorics, 133:104307, 2026.arxiv.org/abs/2404.07305