The graded-graph path-count conjecture

About 22 years old · traced to

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 B⊆RnB\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

1−P(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.

References

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.