Cut Polytope

グラフ \(G\) の頂点集合を, 2つの共通部分の無い部分集合に分ける分け方から, 凸多面体 \(\mathrm {CUT}(G)\) を作ることができる。\(G\) の cut polytope と呼ばれるものである。

頂点の座標が \(0\) か \(1\) である \(0/1\)-polytope と呼ばれるものになっている。 Ziegler の \(0/1\)-polytope の解説 [Zie00] でも取り上げられている。

• \(0/1\)-polytope

文献としては, Deza と Laurent の本 [DL97] をとりあえず見るべきだろうか。彼らによると以下のような応用があるらしい。

1. functional analysis (\(\ell _1\)- and \(L_1\)-metrics),
2. combinatorial optimization,
3. quantum mechanics,
4. probability,
5. statistical data analysis,
6. \(\cdots \)

Avis と Imai と Ito の [AII08] でも quantum information processing などに現れると書いてある。その論文に書いてあるように, cut polytope は, 今まで主に完全グラフの場合について調べられてきたようである。 一般のグラフについては, まだあまり分かっていないようなので, 面白そうである。

そこでも参考文献に挙げられているが, 一般のグラフの cut polytope を調べたものとして, Barahona と Mahjoub の [BM86] がある。そこには, いくつかの facet (最高次元の面) を定義する超平面の見つけ方が書かれている。ただし, 辺のcollapse (ある辺を縮めて二つの頂点を同一視しその結果できる多重辺を一本にする操作) で \(K_5\) にならないグラフについてであるが。

一般化としては, matroid に対する cycle polytope というものがある。 Römer と Madani の [RM] によると Barahona と Grötschel により [BG86] で導入された。

• cycle polytope

Coons ら [Coo+23] は simplicial complex に対する一般化を導入している。その元になっているのは, グラフの場合の correlation polytope と cut polytope の関係である。

• correlation polytope
• generalized cut polytope for simplicial complex

Sturmfels と Sullivant [SS08] は, グラフの cut から toric variety を作ることを考えている。

• cut ideal
• cut algebra

Cut ideal は, cut で生成された多項式環の ideal として定義される。 その商環が cut algebra である。Cut algebra は, [RS18] などで調べられている。

Ohsugi は, Sturmfels と Sullivant の定義した cut polytope の normality について [Ohs10] で調べている。

References

[AII08]

David Avis, Hiroshi Imai, and Tsuyoshi Ito. “Generating facets for the cut polytope of a graph by triangular elimination”. In: Math. Program. 112.2, Ser. A (2008), pp. 303–325. arXiv: math/0601375. url: http://dx.doi.org/10.1007/s10107-006-0018-z.

[BG86]

F. Barahona and M. Grötschel. “On the cycle polytope of a binary matroid”. In: J. Combin. Theory Ser. B 40.1 (1986), pp. 40–62. url: https://doi.org/10.1016/0095-8956(86)90063-8.

[BM86]

Francisco Barahona and Ali Ridha Mahjoub. “On the cut polytope”. In: Math. Programming 36.2 (1986), pp. 157–173. url: http://dx.doi.org/10.1007/BF02592023.

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

[DL97]

Michel Marie Deza and Monique Laurent. Geometry of cuts and metrics. Vol. 15. Algorithms and Combinatorics. Berlin: Springer-Verlag, 1997, pp. xii+587. isbn: 3-540-61611-X.

[Ohs10]

Hidefumi Ohsugi. “Normality of cut polytopes of graphs in a minor closed property”. In: Discrete Math. 310.6-7 (2010), pp. 1160–1166. arXiv: 0906 . 5303. url: http://dx.doi.org/10.1016/j.disc.2009.11.012.

[RM]

Tim Römer and Sara Saeedi Madani. Cycle algebras and polytopes of matroids. arXiv: 2105.00185.

[RS18]

Tim Römer and Sara Saeedi Madani. “Retracts and algebraic properties of cut algebras”. In: European J. Combin. 69 (2018), pp. 214–236. arXiv: 1608.04973. url: https://doi.org/10.1016/j.ejc.2017.11.002.

[SS08]

Bernd Sturmfels and Seth Sullivant. “Toric geometry of cuts and splits”. In: Michigan Math. J. 57 (2008). Special volume in honor of Melvin Hochster, pp. 689–709. arXiv: math / 0606683. url: http://dx.doi.org/10.1307/mmj/1220879432.

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