The graded-graph path-count conjecture

Let GG be a graded graph of height nn, and let K(G)K(G) be the number of oriented paths that pass through every level of GG. Let X(σ)X(\sigma) be independent, identically distributed random variables with common law μ\mu, and let BRnB\subseteq\mathbb{R}^n. Write P(B;G)P(B;G) for the probability that the labels along a path in GG produce a vector in BB.

Graded-graph path-count conjecture. One has

1P(B;G)(1μn(B))K(G).1-P(B;G)\geq\left(1-\mu^n(B)\right)^{K(G)}.

This conjecture extends the corresponding inequality for trees to arbitrary graded graphs. It asserts that the number of complete oriented paths alone gives the same lower bound for the probability that no path produces a vector in BB; its resolution is not specified in the source.

Sources & referencesView supporting material

Primary source

Robin Pemantle and Yuval Peres, “Domination Between Trees and Application to an Explosion Problem”, arXiv:math/0404044 (2004).

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.