Geodesic
Construction methods for gaussoids
Kybernetika, Tome 56 (2020) no. 6, pp. 1045-1062
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2020-6-1045
Classification : 05B35, 05B99, 60E05
Keywords: gaussoid; conditional independence; normal distribution; cube; minor 
@article{10_14736_kyb_2020_6_1045,
     author = {Boege, Tobias and Kahle, Thomas},
     title = {Construction methods for gaussoids},
     journal = {Kybernetika},
     pages = {1045--1062},
     year = {2020},
     volume = {56},
     number = {6},
     doi = {10.14736/kyb-2020-6-1045},
     mrnumber = {4199902},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2020-6-1045/}
}
TY  - JOUR
AU  - Boege, Tobias
AU  - Kahle, Thomas
TI  - Construction methods for gaussoids
JO  - Kybernetika
PY  - 2020
SP  - 1045
EP  - 1062
VL  - 56
IS  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2020-6-1045/
DO  - 10.14736/kyb-2020-6-1045
LA  - en
ID  - 10_14736_kyb_2020_6_1045
ER  - 
%0 Journal Article
%A Boege, Tobias
%A Kahle, Thomas
%T Construction methods for gaussoids
%J Kybernetika
%D 2020
%P 1045-1062
%V 56
%N 6
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2020-6-1045/
%R 10.14736/kyb-2020-6-1045
%G en
%F 10_14736_kyb_2020_6_1045
Boege, Tobias; Kahle, Thomas. Construction methods for gaussoids. Kybernetika, Tome 56 (2020) no. 6, pp. 1045-1062. doi: 10.14736/kyb-2020-6-1045

[1] Boege, T., D'Ali, A., Kahle, T., Sturmfels, B.: The geometry of Gaussoids. Found. Comput. Math. 19 (2019), 4, 775-812. | DOI | MR

[2] Godsil, Ch., Royle, G.: Algebraic Graph Theory. Springer, Graduate Texts in Mathematics 207, 2001. | MR | Zbl

[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 | MR

[4] Klein, F.: Elementary Mathematics from a Higher Standpoint, II: Geometry, volume 2. Springer, 2016. | DOI | MR

[5] Lněnička, R., Matúš, F.: On Gaussian conditional independence structures. Kybernetika 43 (2007), 3, 327-342. | MR

[6] Lovász, L.: Three short proofs in graph theory. J. Combinat. Theory, Series B 19 (1975), 3, 269-271. | DOI | MR

[7] Matúš, F.: Conditional independence structures examined via minors. Ann. Math. Artif. Intell. 21 (1997), 1, 99-130. | DOI | MR

[8] Nelson, P.: Almost all matroids are non-representable. Bull. London Math. Soc. 50 (2018), 245-248. | DOI | MR

[9] Inc., OEIS Foundation: The On-Line Encyclopedia of Integer Sequences. Towards Math. Assist., 130-130. | DOI

[10] Piff, M. J., Welsh, D. J. A.: On the number of combinatorial geometries. Bull. London Math. Soc. 3 (1071), 1, 55-56. | DOI | MR

[11] Sadeghi, K.: Faithfulness of probability distributions and graphs. J. Machine Learning Res. 18 (2017), 1, 5429-5457. | MR

[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 | MR

[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 | MR

[17] Toda, T., Soh, T.: Implementing efficient all solutions SAT solvers. J. Experiment. Algorithm. 21 (2016), 1-44. | DOI | MR

[18] Welsh, D. J. A.: Matroid Theory. Courier Corporation, 2010. | MR

Cité par Sources :