betaFeedback

WorksMathematics

Equivalence of Small and Large Quasi-kernels

Abstract

A quasi-kernel of a digraph DD is an independent set which can reach every vertex of DD by a directed path of length at most 2. The Small Quasi-kernel Conjecture states that every nn-vertex source-free digraph DD contains a quasi-kernel QQ with ∣Q∣≤n/2|Q|\le n/2, and the Large Quasi-kernel Conjecture states that every nn-vertex digraph DD contains a quasi-kernel QQ with ∣N+[Q]∣≥n/2|N^+[Q]|\ge n/2. Our main result shows for any 12<β<1\frac{1}{2}<β<1 an equivalence between the following two statements: Every n-vertex source-free digraph contains a quasi-kernel with ∣Q∣≤n−Ω(nβ).\textrm{Every }n\textrm{-vertex source-free digraph contains a quasi-kernel with } |Q|\le n-Ω(n^β). Every n-vertex digraph contains a quasi-kernel with ∣N+[Q]∣≥Ω(n2−1β).\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−Ω(n3/4)n-Ω(n^{3/4}) and Ω(n2/3)Ω(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.

Introduction

This paper concerns problems about (finite) digraphs, for which we recall a few definitions. Given vertices uu, vv of a digraph DD, we define dist⁡(u,v)\operatorname{dist}(u,v) to be the length of a shortest directed path from uu to vv, and for a set of vertices SS we define dist⁡(S,v)=min⁡u∈Sdist⁡(u,v)\operatorname{dist}(S,v)=\min_{u\in S}\operatorname{dist}(u,v). We say a set of vertices SS is independent if there exist no arcs between two vertices of SS. The main definition for this paper is the following.

Definition 1. A set of vertices QQ of a digraph DD is said to be a quasi-kernel if (1) QQ is an independent set and (2) dist⁡(Q,x)≤2\operatorname{dist}(Q,x)\le2 for all x∈V(D)x\in V(D) (that is, every vertex x∈V(D)x\in V(D) can be reached from QQ 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 nn-vertex source-free digraph DD contains a quasi-kernel QQ with ∣Q∣≤12n|Q| \le\frac{1}{2}n.

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 DD and a set S⊆V(D)S \subseteq V(D) we write

ND+(S)={v∈V(D)∖S:∃u∈S, uv∈E(D)},ND+[S]=S∪ND+(S),N_D^{+}(S)=\{v\in V(D)\setminus S:\exists u\in S,\ uv\in E(D)\},\qquad N_D^{+}[S]=S\cup N_D^{+}(S),

and we denote these sets simply by N+(S)N^{+}(S) and N+[S]N^{+}[S] whenever DD is clear from context.

Conjecture 1.2 (Large Quasi-kernel Conjecture). Every nn-vertex digraph DD contains a quasi-kernel QQ with ∣N+[Q]∣≥12n|N^{+}[Q]|\ge\frac{1}{2}n.

The Small and Large Quasi-kernel Conjectures are equivalent in a strong sense: for all 0<ε≤120<\varepsilon\le\frac{1}{2}, proving every nn-vertex source-free digraph has a quasi-kernel QQ with ∣Q∣≤(1−ε)n|Q|\le(1-\varepsilon)n is equivalent to proving every nn-vertex digraph has a quasi-kernel QQ with ∣N+[Q]∣≥εn|N^{+}[Q]|\ge\varepsilon n. 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 n2/3−o(1)n^{2/3-o(1)} for all nn-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 n−n2/3−o(1)n-n^{2/3-o(1)} 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 0<α<10<\alpha<1:

(a) There exists some c>0c>0 such that every nn-vertex digraph has a quasi-kernel QQ with

∣N+[Q]∣≥cnα.|N^{+}[Q]|\ge cn^{\alpha}.

(b) There exists some c′>0c'>0 such that every nn-vertex source-free digraph has a quasi-kernel QQ with

∣Q∣≤n−c′n12−α.|Q|\le n-c'n^{\frac{1}{2-\alpha}}.

Substituting β=12−α\beta= \frac{1}{2-\alpha} 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 n−n3/4−o(1)n-n^{3/4-o(1)}. The second result of our paper slightly refines Rutschmann’s argument to get rid of the o(1)o(1) terms in both exponents.

Theorem 1.4. Every nn-vertex digraph has a quasi-kernel QQ with

∣ND+[Q]∣≥164n2/3,\lvert N_D^+[Q]\rvert\ge\frac{1}{64}n^{2/3},

and every nn-vertex source-free digraph has a quasi-kernel QQ with

∣Q∣≤n−1768n3/4.\lvert Q\rvert\le n-\frac{1}{768}n^{3/4}.

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 Ω(n1/2)\Omega(n^{1/2}) 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 D−SD-S where S⊆V(D)S\subseteq V(D) to mean the digraph obtained by deleting every vertex of SS from DD, as well as D[S]D[S] to mean the digraph obtained by deleting every vertex not in SS from DD.

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 DD be a digraph and II an independent set of DD. For every quasi-kernel Q′Q' of D′:=D−ND+[I]D' := D-N_D^+[I], there exists a quasi-kernel QQ satisfying

Q′⊆Q,Q' \subseteq Q,

and

I⊆ND+[Q].I \subseteq N_D^+[Q].

Proof. Take Q=Q′∪(I∖ND+(Q′))Q=Q'\cup(I\setminus N_D^+(Q')). Since Q′⊆V(D)−ND+[I]Q'\subseteq V(D)-N_D^+[I] the set QQ is independent by construction. The set Q′⊆QQ'\subseteq Q reaches every vertex of V(D′)=V(D)−ND+[I]V(D')=V(D)-N_D^+[I] within two steps, and QQ by definition reaches every vertex of II within one step and hence every vertex of ND+[I]N_D^+[I] within two steps. This proves QQ 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 D1,…,DtD_1,\ldots,D_t be a sequence of digraphs obtained by having Di+1=Di−NDi+[Ii]D_{i+1}=D_i-N_{D_i}^+[I_i] for some independent set IiI_i of DiD_i.

(a) For every quasi-kernel QiQ_i of DiD_i, there exists a quasi-kernel Q1Q_1 of D1D_1 with Qi⊆Q1Q_i\subseteq Q_1.

(b) There exists a quasi-kernel Q1Q_1 of D1D_1 with I1∪⋯∪It−1⊆ND1+[Q1]I_1\cup\cdots\cup I_{t-1}\subseteq N_{D_1}^+[Q_1].

Proof. We prove (a) by induction on ii. The i=1i=1 case is immediate. For i>1i>1 assume we have proven the result for i−1i-1. By Lemma Lemma 2.1 there exists a quasi-kernel Qi−1Q_{i-1} of Di−1D_{i-1} containing QiQ_i, and applying the inductive hypothesis to Qi−1Q_{i-1} gives a quasi-kernel of D1D_1 containing Qi−1⊇QiQ_{i-1}\supseteq Q_i.

We prove (b) via showing by reverse induction on 1≤i≤t1\leq i\leq t that there exists a quasi-kernel QiQ_i of DiD_i with Ii∪Ii+1⋯∪It−1⊆NDi+[Qi]I_i\cup I_{i+1}\cdots\cup I_{t-1}\subseteq N_{D_i}^+[Q_i]. The i=ti=t case follows by taking any quasi-kernel of DtD_t (which exist either by Chvátal and Lovász [3] or by applying Lemma Lemma 2.1). For i<ti<t assume we have already inductively constructed Qi+1Q_{i+1}. We can then apply Lemma Lemma 2.1 with respect to Q′=Qi+1Q'=Q_{i+1} and I=IiI=I_i to obtain a quasi-kernel QiQ_i of DiD_i which satisfies

NDi+[Qi]⊇Ii∪NDi+1+[Qi+1]⊇Ii∪Ii+1⋯∪It−1.N_{D_i}^+[Q_i]\supseteq I_i\cup N_{D_{i+1}}^+[Q_{i+1}]\supseteq I_i\cup I_{i+1}\cdots\cup I_{t-1}.

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 DiD_i 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 f(x)=xγf(x)=x^\gamma for 0<γ≤10<\gamma\leq1 is concave, and hence

xγ−yγ≥γxγ−1(x−y)x^\gamma-y^\gamma\geq\gamma x^{\gamma-1}(x-y)

for all x>0x>0 and y≥0y\geq0.

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 0<c<10<c<1 and 12<β<1\frac{1}{2}<\beta<1 are real numbers such that every nn-vertex source-free digraph D′D' has a quasi-kernel Q′Q' with ∣Q′∣≤n−cnβ|Q'|\leq n-cn^\beta; then every nn-vertex digraph DD has a quasi-kernel QQ with ∣N+[Q]∣≥12c1/βn2−1β|N^+[Q]|\geq\frac{1}{2}c^{1/\beta}n^{2-\frac{1}{\beta}}.

Proof. Assume for contradiction that the result is false and choose a counterexample DD with nn as small as possible.

Claim 3.2. The digraph DD does not contain sources.

Proof. Assume DD had a source vv and let d:=∣ND+[v]∣d := |N_D^+[v]|. Because DD is a minimal counterexample, there exists a quasi-kernel Q′Q' of D′:=D−ND+[v]D' := D - N_D^+[v] with ∣ND′+[Q′]∣≥18c1/β(n−d)2−1/β|N_{D'}^+[Q']| \ge\frac{1}{8}c^{1/\beta}(n-d)^{2-1/\beta}. Observe that Q:=Q′∪{v}Q := Q' \cup\{v\} is a quasi-kernel of DD since vv is a source and ND+[v]∩Q′=∅N_D^+[v] \cap Q' = \varnothing. In total,

∣ND+[Q]∣≥∣ND′+[Q′]∣+∣ND+[v]∣≥18c1/β(n−d)2−1/β+d≥18c1/β[(n−d)2−1/β+d]≥18c1/βn2−1/β,\begin{aligned} |N_D^+[Q]| \ge|N_{D'}^+[Q']| + |N_D^+[v]| \ge\frac{1}{8}c^{1/\beta}(n-d)^{2-1/\beta} + d \\ &\ge\frac{1}{8}c^{1/\beta}[(n-d)^{2-1/\beta} + d] \ge\frac{1}{8}c^{1/\beta}n^{2-1/\beta}, \end{aligned}

with this last inequality using that 2−1/β≤12 - 1/\beta\le1. This contradicts DD being a counterexample, proving the result.

Let mm be the maximum size of ∣ND+[Q]∣|N_D^+[Q]| amongst all quasi-kernels QQ of DD, and with some foresight we take

k:=⌊nm⌋≥1.k := \left\lfloor\frac{n}{m} \right\rfloor\ge1.

Now define a digraph D′D' by taking each vertex v∈V(D)v \in V(D) and adding kk new vertices v1,…,vkv_1,\ldots,v_k together with the arcs vvivv_i for all ii; that is, we form D′D' by attaching kk directed leaves to each vertex in the original digraph DD. Let Q′Q' be a smallest quasikernel of D′D', noting by hypothesis that

∣Q′∣≤∣V(D′)∣−c∣V(D′)∣β=(k+1)n−c((k+1)n)β.|Q'| \le|V(D')| - c|V(D')|^\beta= (k+1)n - c((k+1)n)^\beta.

It is not difficult to verify that Q:=Q′∩V(D)Q := Q' \cap V(D) is a quasikernel of DD and that Q′∖Q=Q′∖V(D)Q' \setminus Q = Q' \setminus V(D) contains every vertex viv_i with v∈V(D)∖ND+[Q]v \in V(D) \setminus N_D^+[Q] (as otherwise Q′Q' would not be a quasikernel for D′D'). These observations imply

(k+1)n−c((k+1)n)β≥∣Q′∣≥∣Q′∖Q∣≥k(n−∣ND+[Q]∣)≥k(n−m),(k+1)n - c((k+1)n)^\beta\ge|Q'| \ge|Q' \setminus Q| \ge k(n - |N_D^+[Q]|) \ge k(n-m),

with the last step using the definition of mm. Rearranging this and using n/2m≤k≤n/mn/2m \le k \le n/m gives

c(n22m)β≤c((k+1)n)β≤n+km≤2n.c\left(\frac{n^2}{2m}\right)^\beta\le c((k+1)n)^\beta\le n + km \le2n.

Rearranging this yields

(2m)β≥12cn2β−1,(2m)^\beta\ge\frac{1}{2}cn^{2\beta-1},

which in turn gives

m≥2−1−1/βc1/βn2−1/β≥2−3c1/βn2−1/β,m \ge2^{-1-1/\beta}c^{1/\beta}n^{2-1/\beta} \ge2^{-3}c^{1/\beta}n^{2-1/\beta},

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 QQ, decomposing it into sets Q1∪Q2Q_1 \cup Q_2 in some way, constructing a weighted subgraph D~⊆D\widetilde{D} \subseteq D with weights based on how many vertices of Q2Q_2 are covered, finding a large quasi-kernel Q~\widetilde{Q} of D~\widetilde{D}, and finally showing that if ∣Q∣|Q| is large then we can use Q~\widetilde{Q} to replace Q2Q_2 with a smaller set while maintaining the quasi-kernel condition. This gives a contradiction, showing that we can not have ∣Q∣|Q| large.

Roughly, our refinement of this approach gets rid of the weighting on D~\widetilde{D} and the singular Q~\widetilde{Q} and replaces it with a small set of quasi-kernels whose neighborhoods cover D~\widetilde{D} in the following sense.

Lemma 3.3. If 0<c,α<10 < c, \alpha< 1 are real numbers such that every nn-vertex digraph D′D' has a quasi-kernel Q′Q' with ∣ND′+[Q′]∣≥cnα|N^+_{D'}[Q']| \ge cn^\alpha; then for every digraph DD there exist quasi-kernels R1,…,RtR_1, \ldots, R_t of DD satisfying ⋃i=1tND+[Ri]=V(D)\bigcup_{i=1}^{t} N^+_D[R_i] = V(D) and t≤1c(1−α)∣V(D)∣1−αt \le\frac{1}{c(1-\alpha)}|V(D)|^{1-\alpha}.

Proof. Let D1=DD_1 = D. Iteratively, if DiD_i is not the empty digraph then let Qi⊆V(Di)Q_i \subseteq V(D_i) be a quasi-kernel of DiD_i satisfying ∣NDi+[Qi]∣≥c∣V(Di)∣α|N^+_{D_i}[Q_i]| \ge c|V(D_i)|^\alpha and let Di+1=Di−NDi+[Qi]D_{i+1} = D_i - N^+_{D_i}[Q_i].

We claim that this process stops at Dt+1=∅D_{t+1} = \varnothing for some t≤1c(1−α)∣V(D)∣1−αt \le\frac{1}{c(1-\alpha)}|V(D)|^{1-\alpha}. Indeed, let ni:=∣V(Di)∣n_i := |V(D_i)|. By construction ni+1≤ni−cniαn_{i+1} \le n_i - cn_i^\alpha, which together with concavity implies

ni1−α−ni+11−α≥(1−α)ni−α(ni−ni+1)≥c(1−α).n_i^{1-\alpha} - n_{i+1}^{1-\alpha} \ge(1-\alpha)n_i^{-\alpha}(n_i-n_{i+1}) \ge c(1-\alpha).

Since the sequence ni1−αn_i^{1-\alpha} decreases by at least c(1−α)c(1-\alpha) at each step and since its initial term is ∣V(D)∣1−α|V(D)|^{1-\alpha}, it follows that this process can continue for at most 1c(1−α)∣V(D)∣1−α\frac{1}{c(1-\alpha)}|V(D)|^{1-\alpha} steps as desired.

Since each QiQ_i is in particular an independent set of DiD_i, it follows that the DiD_i digraphs satisfy the conditions of Corollary 2.2, and as such Corollary 2.2(a) implies there exist quasi-kernels R1,…,RtR_1, \ldots, R_t of DD with Qi⊆RiQ_i \subseteq R_i for all ii. By construction

⋃i=1tND+[Ri]⊇⋃i=1tNDi+[Qi]=V(D),\bigcup_{i=1}^{t} N^+_D[R_i] \supseteq\bigcup_{i=1}^{t} N^+_{D_i}[Q_i] = V(D),

so this establishes the result. □

We now use this to prove large quasi-kernels imply small quasi-kernels.

Lemma 3.4. If 0<c,α<10 < c, \alpha< 1 are real numbers such that every nn-vertex digraph D′D' has a quasi-kernel Q′Q' with ∣ND′+[Q′]∣≥cnα|N^+_{D'}[Q']| \ge cn^\alpha; then every nn-vertex source-free digraph DD has a quasi-kernel QQ with ∣Q∣≤n−c(1−α)4n12−α|Q| \le n - \frac{c(1-\alpha)}{4}n^{\frac{1}{2-\alpha}}.

Proof. Let DD be an nn-vertex source-free digraph and let Q⊆V(D)Q \subseteq V(D) be a quasi-kernel of minimum size.

Claim 3.5. There exists Q1⊆QQ_1 \subseteq Q with N+(Q1)=N+(Q)N^+(Q_1) = N^+(Q) and with ∣Q1∣≤∣N+(Q)∣|Q_1| \le|N^+(Q)|.

Proof. By definition for each v∈N+(Q)v \in N^+(Q) there exists some v′∈Qv' \in Q with v∈N+(v′)v \in N^+(v'), and taking Q1={v′:v∈N+(Q)}Q_1 = \{v' : v \in N^+(Q)\} gives the result. □ Fix such a Q1Q_1 and define the sets

Q2=Q∖Q1,F=V(D)∖ND+[Q],Q_2 = Q \setminus Q_1, \qquad F = V(D) \setminus N_D^+[Q],

where FF is meant to stand for the vertices which are “far” from QQ. Claim 3.5 gives some control over ∣Q1∣|Q_1| and it remains to bound Q2Q_2. To do this, for each R⊆FR \subseteq F let

CR={v∈Q2:dist⁡(R,v)≤2}.C_R = \{v \in Q_2 : \operatorname{dist}(R,v) \le2\}.

Claim 3.6. If R⊆FR \subseteq F is a quasi-kernel of D[F]D[F], then ∣CR∣≤∣R∣|C_R| \le|R|.

Proof. Define the set

Q′=R∪(Q2∖CR)∪(Q1∖ND+(R)).Q' = R \cup(Q_2 \setminus C_R) \cup(Q_1 \setminus N_D^+(R)).

We claim Q′Q' is a quasi-kernel of DD. Indeed, RR, QQ being quasi-kernels implies there are no arcs within RR or (Q2∖CR)∪(Q1∖ND+(R))⊆Q(Q_2 \setminus C_R) \cup(Q_1 \setminus N_D^+(R)) \subseteq Q, there are no arcs from Q1∪Q2Q_1 \cup Q_2 to RR by definition of R⊆FR \subseteq F, and there are no arcs from RR to either Q1∖ND+(R)Q_1 \setminus N_D^+(R) or Q2∖CRQ_2 \setminus C_R by definition. We have that RR reaches all of FF within two steps by definition of RR being a quasi-kernel of D[F]D[F], that R∪(Q2∖CR)R \cup(Q_2 \setminus C_R) reaches all of Q2Q_2 within two steps by definition of CRC_R, and that R∪(Q1∖ND+(R))R \cup(Q_1 \setminus N_D^+(R)) reaches all of Q1Q_1 within one step and hence all of ND+(Q)N_D^+(Q) by definition of Q1Q_1. In total Q′Q' reaches all of Q∪ND+(Q)∪FQ \cup N_D^+(Q) \cup F which equals V(D)V(D) since QQ is a quasi-kernel.

Now because we chose QQ to be a minimum quasi-kernel this implies

∣Q∣≤∣Q′∣=∣R∣+∣Q∣−∣CR∣−∣Q1∩ND+(R)∣≤∣R∣+∣Q∣−∣CR∣,|Q| \le|Q'| = |R| + |Q| - |C_R| - |Q_1 \cap N_D^+(R)| \le|R| + |Q| - |C_R|,

and rearranging gives the desired bound. As an aside, the role of Q′Q' 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 v∈Q2v \in Q_2 there exists some u∈Fu \in F with v∈N+(u)v \in N^+(u). Indeed because DD is source-free there exists some uu with v∈N+(u)v \in N^+(u). We can not have u∈Qu \in Q since this is an independent set, and if we had u∈N+(Q)u \in N^+(Q) then Q∖{v}Q \setminus\{v\} would be a strictly smaller quasi-kernel due to Claim 3.5 guaranteeing every vertex which could be reached by QQ continues to be reached by Q∖{v}Q \setminus\{v\}, and this would contradict us defining QQ to be a smallest quasi-kernel.

With this all in mind, let R1,…,RtR_1, \ldots, R_t be the quasi-kernels of D[F]D[F] guaranteed by Lemma 3.3. Because the ND[F]+[Ri]N_{D[F]}^+[R_i] sets cover all of FF, the observation above implies for each v∈Q2v \in Q_2 there exists some ii with ND[F]+[Ri]N_{D[F]}^+[R_i] containing an in-neighbor of vv, which in turn implies v∈CRiv \in C_{R_i}. It follows that

∣Q2∣≤∑i=1t∣CRi∣≤∑i=1t∣Ri∣≤t⋅∣F∣≤1c(1−α)∣F∣2−α.|Q_2| \le\sum_{i=1}^{t} |C_{R_i}| \le\sum_{i=1}^{t} |R_i| \le t \cdot|F| \le\frac{1}{c(1-\alpha)}|F|^{2-\alpha}.

Putting everything together, we find

∣V(D)∣=∣Q1∣+∣Q2∣+∣ND+(Q)∣+∣F∣≤∣ND+(Q)∣+1c(1−α)∣F∣2−α+∣ND+(Q)∣+∣F∣≤4c(1−α)∣ND+(Q)∪F∣2−α.\begin{aligned} |V(D)| = |Q_1| + |Q_2| + |N_D^+(Q)| + |F| \\ &\le|N_D^+(Q)| + \frac{1}{c(1-\alpha)}|F|^{2-\alpha} + |N_D^+(Q)| + |F| \le\frac{4}{c(1-\alpha)}|N_D^+(Q) \cup F|^{2-\alpha}. \end{aligned}

Rearranging this and using ∣ND+(Q)∪F∣=∣V(D)∣−∣Q∣|N_D^+(Q) \cup F| = |V(D)| - |Q| gives

∣Q∣≤∣V(D)∣−(c(1−α)4)12−α∣V(D)∣12−α≤∣V(D)∣−c(1−α)4∣V(D)∣12−α,|Q| \le|V(D)| - \left(\frac{c(1-\alpha)}{4}\right)^{\frac{1}{2-\alpha}} |V(D)|^{\frac{1}{2-\alpha}} \le|V(D)| - \frac{c(1-\alpha)}{4}|V(D)|^{\frac{1}{2-\alpha}},

proving the result.

We now put these pieces together to formally prove our equivalence result.

Proof of Theorem 1.3. Let 0<α<10 < \alpha< 1. First assume (a) holds, meaning there exists some c>0c > 0 such that every nn-vertex digraph has a quasi-kernel QQ with ∣N+[Q]∣≥cnα|N^+[Q]| \ge cn^\alpha. This assumption continues to hold if we replace cc with a smaller positive number, so we may assume without loss of generality that c<1c < 1. It follows from Lemma 3.4 that (b) holds with c′=c(1−α)4>0c' = \frac{c(1-\alpha)}{4} > 0.

Now assume (b) holds, meaning there exists some c′>0c' > 0 such that every nn-vertex source-free digraph has a quasi-kernel with ∣Q∣≤n−c′n12−α|Q| \le n - c'n^{\frac{1}{2-\alpha}}. Again we may assume c′<1c' < 1, so it follows from applying Lemma 3.1 with β=12−α\beta= \frac{1}{2-\alpha} that (a) holds with c=18(c′)2−α>0c = \frac{1}{8}(c')^{2-\alpha} > 0, proving the result.

