0∕1-polytope

全ての頂点の座標が \(0\) か \(1\) である凸多面体, つまり単位立方体 \([0,1]^n\) の頂点を適当に選んでその convex hull を取ったものを, \(0/1\)-polytope という。

定義だけ見ると単純そうに思えるが, Ziegler の解説 [Zie00] を読んでみると, 次元が高くなると非常に複雑になることが分かる。Zong の [Zon05] にも解説がある。

各次元に何個あるか, というのは基本的な問題であるが, これまでは \(5\)次元まで (Aichholzer の [Aic00]) しか分っていなかった。 \(6\)次元では頂点 \(12\)個までのものしか分かっていなかったようであるが, Chen と Guo の [CG14] で \(12\)個より多いものについても分かったようである。

\(0/1\)-polytope の不変量として, Há と Lin が [HL15] で導入したものがある。彼等は, \(0/1\)-polytope に対し hypergraph を定義した。

例としては, グラフの cut polytope や orbitope や half cube などがある。

• cut polytope
• orbitope
• half cube
• traveling salesman polytope ([GP85; App+98])
• correlation polytope [Coo+23]

Orbitope は Kaibel と Pfetsch により [KP08] で定義された。更に [FK09] で調べられている。

Half cube は立方体の頂点を一つおきに取ってできる \(0/1\)-polytope である。 R.M. Green の [Gre09] で詳しく調べられている。その目的は, half cube の subcomplex として定義される CW複体のホモロジー上のtype \(D_n\) の Coxeter group の表現を 考えることである。[Gre10] でその表現について調べられている。

References

[Aic00]

Oswin Aichholzer. “Extremal properties of \(0/1\)-polytopes of dimension 5”. In: Polytopes—combinatorics and computation (Oberwolfach, 1997). Vol. 29. DMV Sem. Basel: Birkhäuser, 2000, pp. 111–130.

[App+98]

David Applegate, Robert Bixby, Vašek Chvátal, and William Cook. “On the solution of traveling salesman problems”. In: Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998). Extra Vol. III. 1998, pp. 645–656.

[CG14]

William Y. C. Chen and Peter L. Guo. “Equivalence classes of full-dimensional \(0/1\)-polytopes with many vertices”. In: Discrete Comput. Geom. 52.4 (2014), pp. 630–662. arXiv: 1101.0410. url: https://doi.org/10.1007/s00454-014-9630-5.

[Coo+23]

Jane Ivy Coons, Joseph Cummings, Benjamin Hollering, and Aida Maraj. “Generalized cut polytopes for binary hierarchical models”. In: Algebr. Stat. 14.1 (2023), pp. 17–36. arXiv: 2008.00043. url: https://doi.org/10.2140/astat.2023.14.17.

[FK09]

Yuri Faenza and Volker Kaibel. “Extended formulations for packing and partitioning orbitopes”. In: Math. Oper. Res. 34.3 (2009), pp. 686–697. arXiv: 0806.0233. url: https://doi.org/10.1287/moor.1090.0392.

[GP85]

M. Grötschel and M. W. Padberg. “Polyhedral theory”. In: The traveling salesman problem. Wiley-Intersci. Ser. Discrete Math. Wiley, Chichester, 1985, pp. 251–305.

[Gre09]

R. M. Green. “Homology representations arising from the half cube”. In: Adv. Math. 222.1 (2009), pp. 216–239. arXiv: 0806.1503. url: https://doi.org/10.1016/j.aim.2008.11.019.

[Gre10]

R. M. Green. “Homology representations arising from the half cube, II”. In: J. Combin. Theory Ser. A 117.8 (2010), pp. 1037–1048. arXiv: 0812.1208. url: https://doi.org/10.1016/j.jcta.2009.10.005.

[HL15]

Huy Tài Hà and Kuei-Nuan Lin. “Normal 0-1 polytopes”. In: SIAM J. Discrete Math. 29.1 (2015), pp. 210–223. arXiv: 1309.4807. url: https://doi.org/10.1137/130948240.

[KP08]

Volker Kaibel and Marc Pfetsch. “Packing and partitioning orbitopes”. In: Math. Program. 114.1, Ser. A (2008), pp. 1–36. arXiv: math/0603678. url: https://doi.org/10.1007/s10107-006-0081-5.

[Zie00]

Günter M. Ziegler. “Lectures on \(0/1\)-polytopes”. In: Polytopes—combinatorics and computation (Oberwolfach, 1997). Vol. 29. DMV Sem. Basel: Birkhäuser, 2000, pp. 1–41. arXiv: math/9909177.

[Zon05]

Chuanming Zong. “What is known about unit cubes”. In: Bull. Amer. Math. Soc. (N.S.) 42.2 (2005), 181–211 (electronic). url: http://dx.doi.org/10.1090/S0273-0979-05-01050-5.