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

About 3 years old · traced to

Consider a random multidigraph on nn vertices in which the outdegree of each vertex is independently distributed as Ge⁡(1−p)\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 n⩾1n\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.

References

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).

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.