Proof of Theorem 1.4

At a high-level, our proof showing every digraph DD has a quasi-kernel with ∣N+[Q]∣|N^+[Q]| large works by starting with D1=DD_1 = D and then iteratively defining QiQ_i to be a large quasi-kernel of DiD_i and taking Di+1=Di−N+[Qi]D_{i+1} = D_i - N^+[Q_i]. If we can show this process terminates after a small number of steps, then necessarily some ∣N+[Qi]∣|N^+[Q_i]| must be large, which by Corollary 2.2 implies there exists some quasi-kernel Q⊇QiQ \supseteq Q_i of DD which has ∣N+[Q]∣|N^+[Q]| large. The simplest way to show this process takes a small number of steps would be to show each N+[Qi]N^+[Q_i] is large, but this is seemingly as hard as proving the theorem in the first place. To get around this, we instead show N+[Qi]∩LN^+[Q_i] \cap L is large in terms of ∣L∣|L| for some “nice” set of vertices LL, from which we will be able to lift the bound with LL replaced by V(D)V(D) throughout.

Following Rutschmann [6], we say a vertex vv in a digraph DD is eligible if there exists some quasi-kernel QQ of DD which contains vv. Let L(D)L(D) denote the set of eligible vertices of DD and let

r(D)=max⁡Q∣ND+[Q]∩L(D)∣r(D) = \max_Q |N_D^+[Q] \cap L(D)|

