Extended Knuth conjecture for joint arc-count distributions in random digraph depth-first search
Consider a random multidigraph on vertices in which the outdegree of each vertex is independently distributed as , with , and endpoints of outgoing arcs chosen independently and uniformly from the vertices. In a Depth-First Search, let denote the counts of the corresponding arc types used in the paper. Extended Knuth conjecture. For every and every ,
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
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.