The asymptotic number of probabilistic compositional graphoids
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 discrete random variables if it is induced by the conditional-independence relations among those variables. The notation denotes an asymptotic lower bound up to a positive constant factor.
Asymptotic counting conjecture. The number of compositional graphoids which are representable by discrete random variables is asymptotically
for some (or even ).
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.