Extended Knuth conjecture for joint arc-count distributions in random digraph depth-first search

From papers

Consider a random multidigraph on nn vertices in which the outdegree of each vertex is independently distributed as Ge(1p)\operatorname{Ge}(1-p), with p(0,1)p\in(0,1), and endpoints of outgoing arcs chosen independently and uniformly from the nn vertices. In a Depth-First Search, let L,F,B,C,TL,F,B,C,T denote the counts of the corresponding arc types used in the paper. Extended Knuth conjecture. For every n1n\geqslant1 and every p(0,1)p\in(0,1),

(L,F,B+C,T)=d(L,B,F+C,T).(L,F,B+C,T)\overset{\mathrm{d}}{=}(L,B,F+C,T).

This strengthens Knuth's equality in distribution by asserting a joint symmetry involving the other arc counts. It is presented as a conjecture and no resolution is supplied in the source.

Progress summary

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

Sources & referencesView supporting material

Primary source

Svante Janson, “On Knuth's conjecture for back and forward arcs in Depth First Search in a random digraph with geometric outdegree distribution”, arXiv:2301.04131 (2023).

Solutions 0

No solutions have been posted yet.