×
Martínez-Sandoval, Leonardo; Padrol, Arnau

The convex dimension of hypergraphs and the hypersimplicial Van Kampen-Flores theorem. (English) Zbl 1466.05153

J. Comb. Theory, Ser. B 149, 23-51 (2021).
Summary: The convex dimension of a \(k\)-uniform hypergraph is the smallest dimension \(d\) for which there is an injective mapping of its vertices into \(\mathbb{R}^d\) such that the set of \(k\)-barycenters of all hyperedges is in convex position.
We completely determine the convex dimension of complete \(k\)-uniform hypergraphs, which settles an open question by N. Halman et al. [Discrete Appl. Math. 155, No. 11, 1373–1383 (2007; Zbl 1278.90339)], who solved the problem for complete graphs. We also provide lower and upper bounds for the extremal problem of estimating the maximal number of hyperedges of \(k\)-uniform hypergraphs on \(n\) vertices with convex dimension \(d\).
To prove these results, we restate them in terms of affine projections that preserve the vertices of the hypersimplex. More generally, we provide a full characterization of the projections that preserve its \(i\)-dimensional skeleton. In particular, we obtain a hypersimplicial generalization of the linear van Kampen-Flores theorem: for each \(n\), \(k\) and \(i\) we determine onto which dimensions can the \((n\), \(k)\)-hypersimplex be linearly projected while preserving its \(i\)-skeleton.
Our results have direct interpretations in terms of \(k\)-sets and \((i, j)\)-partitions, and are closely related to the problem of finding large convexly independent subsets in Minkowski sums of \(k\) point sets.

Cited in 1 Document

MSC:

05C65 Hypergraphs
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
90C25 Convex programming

Keywords:

convex embeddings of hypergraphs; hypersimplices; dimensional ambiguity of polytope skeleta; Van Kampen-Flores theorem; \(k\)-sets; Minkowski sums

Citations:

