ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.