where the maximum ranges over all quasi-kernels QQ of DD. Intuitively, r(D)r(D) measures how many eligible vertices we can remove from DD by deleting some N+[Q]N^+[Q] 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 DD has

r(D)≥18∣L(D)∣2/3.r(D) \ge\frac{1}{8}|L(D)|^{2/3}.

Proof. The result is trivial when DD is the empty digraph, so from now on we assume DD has at least one vertex which implies r(D)>0r(D)>0.

The key idea of the proof will be to bound the number of arcs of DD which have both endpoints in L(D)L(D), and we denote this quantity by aL(D)a_L(D). We first observe

aL(D)≤r(D)∣L(D)∣,a_L(D) \le r(D)|L(D)|,

since by definition ∣ND+[v]∩L(D)∣≤r(D)|N^+_D[v]\cap L(D)|\le r(D) for any v∈L(D)v\in L(D) due to the quasi-kernel QQ containing vv. The remainder of the proof is dedicated towards lower bounding aL(D)a_L(D), the rough idea for which is to find a large number of disjoint sets R⊆L(D)R\subseteq L(D) which have many arcs from vertices of L(D)L(D). For this the following will be helpful.

Claim 4.2. Let D1,D2,…D_1,D_2,\ldots be any sequence of digraphs with D1=DD_1=D and Di+1=Di−NDi+[Ii]D_{i+1}=D_i-N^+_{D_i}[I_i] for some independent set IiI_i of DiD_i. If R⊆V(Di)R\subseteq V(D_i) is a quasi-kernel of DiD_i, then