Zbl 1278.90339
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Adiprasito, K. A.; Sanyal, R., Relative Stanley-Reisner theory and upper bound theorems for Minkowski sums, Publ. Math. Inst. Hautes Études Sci., 124, 99-163 (2016) · Zbl 1368.52016
[2] Andrzejak, A., On k-sets and their generalizations (2000), Swiss Federal Institute of Technology: Swiss Federal Institute of Technology Zurich (ETH Zurich), Ph.D. thesis
[3] Andrzejak, A.; Welzl, E., In between k-sets, j-facets, and i-faces: \((i, j)\)-partitions, Discrete Comput. Geom., 29, 1, 105-131 (2003) · Zbl 1024.52011
[4] Bílka, O.; Buchin, K.; Fulek, R.; Kiyomi, M.; Okamoto, Y.; Tanigawa, S.-i.; Tóth, C. D., A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets, Electron. J. Comb., 17, Article #N35 pp. (2010) · Zbl 1205.52010
[5] de Caen, D., Extension of a theorem of Moon and Moser on complete subgraphs, Ars Comb., 16, 5-10 (1983) · Zbl 0532.05037
[6] Edelsbrunner, H.; Valtr, P.; Welzl, E., Cutting dense point sets in half, Discrete Comput. Geom., 17, 3, 243-255 (1997) · Zbl 0870.68153
[7] Eisenbrand, F.; Pach, J.; Rothvoß, T.; Sopher, N. B., Convexly independent subsets of the Minkowski sum of planar point sets, Electron. J. Comb., 15, 1 (2008), #N8 · Zbl 1160.52013
[8] Ewald, G., Combinatorial Convexity and Algebraic Geometry, Graduate Texts in Mathematics, vol. 168 (1996), Springer-Verlag: Springer-Verlag New York · Zbl 0869.52001
[9] Flores, A., Über n-dimensionale Komplexe, die im \(R_{2 n + 1}\) absolut selbstverschlungen sind, Erg. Math. Kolloquium Wien, 6, 4-6 (1935) · Zbl 0011.03804
[10] Galashin, P., Plabic graphs and zonotopal tilings, Proc. Lond. Math. Soc. (3), 117, 4, 661-681 (2018) · Zbl 1406.52039
[11] García-Marco, I.; Knauer, K., Drawing graphs with vertices and edges in convex position, Comput. Geom., 58, 25-33 (2016) · Zbl 1350.05107
[12] Grande, F.; Padrol, A.; Sanyal, R., Extension complexity and realization spaces of hypersimplices, Discrete Comput. Geom., 59, 3, 621-642 (2018) · Zbl 1387.52042
[13] Grünbaum, B., Convex Polytopes, Graduate Texts in Mathematics, vol. 221 (2003), Springer-Verlag: Springer-Verlag New York, prepared and with a preface by Volker Kaibel, Victor Klee and Günter M. Ziegler · Zbl 1033.52001
[14] Halman, N.; Onn, S.; Rothblum, U. G., The convex dimension of a graph, Discrete Appl. Math., 155, 11, 1373-1383 (2007) · Zbl 1278.90339
[15] Joswig, M.; Ziegler, G. M., Neighborly cubical polytopes, Discrete Comput. Geom., 24, 325-344 (2000), The Branko Grünbaum birthday issue · Zbl 1066.52012
[16] Matoušek, J., Lectures on Discrete Geometry, Graduate Texts in Mathematics, vol. 212 (2002), Springer-Verlag: Springer-Verlag New York · Zbl 0999.52006
[17] Matschke, B.; Pfeifle, J.; Pilaud, V., Prodsimplicial-neighborly polytopes, Discrete Comput. Geom., 46, 1, 100-131 (2011) · Zbl 1223.52005
[18] Nill, B.; Padrol, A., The degree of point configurations: Ehrhart theory, Tverberg points and almost neighborly polytopes, Eur. J. Comb., 50, 159-179 (2015) · Zbl 1323.52007
[19] Oh, S.; Postnikov, A.; Speyer, D. E., Weak separation and plabic graphs, Proc. Lond. Math. Soc. (3), 110, 3, 721-754 (2015) · Zbl 1309.05182
[20] Ohsugi, H.; Hibi, T., Normal polytopes arising from finite graphs, J. Algebra, 207, 2, 409-426 (1998) · Zbl 0926.52017
[21] Olarte, J. A.; Santos, F., Hypersimplicial subdivisions (2019), preprint
[22] Onn, S., Convex matroid optimization, SIAM J. Discrete Math., 17, 2, 249-253 (2003) · Zbl 1056.90121
[23] Onn, S.; Rothblum, U. G., Convex combinatorial optimization, Discrete Comput. Geom., 32, 4, 549-566 (2004) · Zbl 1179.90289
[24] Pach, J.; Sharir, M., On the number of incidences between points and curves, Comb. Probab. Comput., 7, 1, 121-127 (1998) · Zbl 0901.52016
[25] Postnikov, A., Total positivity, Grassmannians, and networks (2006), preprint
[26] Postnikov, A., Positive Grassmannian and polyhedral subdivisions, (Sirakov, B.; de Souza, P. N.; Viana, M., Proceedings of the International Congress of Mathematicians 2018. Proceedings of the International Congress of Mathematicians 2018, Rio de Janeiro, Brazil, August 1-9, 2018, vol. 3 (2019), World Scientific: World Scientific Hackensack, NJ), 3167-3196 · Zbl 1437.00044
[27] Rörig, T.; Sanyal, R., Non-projectability of polytope skeleta, Adv. Math., 229, 1, 79-101 (2012) · Zbl 1242.52017
[28] Sanyal, R., Topological obstructions for vertex numbers of Minkowski sums, J. Comb. Theory, Ser. A, 116, 1, 168-179 (2009) · Zbl 1166.52011
[29] Sanyal, R.; Ziegler, G. M., Construction and analysis of projected deformed products, Discrete Comput. Geom., 43, 2, 412-435 (2010) · Zbl 1192.52019
[30] Sharir, M., An improved bound for k-sets in four dimensions, Comb. Probab. Comput., 20, 1, 119-129 (2011) · Zbl 1211.68475
[31] Sharir, M.; Smorodinsky, S.; Tardos, G., An improved bound for k-sets in three dimensions, ACM Symposium on Computational Geometry (Hong Kong, 2000). ACM Symposium on Computational Geometry (Hong Kong, 2000), Discrete Comput. Geom., 26, 2, 195-204 (2001) · Zbl 0988.52034
[32] Shephard, G. C., Neighbourliness and Radon’s theorem, Mathematika, 16, 2, 273-275 (1969) · Zbl 0185.25801
[33] Skomra, M.; Thomassé, S., Convexly independent subsets of Minkowski sums of convex polygons (2019), preprint
[34] Swanepoel, K. J.; Valtr, P., Large convexly independent subsets of Minkowski sums, Electron. J. Comb., 17, Article #R146 pp. (2010) · Zbl 1205.52011
[35] Tiwary, H. R., On the largest convex subsets in Minkowski sums, Inf. Process. Lett., 114, 8, 405-407 (2014) · Zbl 1296.68105
[36] van Kampen, E. R., Komplexe in euklidischen Räumen, Abh. Math. Semin. Univ. Hamb., 9, 72-78 (1932) · JFM 58.0615.02
[37] Villarreal, R. H., On the equations of the edge cone of a graph and some applications, Manuscr. Math., 97, 3, 309-317 (1998) · Zbl 0920.13015
[38] Wagner, U., k-sets and k-facets, (Surveys on Discrete and Computational Geometry. Surveys on Discrete and Computational Geometry, Contemp. Math., vol. 453 (2008), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 443-513 · Zbl 1149.52012
[39] Weibel, C., Maximal f-vectors of Minkowski sums of large numbers of polytopes, Discrete Comput. Geom., 47, 3, 519-537 (2012) · Zbl 1243.52007
[40] Ziegler, G. M., Lectures on Polytopes, Grad. Texts in Math., vol. 152 (1995), Springer-Verlag: Springer-Verlag New York · Zbl 0823.52002
[41] Ziegler, G. M., Projected products of polygons, Electron. Res. Announc. Am. Math. Soc., 10, 122-134 (2004) · Zbl 1068.52014
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.