You are here

Home » Content

On the Connectivity of Fiber Graphs

Journal Name:

  • Journal of Algebraic Statistics

Publication Year:

  • 2015

Key Words:

Author NameUniversity of Author
Abstract (2. Language): 
We consider the connectivity of ber graphs with respect to Grobner basis and Graver basis moves. First, we present a sequence of ber graphs using moves from a Grobner basis and prove that their edge-connectivity is lowest possible and can have an arbitrarily large distance from the minimal degree. We then show that graph-theoretic properties of ber graphs do not depend on the size of the right-hand side. This provides a counterexample to a conjecture of Engstrom on the node-connectivity of ber graphs. Our main result shows that the edge-connectivity in all ber graphs of this counterexample is best possible if we use moves from Graver basis instead.
Bookmark/Search this post with
FULL TEXT (PDF): 
PDF icon arastirmax-connectivity-fiber-graphs.pdf
  • 1
24
45
  • English

JEL Codes:

REFERENCES

References: 

[1] Anders Bjorner and Kathrin Vorwerk. Connectivity of chamber graphs of buildings and
related complexes. European Journal of Combinatorics, 31(8):2149{2160, 2010.
[2] Stephen Boyd, Persi Diaconis, and Lin Xiao. Fastest Mixing Markov Chain on a Graph.
SIAM Review, 46(4):667-689, 2004.
[3] Wen-Sz Chiue and Bih-Sheue Shieh. On connectivity of the Cartesian product of two
graphs. Applied Mathematics and Computation, 102(2-3):129{137, 1999.
REFERENCES 45
[4] Persi Diaconis and Bernd Sturmfels. Algebraic algorithms for sampling from conditional
distributions. The Annals of statistics, 26(1):363{397, 1998.
[5] Reinhard Diestel. Graph Theory. Springer-Verlag, New York, Berlin, Heidelberg, second
edition, 2000.
[6] Mathias Drton, Bernd Sturmfels, and Seth Sullivant. Lectures on algebraic statistics.
Birkauser Verlag AG, Basel, Boston, Berlin, 2009.
[7] Daniel R. Grayson and Michael E. Stillman. Macaulay2. A software system for research
in algebraic geometry. Available at http://math.uiuc.edu/Macaulay2/ .
[8] David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov Chains and Mixing
Times. American Mathematical Society, 2008.
[9] Liu Gui-Zhen. Proof of a conjecture on matroid base graphs. Science China Mathematics,
33(11):1329, 1990.
[10] Jesus A. De Loera, Raymond Hemmecke, and Matthias Koppe. Algebraic and Geometric
Ideas in the Theory of Discrete Optimization. MPS-SIAM Series on Optimization,
SIAM, 2013.
[11] Samu Potka. Higher connectivity of ber graphs of Grobner bases. Journal of Algebraic
Statistics, 4(1):93{107, September 2013.
[12] Bernd Sturmfels. Grobner bases and convex polytopes. American Mathematical Society,
1996.

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