R⊆L(D),∣ND+[R]∩L(D)∣≤r(D).R\subseteq L(D), \qquad|N^+_D[R]\cap L(D)|\le r(D).

Proof. By Corollary 2.2(a) there exists a quasi-kernel QQ of D1=DD_1=D which contains RR. This immediately implies R⊆L(D)R\subseteq L(D) as well as

∣ND+[R]∩L(D)∣≤∣ND+[Q]∩L(D)∣≤r(D).|N^+_D[R]\cap L(D)|\le|N^+_D[Q]\cap L(D)|\le r(D).

Note that if ∣L(D)∣<4r(D)|L(D)|<4r(D) then the bound of the lemma trivially holds, so we may assume ∣L(D)∣≥4r(D)|L(D)|\ge4r(D). Define

k=⌊∣L(D)∣4r(D)⌋≥1.k=\left\lfloor\frac{|L(D)|}{4r(D)}\right\rfloor\ge1.

Let D1=DD_1=D. Iteratively assume we have defined a digraph DiD_i. Let Di,1=DiD_{i,1}=D_i. Iteratively given that we have defined Di,jD_{i,j}, let Ri,jR_{i,j} be an inclusion-maximal quasi-kernel of Di,jD_{i,j} and set Di,j+1=Di,j−N+[Ri,j]D_{i,j+1}=D_{i,j}-N^+[R_{i,j}]. By Corollary 2.2(b) there exists a quasi-kernel QiQ_i of DiD_i which satisfies Ri,1∪⋯∪Ri,k⊆N+[Qi]R_{i,1}\cup\cdots\cup R_{i,k}\subseteq N^+[Q_i]. We then define Di+1=Di−NDi+[Qi]D_{i+1}=D_i-N^+_{D_i}[Q_i] and we stop this process upon defining Dk+1D_{k+1}.

