Extended Knuth conjecture for joint arc-count distributions in random digraph depth-first search
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.
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
Sign in to submit a solution.
No solutions have been posted yet.