0∕1-polytope

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

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

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

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

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

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

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

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.

[CG]

William Y. C. Chen and Peter L. Guo. Equivalence Classes of Full-Dimensional 0/1-Polytopes with Many Vertices. arXiv: 1101.0410.

[FK]

Yuri Faenza and Volker Kaibel. Extended Formulations for Packing and Partitioning Orbitopes. arXiv: 0806.0233.

[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.

[Grea]

R. M. Green. Homology representations arising from the half cube. arXiv: 0806.1503.

[Greb]

R. M. Green. Homology representations arising from the half cube, II. arXiv: 0812.1208.

[HL]

Huy Tài Hà and Kuei-Nuan Lin. Normal 0-1 polytopes. arXiv: 1309.4807.

[KP]

Volker Kaibel and Marc E. Pfetsch. Packing and Partitioning Orbitopes. arXiv: math/0603678.

[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.