You are here

Home » Content

Higher Connectivity of Fiber Graphs of Gröbner Bases

Journal Name:

  • Journal of Algebraic Statistics

Publication Year:

  • 2013

Keywords (Original Language):

Author NameUniversity of Author

AMS Codes:

Bookmark/Search this post with
Abstract (Original Language): 
Fiber graphs of Gröbner bases from contingency tables are important in statistical hypothesis testing, where one studies random walks on these graphs using the Metropolis-Hastings algorithm. The connectivity of the graphs has implications on how fast the algorithm converges. In this paper, we study a class of fiber graphs with elementary combinatorial techniques and provide results that support a recent conjecture of Engström: the connectivity is given by the minimum vertex degree.
FULL TEXT (PDF): 
PDF icon arastirmax-higher-connectivity-fiber-graphs-grobner-bases.pdf
  • 1
93
107
  • English

REFERENCES

References: 

[1] Anders Björner and Kathrin Vorwerk. Connectivity of chamber graphs of buildings
and related complexes. European J. Combin., 31(8):2149–2160, 2010.
[2] Persi Diaconis and Bernd Sturmfels. Algebraic algorithms for sampling from conditional
distributions. Ann. Statist., 26(1):363–397, 1998.
[3] Reinhard Diestel. Graph Theory. Graduate Texts in Mathematics. Springer, Heidelberg,
fourth edition, 2010.
[4] Mathias Drton, Bernd Sturmfels, and Seth Sullivant. Lectures on Algebraic Statistics.
Oberwolfach Seminars. Birkhäuser, Basel, 2009.
[5] Alexander Engström. Private communication, June 2012.
[6] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications.
Bull. Amer. Math. Soc. (N.S.), 43(4):439–561, 2006.
[7] Dénes Konig. Über Graphen und ihre Anwendung auf Determinantentheorie und
Mengenlehre. Math. Ann., 77(4):453–465, 1916.
[8] Gui Zhen Liu. Proof of a conjecture on matroid base graphs. Sci. China Ser. A,
33(11):1329–1337, 1990.
[9] Samu Potka. Connectivity. "Problem book for Sannäs workshop, August 9-10, 2012",
edited by Alexander Engström, 2012.
[10] Bernd Sturmfels. Gröbner Bases and Convex Polytopes. University Lecture Series.
American Mathematical Society, Providence, R.I., 1996.

Thank you for copying data from http://www.arastirmax.com