| Title:
|
Construction methods for gaussoids (English) |
| Author:
|
Boege, Tobias |
| Author:
|
Kahle, Thomas |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
56 |
| Issue:
|
6 |
| Year:
|
2020 |
| Pages:
|
1045-1062 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
gaussoid |
| Keyword:
|
conditional independence |
| Keyword:
|
normal distribution |
| Keyword:
|
cube |
| Keyword:
|
minor |
| MSC:
|
05B35 |
| MSC:
|
05B99 |
| MSC:
|
60E05 |
| idMR:
|
MR4199902 |
| DOI:
|
10.14736/kyb-2020-6-1045 |
| . |
| Date available:
|
2021-01-08T08:32:38Z |
| Last updated:
|
2021-03-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/148498 |
| . |
| Reference:
|
[1] Boege, T., D'Ali, A., Kahle, T., Sturmfels, B.: The geometry of Gaussoids..Found. Comput. Math. 19 (2019), 4, 775-812. MR 3989713, 10.1007/s10208-018-9396-x |
| Reference:
|
[2] Godsil, Ch., Royle, G.: Algebraic Graph Theory..Springer, Graduate Texts in Mathematics 207, 2001. Zbl 0968.05002, MR 1829620 |
| Reference:
|
[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. MR 2396350, 10.1017/S0963548307008838 |
| Reference:
|
[4] Klein, F.: Elementary Mathematics from a Higher Standpoint, II: Geometry, volume 2..Springer, 2016. MR 3495524, 10.1007/978-3-662-49445-5 |
| Reference:
|
[5] Lněnička, R., Matúš, F.: On Gaussian conditional independence structures..Kybernetika 43 (2007), 3, 327-342. MR 2362722 |
| Reference:
|
[6] Lovász, L.: Three short proofs in graph theory..J. Combinat. Theory, Series B 19 (1975), 3, 269-271. MR 0396344, 10.1016/0095-8956(75)90089-1 |
| Reference:
|
[7] Matúš, F.: Conditional independence structures examined via minors..Ann. Math. Artif. Intell. 21 (1997), 1, 99-130. MR 1479010, 10.1023/A:1018957117081 |
| Reference:
|
[8] Nelson, P.: Almost all matroids are non-representable..Bull. London Math. Soc. 50 (2018), 245-248. MR 3830117, 10.1112/blms.12141 |
| Reference:
|
[9] Inc., OEIS Foundation: The On-Line Encyclopedia of Integer Sequences..Towards Math. Assist., 130-130. 10.1515/9780691197944-009 |
| Reference:
|
[10] Piff, M. J., Welsh, D. J. A.: On the number of combinatorial geometries..Bull. London Math. Soc. 3 (1071), 1, 55-56. MR 0282867, 10.1112/blms/3.1.55 |
| Reference:
|
[11] Sadeghi, K.: Faithfulness of probability distributions and graphs..J. Machine Learning Res. 18 (2017), 1, 5429-5457. MR 3763782 |
| Reference:
|
[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. |
| Reference:
|
[13] Sörensson, N., Een, N.: MiniSat v1.13 - A SAT Solver with Conflict-Clause Minimization, 2005.. |
| Reference:
|
[14] Sullivant, S.: Gaussian conditional independence relations have no finite complete characterization..J. Pure Appl. Algebra 213 (2009), 8, 1502-1506. MR 2517987, 10.1016/j.jpaa.2008.11.026 |
| Reference:
|
[15] Developers, The Sage: SageMath, the Sage Mathematics Software System (Version 8.0), 2017.. |
| Reference:
|
[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. MR 2265424, 10.1007/11814948_38 |
| Reference:
|
[17] Toda, T., Soh, T.: Implementing efficient all solutions SAT solvers..J. Experiment. Algorithm. 21 (2016), 1-44. MR 3568340, 10.1145/2975585 |
| Reference:
|
[18] Welsh, D. J. A.: Matroid Theory..Courier Corporation, 2010. MR 0427112 |
| . |
