TOPICS
Search

Middle Layer Graph

MiddleLayerGraphs

The middle layer graph of order n is the vertex-transitive graph whose vertex set consists of all bitstrings of length 2n+1 that have exactly n or n+1 entries equal to 1, with an edge between any two vertices for which the corresponding bitstrings differ in exactly one bit (Mütze 2016). The conjecture (now proved) that the middle layer graph has a Hamilton cycle for every n>=1 is known as the middle levels conjecture.

The middle layer graph corresponds to the bipartite Kneser graph H(2n+1,n). It is the sparsest bipartite Kneser graph and so is in some sense is the hardest obstacle in proving Hamiltonicity for this family of graphs (Mütze 2016). Special cases are summarized in the table below.

nn-middle layer graph
1cycle graph C_6
2Desargues graph GP(10,3)
3Danzer graph

The middle layer graph is bipartite, connected, and has (2n+1; n)+(2n+1; n+1) vertices (Mütze 2016).

The middle layer graph of order n is implemented in the Wolfram Language as GraphData[{"MiddleLayer", n}].

See also

Bipartite Kneser Graph, Danzer Graph, Desargues Graph, Middle Levels Conjecture, Nonhamiltonian Vertex-Transitive Graph

Explore with Wolfram|Alpha

References

Knuth, D. Exercise 56, §7.2.1.3 in The Art of Computer Programming, Vol. 4A. Reading, MA: Addison-Wesley, 2011.Mütze, T. "Proof of the Middle Levels Conjecture." Proc. Lond. Math. Soc. 112, 677-713, 2016.Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Soc. 74, 583-592, 2024.

Cite this as:

Weisstein, Eric W. "Middle Layer Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MiddleLayerGraph.html

Subject classifications