The asymptotic number of probabilistic compositional graphoids

A compositional graphoid is a conditional-independence structure satisfying the Composition axiom, and a compositional graphoid is representable by nn discrete random variables if it is induced by the conditional-independence relations among those variables. The notation Ω(nε)\Omega(n^\varepsilon) denotes an asymptotic lower bound up to a positive constant factor.

Asymptotic counting conjecture. The number of compositional graphoids which are representable by nn discrete random variables is asymptotically

22Ω(nε)2^{2^{\Omega(n^\varepsilon)}}

for some ε>0\varepsilon>0 (or even ε>1\varepsilon>1).

This conjecture asks whether probabilistic compositional graphoids are doubly exponentially numerous, paralleling known lower bounds for probabilistic conditional-independence structures and the scarcity of graphical representations. The source proposes the asymptotic estimate but gives no resolution.

Sources & referencesView supporting material

Primary source

Tobias Boege, “On the Intersection and Composition properties of conditional independence”, arXiv:2504.11978 (2026).

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.