中间层图 -- 来自 Wolfram MathWorld

阶数为的中间层图是顶点传递图，其顶点集由长度为且恰好有或个条目等于 1 的所有位串组成，当且仅当两个顶点对应的位串恰好在一个位上不同时，它们之间存在一条边 (Mütze 2016)。中间层图对于每个都具有哈密顿环的猜想（现已证明）被称为中间层猜想。

中间层图对应于二分 Kneser 图。它是最稀疏的二分 Kneser 图，因此在某种意义上是证明此类图族哈密顿性的最难障碍 (Mütze 2016)。特殊情况总结在下表中。

中间层图是二分的、连通的，并且有个顶点 (Mütze 2016)。

阶数为的中间层图在 Wolfram 语言中实现为GraphData["MiddleLayer", n].

参考文献

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.

中间层图