多面体のグラフ

多面体の辺と頂点を取り出すと, グラフができる。 これを多面体のグラフという。

多面体は高次元の場合は絵に描けないが, そのグラフなら描けないこともない。 \(1\)次元の 単体的複体は, \(3\)次元 Euclid 空間に埋め込めるからである。それを実際に polymake というソフトで行うことを考えたのが, Joswig らの [Gaw+10] である。

更に, \(3\)次元多面体ならそのグラフは平面的 (planar) であるので, 辺が交わらないような絵が描ける。更に, 平面的で3連結な単純グラフとして, \(3\)次元多面体のグラフは特徴付けられる。 これは, Steinitz の定理として知られているものである。 一般には \(d\)次元多面体のグラフは\(d\)連結であることが, Balinski の定理として知られている。これらについては, Ziegler の本 [Zie95] が詳しい。

• Steinitz の定理
• Balinski の定理

凸ではない多面体に対する Steinitz の定理の類似として, 各辺が座標軸と平行であるような\(3\)次元の多面体のいくつかの class につい ての, Eppstein と Mumford [EM10] の結果がある。

Balinski の定理の証明としては, Pineda-Villavicencio によるもの [Pin21] もある。

Athanasiadis は [Ath09] で, \(k\)次元面の \((k+1)\)次元面による繋がりを表わすグラフを定義し, Balinski の定理の一般化を証明している。 Balinski の定理の高次元版としては, hypergraph を用いた Hathcock と Yu の [HY23] もある。

Pseudomanifold に対する Balinski の定理の一般化は, Barnette [Bar73] により得られている。 その改良版が Athanasiadis [Ath11] により得られている。

Pseudomanifold の \(1\)-skeleton の成すグラフの研究については, Björner と Vorwerk の [BV15] や, そこに挙げられている文献を見るとよい。

Pfeifle と Pilaud と Santos [PPS12] は,ある (\(d\)次元) 凸多面体のグラフになっているようなグラフを, polytopal (\(d\)-polytopal) 呼んでいる。 彼らは, グラフの polytopality と, グラフや多面体の操作との関係を調べている。

• polytopal graph

もちろん, 一般にはグラフだけでは多面体の全ての情報を得ることはできない。 グラフから face lattice が決まるものとして simple polytope がある。

• simple polytope
• simple polytope の face lattice は その graph から決まる。 [BM87; Kal88]

この, グラフ, そしてより高次元の skeleton から凸多面体を再構成する問題については, Bayer の survey [Bay18] がある。 そこでは, Kalai の [Kal97] を見るように書いてある。

• facet-ridge graph

一般化としては, Yang の [Yan] がある。Shellable simplicial sphere については, facet-ridge graph からその組み合せ論的構造, つまり face lattice が復元できることを示している。 Simplicial polytope の boundary は shellable であることが, Bruggesser と Mani [BM71] により示されているので, Yang の結果は simplicial polytope の face lattice が facet-ridge graph から復元できる, ということを言っている。

多面体のグラフについては, Hirsch conjecture という予想がある。

• Hirsch conjecture
• polynomial Hirsch conjecture

Kalai と Kleitman の [KK92] によると, 1957年に予想されたそうである。そこで参照されているのは, Dantzig の本 [Dan63] であるが。 Kalai と Kleitman は “recent survey” として Klee と Kleinschmidt の [KK87] を挙げているが, もっと新しいものとして Kim と Santos の survey [KS10] がある。どうやら, Santos [San12] により反例が発見されたようである。

Gil Kalai の blog でも 何度か話題になっている。

References

[Ath09]

Christos A. Athanasiadis. “On the graph connectivity of skeleta of convex polytopes”. In: Discrete Comput. Geom. 42.2 (2009), pp. 155–165. arXiv: 0801.0939. url: http://dx.doi.org/10.1007/s00454-009-9181-3.

[Ath11]

Christos A. Athanasiadis. “Some combinatorial properties of flag simplicial pseudomanifolds and spheres”. In: Ark. Mat. 49.1 (2011), pp. 17–29. arXiv: 0807.4369. url: http://dx.doi.org/10.1007/s11512-009-0106-4.

[Bar73]

David Barnette. “The triangulations of the \(3\)-sphere with up to \(8\) vertices”. In: J. Combinatorial Theory Ser. A 14 (1973), pp. 37–52.

[Bay18]

M. M. Bayer. “Graphs, skeleta and reconstruction of polytopes”. In: Acta Math. Hungar. 155.1 (2018), pp. 61–73. arXiv: 1710.00118. url: https://doi.org/10.1007/s10474-018-0804-0.