Observe that each Di,jD_{i,j} is a digraph of the form from Claim 4.2. It follows then that for each quasi-kernel Ri,jR_{i,j} of Di,jD_{i,j} we have Ri,j⊆L(D)R_{i,j}\subseteq L(D) and ∣ND+[Ri,j]∩L(D)∣≤r(D)|N^+_D[R_{i,j}]\cap L(D)|\le r(D). Similarly we have ∣ND+[Qi]∩L(D)∣≤r(D)|N^+_D[Q_i]\cap L(D)|\le r(D) for all ii. Thus as we construct our DiD_i and Di,jD_{i,j} digraphs by deleting either N+[Qi]N^+[Q_i] or N+[Ri,j]N^+[R_{i,j}], we iteratively are removing at most r(D)r(D) vertices from L(D)L(D), which means for all i,j≤ki,j\le k we have

∣L(D)∩V(Di,j)∣≥∣L(D)∩V(Di)∣−∑s=1j−1∣L(D)∩N+[Ri,s]∣≥∣L(D)∣−(i−1)r(D)−(j−1)r(D)≥∣L(D)∣−2kr(D)+r(D)≥12∣L(D)∣+r(D),\begin{aligned} |L(D)\cap V(D_{i,j})| &\ge|L(D)\cap V(D_i)|-\sum_{s=1}^{j-1}|L(D)\cap N^+[R_{i,s}]|\\ &\ge|L(D)|-(i-1)r(D)-(j-1)r(D)\\ &\ge|L(D)|-2kr(D)+r(D)\\ &\ge\frac{1}{2}|L(D)|+r(D), \end{aligned}

