Your language?
May, 2018
Sun Mon Tue Wed Thu Fri Sat
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31

多面体のグラフ

頂点 すと グラフ ができる これを グラフ いう

けないが , その グラフ なら けないこともない 1 3 Euclid めるからである それを polymake という ソフト うことを えたのが Joswig らの [ GJRW10 ] ある

, 3 ならその グラフ (planar) であるので , らないような ける , 3 グラフ として , 3 グラフ けられる これは Steinitz として られ ているものである には d グラフ d であることが Balinski として られている これらについては , Ziegler [ Zie95 ] しい

  • Steinitz
  • Balinski

Balinski Ziegler にある

Athanasiadis [ Ath09 ] , k ( k + 1) による がりを わす グラフ , Balinski している

ではない する Steinitz として , である ような 3 のいくつかの class についての , Eppstein Mumford [ EM14 ] がある

Pseudomanifold する Balinski , Barnette [ Bar73 ] により れている

Pfeifle Pilaud Santos [ PPS12 ] , ある ( d ) グラフ にな てい るような グラフ , polytopal ( d -polytopal) んでいる らは , グラフ polytopality , グラフ との 調 べている

  • polytopal graph

もちろん , には グラフ だけでは ての ることはできない グラ から face lattice まるものとして simple polytope がある

  • simple polytope
  • simple polytope face lattice はその graph から まる [ BML87 Kal88 ]

この , graph, そしてより skeleton から 再構 する について Bayer survey [ Bay ] がある そこでは , Kalai [ Kal97 ] るように いて ある

グラフ については Hirsch conjecture という がある Razborov この によると , Hirsch conjecture convex geometry fascinating open problem らしい

  • 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 でも にな ている

としては , pseudomanifold 1-skeleton グラフ 研究 があ Björner Vorwerk [ BV15 ] , そこに げられている ると よい

References

[Ath09]     Christos A. Athanasiadis. On the graph connectivity of skeleta of convex polytopes. Discrete Comput. Geom. , 42(2):155–165, 2009, arXiv:0801.0939 .

[Bar73]     David Barnette. Graph theorems for manifolds. Israel J. Math. , 16:62–72, 1973, http://dx.doi.org/10.1007/BF02761971 .

[Bay]     Margaret M. Bayer. Graphs, Skeleta and Reconstruction of Polytopes, arXiv:1710.00118 .

[BML87]     Roswitha Blind and Peter Mani-Levitska. Puzzles and polytope isomorphisms. Aequationes Math. , 34(2-3):287–297, 1987, http://dx.doi.org/10.1007/BF01830678 .

[BV15]     Anders Björner and Kathrin Vorwerk. On the connectivity of manifold graphs. Proc. Amer. Math. Soc. , 143(10):4123–4132, 2015, arXiv:1207.5381 .

[Dan63]     George B. Dantzig. Linear programming and extensions . Princeton University Press, Princeton, N.J., 1963.

[EM14]     David Eppstein and Elena Mumford. Steinitz theorems for simple orthogonal polyhedra. J. Comput. Geom. , 5(1):179–244, 2014, arXiv:0912.0537 .

[GJRW10]     Ewgenij Gawrilow, Michael Joswig, Thilo Rörig, and Nikolaus Witte. Drawing polytopal graphs with polymake . Comput. Vis. Sci. , 13(2):99–110, 2010, arXiv:0711.2397 .

[Kal88]     Gil Kalai. A simple way to tell a simple polytope from its graph. J. Combin. Theory Ser. A , 49(2):381–383, 1988, 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., pages 331–344. CRC, Boca Raton, FL, 1997.

[KK87]     Victor Klee and Peter Kleinschmidt. The d -step conjecture and its relatives. Math. Oper. Res. , 12(4):718–755, 1987, 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. Bull. Amer. Math. Soc. (N.S.) , 26(2):315–316, 1992, http://dx.doi.org/10.1090/S0273-0979-1992-00285-9 .

[KS10]     Edward D. Kim and Francisco Santos. An update on the Hirsch conjecture. Jahresber. Dtsch. Math.-Ver. , 112(2):73–98, 2010, arXiv:0907.1186 .

[PPS12]     Julian Pfeifle, Vincent Pilaud, and Francisco Santos. Polytopality and Cartesian products of graphs. Israel J. Math. , 192(1):121–141, 2012, arXiv:1009.1499 .

[San12]     Francisco Santos. A counterexample to the Hirsch conjecture. Ann. of Math. (2) , 176(1):383–412, 2012, arXiv:1006.2814 .

[Zie95]     Günter M. Ziegler. Lectures on polytopes , volume 152 of Graduate Texts in Mathematics . Springer-Verlag, New York, 1995, http://dx.doi.org/10.1007/978-1-4613-8431-1 .