[BM71]

H. Bruggesser and P. Mani. “Shellable decompositions of cells and spheres”. In: Math. Scand. 29 (1971), 197–205 (1972). url: https://doi.org/10.7146/math.scand.a-11045.

[BM87]

Roswitha Blind and Peter Mani-Levitska. “Puzzles and polytope isomorphisms”. In: Aequationes Math. 34.2-3 (1987), pp. 287–297. url: http://dx.doi.org/10.1007/BF01830678.

[BV15]

Anders Björner and Kathrin Vorwerk. “On the connectivity of manifold graphs”. In: Proc. Amer. Math. Soc. 143.10 (2015), pp. 4123–4132. arXiv: 1207.5381. url: https://doi.org/10.1090/proc/12415.

[Dan63]

George B. Dantzig. Linear programming and extensions. Princeton University Press, Princeton, N.J., 1963, pp. xvi+625.

[EM10]

David Eppstein and Elena Mumford. “Steinitz theorems for orthogonal polyhedra”. In: Computational geometry (SCG’10). ACM, New York, 2010, pp. 429–438. arXiv: 0912.0537. url: https://doi.org/10.1145/1810959.1811030.

[Gaw+10]

Ewgenij Gawrilow, Michael Joswig, Thilo Rörig, and Nikolaus Witte. “Drawing polytopal graphs with polymake”. In: Comput. Vis. Sci. 13.2 (2010), pp. 99–110. arXiv: 0711.2397. url: https://doi.org/10.1007/s00791-009-0127-3.

[HY23]

Daniel Hathcock and Josephine Yu. “On the hypergraph connectivity of skeleta of polytopes”. In: Discrete Comput. Geom. 69.2 (2023), pp. 593–596. arXiv: 2010.05053. url: https://doi.org/10.1007/s00454-021-00362-9.

[Kal88]

Gil Kalai. “A simple way to tell a simple polytope from its graph”. In: J. Combin. Theory Ser. A 49.2 (1988), pp. 381–383. url: http://dx.doi.org/10.1016/0097-3165(88)90064-7.

[Kal97]

Gil Kalai. “Polytope skeletons and paths”. In: Handbook of discrete and computational geometry. CRC Press Ser. Discrete Math. Appl. CRC, Boca Raton, FL, 1997, pp. 331–344.

[KK87]

Victor Klee and Peter Kleinschmidt. “The \(d\)-step conjecture and its relatives”. In: Math. Oper. Res. 12.4 (1987), pp. 718–755. url: http://dx.doi.org/10.1287/moor.12.4.718.

[KK92]

Gil Kalai and Daniel J. Kleitman. “A quasi-polynomial bound for the diameter of graphs of polyhedra”. In: Bull. Amer. Math. Soc. (N.S.) 26.2 (1992), pp. 315–316. url: http://dx.doi.org/10.1090/S0273-0979-1992-00285-9.

[KS10]

Edward D. Kim and Francisco Santos. “An update on the Hirsch conjecture”. In: Jahresber. Dtsch. Math.-Ver. 112.2 (2010), pp. 73–98. arXiv: 0907.1186. url: https://doi.org/10.1365/s13291-010-0001-8.

[Pin21]

Guillermo Pineda-Villavicencio. “A new proof of Balinski’s theorem on the connectivity of polytopes”. In: Discrete Math. 344.7 (2021), Paper No. 112408, 3. arXiv: 2009.04658. url: https://doi.org/10.1016/j.disc.2021.112408.

[PPS12]

Julian Pfeifle, Vincent Pilaud, and Francisco Santos. “Polytopality and Cartesian products of graphs”. In: Israel J. Math. 192.1 (2012), pp. 121–141. arXiv: 1009.1499. url: http://dx.doi.org/10.1007/s11856-012-0049-5.

[San12]

Francisco Santos. “A counterexample to the Hirsch conjecture”. In: Ann. of Math. (2) 176.1 (2012), pp. 383–412. arXiv: 1006.2814. url: http://dx.doi.org/10.4007/annals.2012.176.1.7.

[Yan]

Yirong Yang. Reconstructing a Shellable Sphere from its Facet-Ridge Graph. arXiv: 2401.04220.

[Zie95]

Günter M. Ziegler. Lectures on polytopes. Vol. 152. Graduate Texts in Mathematics. Springer-Verlag, New York, 1995, pp. x+370. isbn: 0-387-94365-X. url: https://doi.org/10.1007/978-1-4613-8431-1.