date	page
Dec 04	frieze_pattern.html
Dec 05	manifold_with_bounda...
Dec 05	multivariable.html
Dec 06	exact_category_gener...
Dec 07	dagger_category.html
Dec 07	category_with_someth...
Dec 07	category_with_dualit...
Dec 07	bilinear.html
Dec 08	cluster_algebra.html
Dec 08	total_positivity.htm...
Dec 09	graph_polytopes.html
Dec 10	topological_complexi...
Dec 10	Schwarz_genus.html
Dec 11	coarse_space.html
Dec 12	algebraic_constructi...
Dec 13	persons.html
Dec 14	pin_variations.html
Dec 15	triangulated_categor...
Dec 15	stable_infty-categor...
Dec 16	integrable_systems.h...
Dec 17	word_problem.html
Dec 18	configuration_space_...
Dec 19	reflection_group.htm...
Dec 19	Bott_periodicity.htm...
Dec 20	homology_operation.h...
Dec 21	abstract_polytope.ht...
Dec 21	associahedron.html
Dec 22	sphere_packing.html
Dec 23	toric.html
Dec 23	permutohedron.html

Kantorovich-Rubinstein polytope あるいは fundamental polytope

最適輸送問題との関連で, 有限距離空間から定義される多面体がある。 Vershik [Ver15] は, fundamental polytope と呼んでいるが, Jevtić, Jelić, Živaljević [JJŽ18; JTŽ21] は, Kantorovich-Rubinstein polytope と呼んでいる。

定義は, 簡単である。

Definition 1. Let \((X,d)\) be a finite metric space with \(n=|X|\). The vector space of all \(\R \)-valued functions on \(X\) is denoted by \(C(X)\). The subspace of all functions \(f\) with \(\sum _{x\in X} f(x)=0\) is denoted by \(C_0(X)\).

The fundamental polytope of \((X,d)\) is the convex hull \(R_{(X,d)}\) of \(\set {e_{x,y}}{x,y\in X, x\neq y}\) in \(C_0(X)\), where \[ e_{x,y} = \frac {\delta _x-\delta _y}{d(x,y)} \] and \(\delta _x\) is the function defined by \[ \delta _x(y) = \begin {cases} -\frac {1}{n}, & y\neq x \\ \frac {n-1}{n}, & y=x. \end {cases} \]

この定義を見れば分かるように, \(d\) は距離になっている必要はない。実際, Delucchi と Hoessly [DH20] は tree-like pseudometric に対する fundamental polytope の \(f\)-vector などを調べている。超平面配置の組合せ論に帰着できるようで, 興味深い。

Delucchi と Hoessly [DH20] では, その polar dual は Lipschitz poltyope と呼ばれている。

Lipschitz polytope

Gordon と Petrov の [GP17] や Celik, Jamneshan, Montúfar, Sturmfels, Venturello [Çel+21] にも書かれているが, Lipschitz polytope は, tropicalな意味でも polytope, つまり polytrope になっている。

polytrope

Gordon と Petrov は, [GP17] で “generic” な場合, つまり全ての面が単体になっている場合の \(f\)-vecotr を決定している。また, 距離が generic であることの特徴付けも得ている。

有限グラフ \(G\) が与えられたときに, \(G\) 辺の長さを \(1\) として頂点集合に最短の道の長さで距離を定めることができるが, その fundamental polytope は \(G\) の symmetric edge polytope と呼ばれる多面体になっている。辺に向きの付いたグラフの場合には, directed edge polytope という多面体ができる。

グラフからできる多面体

References

[Çel+21]: Türkü Özlüm Çelik, Asgar Jamneshan, Guido Montúfar, Bernd Sturmfels, and Lorenzo Venturello. “Wasserstein distance to independence models”. In: J. Symbolic Comput. 104 (2021), pp. 855–873. arXiv: 2003.06725. url: https://doi.org/10.1016/j.jsc.2020.10.005.
[DH20]: Emanuele Delucchi and Linard Hoessly. “Fundamental polytopes of metric trees via parallel connections of matroids”. In: European J. Combin. 87 (2020), pp. 103098, 18. arXiv: 1612.05534. url: https://doi.org/10.1016/j.ejc.2020.103098.
[GP17]: J. Gordon and F. Petrov. “Combinatorics of the Lipschitz polytope”. In: Arnold Math. J. 3.2 (2017), pp. 205–218. arXiv: 1608.06848. url: https://doi.org/10.1007/s40598-017-0063-0.
[JJŽ18]: Filip D. Jevtić, Marija Jelić, and Rade T. Živaljević. “Cyclohedron and Kantorovich-Rubinstein polytopes”. In: Arnold Math. J. 4.1 (2018), pp. 87–112. arXiv: 1703.06612. url: https://doi.org/10.1007/s40598-018-0083-4.
[JTŽ21]: Filip D. Jevtić, Marinko Timotijević, and Rade T. Živaljević. “Polytopal Bier spheres and Kantorovich-Rubinstein polytopes of weighted cycles”. In: Discrete Comput. Geom. 65.4 (2021), pp. 1275–1286. arXiv: 1812.00397. url: https://doi.org/10.1007/s00454-019-00151-5.
[Ver15]: A. M. Vershik. “Classification of finite metric spaces and combinatorics of convex polytopes”. In: Arnold Math. J. 1.1 (2015), pp. 75–81. arXiv: 1504.03601. url: https://doi.org/10.1007/s40598-014-0005-z.