Construction methods for gaussoids

Tobias Boege; Thomas Kahle

Kybernetika (2020)

  • Volume: 56, Issue: 6, page 1045-1062
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Boege, Tobias, and Kahle, Thomas. "Construction methods for gaussoids." Kybernetika 56.6 (2020): 1045-1062. <http://eudml.org/doc/297371>.

@article{Boege2020,
abstract = {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.},
author = {Boege, Tobias, Kahle, Thomas},
journal = {Kybernetika},
keywords = {gaussoid; conditional independence; normal distribution; cube; minor},
language = {eng},
number = {6},
pages = {1045-1062},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Construction methods for gaussoids},
url = {http://eudml.org/doc/297371},
volume = {56},
year = {2020},
}

TY - JOUR
AU - Boege, Tobias
AU - Kahle, Thomas
TI - Construction methods for gaussoids
JO - Kybernetika
PY - 2020
PB - Institute of Information Theory and Automation AS CR
VL - 56
IS - 6
SP - 1045
EP - 1062
AB - 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.
LA - eng
KW - gaussoid; conditional independence; normal distribution; cube; minor
UR - http://eudml.org/doc/297371
ER -

References

top
  1. Boege, T., D'Ali, A., Kahle, T., Sturmfels, B., 10.1007/s10208-018-9396-x, Found. Comput. Math. 19 (2019), 4, 775-812. MR3989713DOI10.1007/s10208-018-9396-x
  2. Godsil, Ch., Royle, G., Algebraic Graph Theory., Springer, Graduate Texts in Mathematics 207, 2001. Zbl0968.05002MR1829620
  3. Hemmecke, R., Morton, J., Shiu, A., Sturmfels, B., Wienand, O., 10.1017/S0963548307008838, Combinat. Probab. Comput. 17 (2008), 2, 239-257. MR2396350DOI10.1017/S0963548307008838
  4. Klein, F., 10.1007/978-3-662-49445-5, Springer, 2016. MR3495524DOI10.1007/978-3-662-49445-5
  5. Lněnička, R., Matúš, F., On Gaussian conditional independence structures., Kybernetika 43 (2007), 3, 327-342. MR2362722
  6. Lovász, L., 10.1016/0095-8956(75)90089-1, J. Combinat. Theory, Series B 19 (1975), 3, 269-271. MR0396344DOI10.1016/0095-8956(75)90089-1
  7. Matúš, F., 10.1023/A:1018957117081, Ann. Math. Artif. Intell. 21 (1997), 1, 99-130. MR1479010DOI10.1023/A:1018957117081
  8. Nelson, P., 10.1112/blms.12141, Bull. London Math. Soc. 50 (2018), 245-248. MR3830117DOI10.1112/blms.12141
  9. Inc., OEIS Foundation, 10.1515/9780691197944-009, Towards Math. Assist., 130-130. DOI10.1515/9780691197944-009
  10. Piff, M. J., Welsh, D. J. A., 10.1112/blms/3.1.55, Bull. London Math. Soc. 3 (1071), 1, 55-56. MR0282867DOI10.1112/blms/3.1.55
  11. Sadeghi, K., Faithfulness of probability distributions and graphs., J. Machine Learning Res. 18 (2017), 1, 5429-5457. MR3763782
  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., 10.1016/j.jpaa.2008.11.026, J. Pure Appl. Algebra 213 (2009), 8, 1502-1506. MR2517987DOI10.1016/j.jpaa.2008.11.026
  15. Developers, The Sage, SageMath, the Sage Mathematics Software System (Version 8.0), 2017. 
  16. Thurley, M., 10.1007/11814948_38, In: Theory and Applications of Satisfiability Testing - SAT 2006 (A. Biere and C. P. Gomes, eds.), Springer, Berlin 2006, pp. 424-429. MR2265424DOI10.1007/11814948_38
  17. Toda, T., Soh, T., 10.1145/2975585, J. Experiment. Algorithm. 21 (2016), 1-44. MR3568340DOI10.1145/2975585
  18. Welsh, D. J. A., Matroid Theory., Courier Corporation, 2010. MR0427112

NotesEmbed ?

top

You must be logged in to post comments.