Article
Full entry |
PDF
(0.5 MB)
Feedback
PDF
(0.5 MB)
Feedback
Keywords:
gaussoid; conditional independence; normal distribution; cube; minor
gaussoid; conditional independence; normal distribution; cube; minor
Summary:
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.
References:
[1] Boege, T., D'Ali, A., Kahle, T., Sturmfels, B.: The geometry of Gaussoids. Found. Comput. Math. 19 (2019), 4, 775-812. DOI 10.1007/s10208-018-9396-x | MR 3989713
[2] Godsil, Ch., Royle, G.: Algebraic Graph Theory. Springer, Graduate Texts in Mathematics 207, 2001. MR 1829620 | Zbl 0968.05002
[3] Hemmecke, R., Morton, J., Shiu, A., Sturmfels, B., Wienand, O.: Three counter-examples on semi-graphoids. Combinat. Probab. Comput. 17 (2008), 2, 239-257. DOI 10.1017/S0963548307008838 | MR 2396350
[4] Klein, F.: Elementary Mathematics from a Higher Standpoint, II: Geometry, volume 2. Springer, 2016. DOI 10.1007/978-3-662-49445-5 | MR 3495524
[5] Lněnička, R., Matúš, F.: On Gaussian conditional independence structures. Kybernetika 43 (2007), 3, 327-342. MR 2362722
[6] Lovász, L.: Three short proofs in graph theory. J. Combinat. Theory, Series B 19 (1975), 3, 269-271. DOI 10.1016/0095-8956(75)90089-1 | MR 0396344
[7] Matúš, F.: Conditional independence structures examined via minors. Ann. Math. Artif. Intell. 21 (1997), 1, 99-130. DOI 10.1023/A:1018957117081 | MR 1479010
[8] Nelson, P.: Almost all matroids are non-representable. Bull. London Math. Soc. 50 (2018), 245-248. DOI 10.1112/blms.12141 | MR 3830117
[9] Inc., OEIS Foundation: The On-Line Encyclopedia of Integer Sequences. Towards Math. Assist., 130-130. DOI 10.1515/9780691197944-009
[10] Piff, M. J., Welsh, D. J. A.: On the number of combinatorial geometries. Bull. London Math. Soc. 3 (1071), 1, 55-56. DOI 10.1112/blms/3.1.55 | MR 0282867
[11] Sadeghi, K.: Faithfulness of probability distributions and graphs. J. Machine Learning Res. 18 (2017), 1, 5429-5457. MR 3763782
[12] Šimecek, P.: Classes of gaussian, discrete and binary representable independence models have no finite characterization. In: Proc. Prague Stochastics 2006, volume 400, pp. 622-631.
[13] Sörensson, N., Een, N.: MiniSat v1.13 - A SAT Solver with Conflict-Clause Minimization, 2005.
[14] Sullivant, S.: 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 | MR 2517987
[15] Developers, The Sage: SageMath, the Sage Mathematics Software System (Version 8.0), 2017.
[16] Thurley, M.: 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 | MR 2265424
[17] Toda, T., Soh, T.: Implementing efficient all solutions SAT solvers. J. Experiment. Algorithm. 21 (2016), 1-44. DOI 10.1145/2975585 | MR 3568340
[18] Welsh, D. J. A.: Matroid Theory. Courier Corporation, 2010. MR 0427112
Search
Partner of
