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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.