Small and large quasi-kernels: a weighted transfer theorem

Abstract

A quasi-kernel of a digraph D is an independent set from which every vertex is reachable by a directed path of length at most two. The Small Quasi-kernel Conjecture asserts that every source-free digraph on n vertices has a quasi-kernel of size at most n/2, whereas the Large Quasi-kernel Conjecture asks for a quasi-kernel whose closed out-neighbourhood has size at least n/2. Spiro proved that the former implies the latter. In this paper, we establish a weighted transfer theorem: if every nonnegative integer weighting of a source-free digraph D admits a quasi-kernel whose closed out-neighbourhood contains at least a θ-fraction of the total weight, then D has a quasi-kernel of size at most ⌊(1−θ)α(D)+θμ⌋ for 0<θ≤1/2, where μ is the maximum matching size between a maximum independent set and its complement. Using the independent blow-up construction of Spiro, we deduce that the universal small and large quasi-kernel assertions are equivalent for every such θ, with no loss in the parameter. In particular, the two conjectures are equivalent. As an application, we prove the half-order bound for source-free break digraphs.

Small and Large Quasi-Kernels in General Digraphs
Daniel Rutschmann
arXiv21 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
σTransfer: Uncertainty Transfer from Small to Large Networks under μP
Richard Bergna, Fernando Ruiz Mazo, Nicolò Felicioni +2
arXiv8 Oct 2026PreprintarXiv licenceFull textStatisticsarXiv
Transfer kernels and the Schur multiplier
Franz Lemmermeyer
arXiv28 Oct 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv
Weighted H^p−L^q boundedness of integral operators with rough kernels
Andrea L. Gallo, M. Silvina Riveros, Lucas A. Vallejos
arXiv23 Oct 2026PreprintCC BY 4.0Full textAnalysis & PDEsarXiv
A Tb type theorem for suppressed kernels
Marina Fernàndez-Vilaseca
arXiv3 Nov 2026PreprintCC BY 4.0Full textAnalysis & PDEsarXiv

Cite

BibTeX RIS

BibTeX

@misc{ai2026small,
  title = {{Small and large quasi-kernels: a weighted transfer theorem}},
  author = {Jiangdong Ai and Gregory Gutin and Xiangzhou Liu and Xianhao Meng},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.23487},
  eprint = {2610.23487},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.23487},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Small and large quasi-kernels: a weighted transfer theorem
AU  - Jiangdong Ai
AU  - Gregory Gutin
AU  - Xiangzhou Liu
AU  - Xianhao Meng
PY  - 2026
DA  - 2026/10/16
PB  - arXiv
DO  - 10.48550/arxiv.2610.23487
UR  - https://arxiv.org/abs/2610.23487
AB  - A quasi-kernel of a digraph D is an independent set from which every vertex is reachable by a directed path of length at most two. The Small Quasi-kernel Conjecture asserts that every source-free digraph on n vertices has a quasi-kernel of size at most n/2, whereas the Large Quasi-kernel Conjecture asks for a quasi-kernel whose closed out-neighbourhood has size at least n/2. Spiro proved that the former implies the latter. In this paper, we establish a weighted transfer theorem: if every nonnegative integer weighting of a source-free digraph D admits a quasi-kernel whose closed out-neighbourhood contains at least a θ-fraction of the total weight, then D has a quasi-kernel of size at most ⌊(1−θ)α(D)+θμ⌋ for 0<θ≤1/2, where μ is the maximum matching size between a maximum independent set and its complement. Using the independent blow-up construction of Spiro, we deduce that the universal small and large quasi-kernel assertions are equivalent for every such θ, with no loss in the parameter. In particular, the two conjectures are equivalent. As an application, we prove the half-order bound for source-free break digraphs.
ER  -

Abstract

Related

Cite