The subexponential bound conjecture for disjoint q-kernels

Let DD be a finite digraph. A source set is a set of vertices with no in-neighbor outside the set, and rr-disjoint qq-kernels are rr pairwise disjoint sets that are each independent and reach every vertex by directed paths of length at most qq.

Subexponential disjoint q-kernel conjecture. There exist constants ε>0\varepsilon>0 and r0r_0 such that, whenever rr0r\ge r_0 and DD contains no (r1)(r-1)-source sets, DD contains rr-disjoint qq-kernels with

q(2ε)r.q\le(2-\varepsilon)^r.

The conjecture would improve the paper's known exponential bound, whose growth rate is approximately 2r2^r. The source identifies substantial barriers to proving it.

Sources & referencesView supporting material

Primary source

Sam Spiro, “Generalized Quasikernels in Digraphs”, arXiv:2404.07305 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.