The delta-process tree probability conjecture

About 11 years old · traced to

Let kk and rr be positive integers with r<kr<k, let p=(p1,…,pk)\textbf{p}=(p_1,\ldots,p_k) be a tuple of non-negative integers, and let Rp,r\mathcal{R}_{\textbf{p},r} be the specified set of rr-tuples of subsets. Suppose this set is non-empty. Choose S=(S1,…,Sr)\textbf{S}=(S_1,\ldots,S_r) uniformly from Rp,r\mathcal{R}_{\textbf{p},r} and choose a surjection f:[k−1]→[r]f:[k-1]\to[r] uniformly and independently of S\textbf{S}. Let Gδ(S,f)G_\delta(\textbf{S},f) be the random digraph defined by the delta rule, and write Pδ(p,r)P_\delta(\textbf{p},r) for the probability that it is a tree.

The delta-process tree probability conjecture. One has

Pδ(p,r)=∣Rp,r−1∣∣Rp,r∣.P_\delta(\textbf{p},r)=\frac{|\mathcal{R}_{\textbf{p},r-1}|}{|\mathcal{R}_{\textbf{p},r}|}.

This is equal to the probability that S1=∅S_1=\emptyset.

The paper states that this conjecture suggests a simple expression for the tree probability and reports that it could not be proved. It is equivalent there to an identity involving a generalized probabilistic determinant.

References

Primary source

Olivier Bernardi and Alejandro H. Morales, “Some probabilistic trees with algebraic roots”, arXiv:1501.01135 (2015).

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.