with the second inequality using that DiD_i is obtained by deleting i−1i-1 sets of the form N+[Qi]N^+[Q_i] and the last inequality used k≤∣L(D)∣4r(D)k\le\frac{|L(D)|}{4r(D)} by definition. Observe that each Ri,jR_{i,j} is a maximal independent set in Di,jD_{i,j} since it is an inclusion-maximal quasi-kernel. This in particular means every vertex in Di,j−ND+[Ri,j]D_{i,j}-N_D^+[R_{i,j}] has an arc to some vertex in Ri,jR_{i,j}, and the number of such vertices lying in L(D)L(D) is at least

∣L(D)∩V(Di,j)∣−∣L(D)∩ND+[Ri,j]∣≥(12∣L(D)∣+r(D))−r(D)=12∣L(D)∣.|L(D) \cap V(D_{i,j})|-|L(D) \cap N_D^+[R_{i,j}]| \ge\left(\frac{1}{2}|L(D)|+r(D)\right)-r(D)=\frac{1}{2}|L(D)|.

Thus every Ri,jR_{i,j} set has at least 12∣L(D)∣\frac{1}{2}|L(D)| arcs from vertices of L(D)L(D). Finally, we note that each of the k2k^2 sets Ri,jR_{i,j} are pairwise disjoint; this is evident for Ri,j,Ri,j′R_{i,j},R_{i,j'}, and for Ri,j,Ri′,j′R_{i,j},R_{i',j'} with say i<i′i<i' this follows from Di+1D_{i+1} being formed by deleting N+[Qi]N^+[Q_i] which contains Ri,jR_{i,j}. Since each Ri,jR_{i,j} set lies in L(D)L(D), putting all this together with the previous observation implies

12k2∣L(D)∣≤aL(D)≤r(D)∣L(D)∣.\frac{1}{2}k^2|L(D)| \le a_L(D) \le r(D)|L(D)|.

The definition of kk implies k≥∣L(D)∣8r(D)k \ge\frac{|L(D)|}{8r(D)}, and plugging this in and rearranging gives

∣L(D)∣2≤27r(D)3≤29r(D)3.|L(D)|^2 \le2^7r(D)^3 \le2^9r(D)^3.

Taking cube roots on both sides and dividing by 8 gives the result. □\square

We conclude with our main proof of the section.

Proof of Theorem 1.4. The upper bound on ∣Q∣|Q| for source-free digraphs will follow from applying Lemma 3.4 with c=164c=\frac{1}{64} and α=23\alpha=\frac{2}{3}, so it remains to prove the lower bound on ∣N+[Q]∣|N^+[Q]|.

Let D1=DD_1=D. Iteratively given DiD_i, let QiQ_i be a quasi-kernel of DiD_i satisfying ∣NDi+[Qi]∩L(Di)∣=r(Di)|N_{D_i}^+[Q_i]\cap L(D_i)|=r(D_i) and define Di+1=Di−NDi+[Qi]D_{i+1}=D_i-N_{D_i}^+[Q_i]. Let tt be the smallest integer such that Dt+1D_{t+1} is empty.

For ease of notation let ℓi=∣L(Di)∣\ell_i=|L(D_i)| and ri=r(Di)r_i=r(D_i). By how we defined Di+1D_{i+1}, we have by Lemma 2.1 that every quasi-kernel Q′Q' of Di+1D_{i+1} is contained in a quasi-kernel of DiD_i, meaning L(Di+1)⊆L(Di)L(D_{i+1})\subseteq L(D_i). In particular this implies ℓi+1≤ℓi−ri\ell_{i+1}\le\ell_i-r_i. Now Lemma 4.1 implies ri≥2−3ℓi2/3r_i\ge2^{-3}\ell_i^{2/3} for all ii, and using this together with concavity implies

ℓi1/3−ℓi+11/3≥ℓi−ℓi+13ℓi2/3≥2−5.\ell_i^{1/3}-\ell_{i+1}^{1/3}\ge\frac{\ell_i-\ell_{i+1}}{3\ell_i^{2/3}}\ge2^{-5}.

Since the sequence ℓi1/3\ell_i^{1/3} decreases by at least 2−52^{-5} and since ℓi≥0\ell_i\ge0 for all ii, we conclude that this process must stop at

t≤25ℓ11/3.t\le2^5\ell_1^{1/3}.

Now let mm be the maximum size of ∣N+[Q]∣|N^+[Q]| amongst all quasi-kernels QQ of DD. Because the DiD_i are of the form from Corollary 2.2, for every quasi-kernel QiQ_i of DiD_i there exists a quasi-kernel Qi′⊇QiQ'_i\supseteq Q_i of D1=DD_1=D which necessarily satisfies

∣NDi+[Qi]∣≤∣ND+[Qi′]∣≤m.|N_{D_i}^+[Q_i]|\le|N_D^+[Q'_i]|\le m.

Since the NDi+[Qi]N_{D_i}^+[Q_i] sets partition V(D)V(D) by construction, we necessarily have ∣V(D)∣≤mt|V(D)|\le mt. We also observe by definition of rr and mm that r(D)≤mr(D)\le m, so Lemma 4.1 implies

∣L(D)∣≤83/2m3/2.|L(D)|\le8^{3/2}m^{3/2}.

Putting all this together gives

∣V(D)∣≤m⋅t≤m⋅25∣L(D)∣1/3≤m⋅27m1/2≤29m3/2,|V(D)| \le m \cdot t \le m \cdot2^{5}|L(D)|^{1/3} \le m \cdot2^{7}m^{1/2} \le2^{9}m^{3/2},

and rearranging gives m≥2−6∣V(D)∣2/3m \ge2^{-6}|V(D)|^{2/3}, proving the result.

References

  1. [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. [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. [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. [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. [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. [6]D. Rutschmann. Small and large quasi-kernels in general digraphs. arXiv preprint arXiv:2610.29659, 2026.arxiv.org/abs/2610.29659
  7. [7]S. Spiro. Generalized quasikernels in digraphs. European Journal of Combinatorics, 133:104307, 2026.arxiv.org/abs/2404.07305

Paper details

vlnc:W_ct75gffh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents