Kybernetika 56 no. 6, 1045-1062, 2020

Construction methods for gaussoids

Tobias Boege and Thomas KahleDOI: 10.14736/kyb-2020-6-1045

Abstract:

\noindent The number of $n$-gaussoids is shown to be a double exponential function in $n$. The necessary bounds are achieved by studying construction methods for gaussoids that rely on prescribing $3$-minors and encoding the resulting combinatorial constraints in a suitable transitive graph. Various special classes of gaussoids arise from restricting the allowed $3$-minors.

Keywords:

normal distribution, conditional independence, gaussoid, cube, minor

Classification:

05B99, 05B35, 60E05

paper.pdf

References:

  1. T. Boege, A. D'Al{\`i}, T. Kahle and B. Sturmfels: The geometry of Gaussoids. Found. Comput. Math. 19 (2019), 4, 775-812.   DOI:10.1007/s10208-018-9396-x
  2. Ch. Godsil and G. Royle: Algebraic Graph Theory. Springer, Graduate Texts in Mathematics 207, 2001.   CrossRef
  3. R. Hemmecke, J. Morton, A. Shiu, B. Sturmfels and O. Wienand: Three counter-examples on semi-graphoids. Combinat. Probab. Comput. 17 (2008), 2, 239-257.   CrossRef
  4. F. Klein: Elementary Mathematics from a Higher Standpoint, II: Geometry, volume 2. Springer, 2016.   DOI:10.1007/978-3-662-49445-5
  5. R. Lněnička and F. Matúš: On Gaussian conditional independence structures. Kybernetika 43 (2007), 3, 327-342.   CrossRef
  6. L. Lovász: Three short proofs in graph theory. J. Combinat. Theory, Series B 19 (1975), 3, 269-271.   DOI:10.1016/0095-8956(75)90089-1
  7. F. Matúš: Conditional independence structures examined via minors. Ann. Math. Artif. Intell. 21 (1997), 1, 99-130.   CrossRef
  8. P. Nelson: Almost all matroids are non-representable. Bull. London Math. Soc. 50 (2018), 245-248.   DOI:10.1112/blms.12141
  9. OEIS Foundation Inc.: The On-Line Encyclopedia of Integer Sequences. Towards Math. Assist., 130-130.   DOI:10.1515/9780691197944-009
  10. M. J. Piff and D. J. A. Welsh: On the number of combinatorial geometries. Bull. London Math. Soc. 3 (1071), 1, 55-56.   DOI:10.1112/blms/3.1.55
  11. K. Sadeghi: Faithfulness of probability distributions and graphs. J. Machine Learning Res. 18 (2017), 1, 5429-5457.   CrossRef
  12. P. Šimecek: Classes of gaussian, discrete and binary representable independence models have no finite characterization. In: Proc. Prague Stochastics 2006, volume 400, pp. 622-631.   CrossRef
  13. N. Sörensson and N. Een: MiniSat v1.13 - A SAT Solver with Conflict-Clause Minimization, 2005.    CrossRef
  14. S. Sullivant: Gaussian conditional independence relations have no finite complete characterization. J. Pure Appl. Algebra 213 (2009), 8, 1502-1506.   DOI:10.1016/j.jpaa.2008.11.026
  15. The Sage Developers: SageMath, the Sage Mathematics Software System (Version 8.0), 2017.    CrossRef
  16. M. Thurley: sharpSAT - Counting Models with Advanced Component Caching and Implicit BCP. In: Theory and Applications of Satisfiability Testing - SAT 2006 (A. Biere and C. P. Gomes, eds.), Springer, Berlin 2006, pp. 424-429.   DOI:10.1007/11814948\_38
  17. T. Toda and T. Soh: Implementing efficient all solutions {SAT} solvers. J. Experiment. Algorithm. 21 (2016), 1-44.   DOI:10.1145/2975585
  18. D. J. A. Welsh: Matroid Theory. Courier Corporation, 2010.   CrossRef