Intersection patterns of finite sets and of convex sets

Frick, Florian

doi:10.1090/proc/13443

Intersection patterns of finite sets and of convex sets
HTML articles powered by AMS MathViewer

by Florian Frick PDF

Proc. Amer. Math. Soc. 145 (2017), 2827-2842 Request permission

Abstract:

The main result is a common generalization of results on lower bounds for the chromatic number of $r$-uniform hypergraphs and some of the major theorems in Tverberg-type theory, which is concerned with the intersection pattern of faces in a simplicial complex when continuously mapped to Euclidean space. As an application we get a simple proof of a generalization of a result of Kriz for certain parameters. This specializes to a short and simple proof of Kneser’s conjecture. Moreover, combining this result with recent work of Mabillard and Wagner we show that the existence of certain equivariant maps yields lower bounds for chromatic numbers. We obtain an essentially elementary proof of the result of Schrijver on the chromatic number of stable Kneser graphs. In fact, we show that every neighborly even-dimensional polytope yields a small induced subgraph of the Kneser graph of the same chromatic number. We furthermore use this geometric viewpoint to give tight lower bounds for the chromatic number of certain small subhypergraphs of Kneser hypergraphs.

References

MichałAdamaszek, Henry Adams, Florian Frick, Chris Peterson, and Corrine Previte-Johnson, Nerve complexes of circular arcs, Discrete Comput. Geom. 56 (2016), no. 2, 251–273. MR 3530967, DOI 10.1007/s00454-016-9803-5
Meysam Alishahi and Hossein Hajiabolhassan, On the chromatic number of general Kneser hypergraphs, J. Combin. Theory Ser. B 115 (2015), 186–209. MR 3383256, DOI 10.1016/j.jctb.2015.05.010
Noga Alon, Lech Drewnowski, and Tomasz Łuczak, Stable Kneser hypergraphs and ideals in $\Bbb N$ with the Nikodým property, Proc. Amer. Math. Soc. 137 (2009), no. 2, 467–471. MR 2448565, DOI 10.1090/S0002-9939-08-09588-9
N. Alon, P. Frankl, and L. Lovász, The chromatic number of Kneser hypergraphs, Trans. Amer. Math. Soc. 298 (1986), no. 1, 359–370. MR 857448, DOI 10.1090/S0002-9947-1986-0857448-8
S. Avvakumov, I. Mabillard, A. Skopenkov, and U. Wagner, Eliminating Higher-Multiplicity Intersections, III. Codimension 2, arXiv preprint arXiv:1511.03501 (2015).
E. G. Bajmóczy and I. Bárány, On a common generalization of Borsuk’s and Radon’s theorem, Acta Math. Acad. Sci. Hungar. 34 (1979), no. 3-4, 347–350 (1980). MR 565677, DOI 10.1007/BF01896131
I. Bárány, A short proof of Kneser’s conjecture, J. Combin. Theory Ser. A 25 (1978), no. 3, 325–326. MR 514626, DOI 10.1016/0097-3165(78)90023-7
I. Bárány, S. B. Shlosman, and A. Szűcs, On a topological generalization of a theorem of Tverberg, J. London Math. Soc. (2) 23 (1981), no. 1, 158–164. MR 602247, DOI 10.1112/jlms/s2-23.1.158
Pavle V. M. Blagojević, Florian Frick, and Günter M. Ziegler, Tverberg plus constraints, Bull. Lond. Math. Soc. 46 (2014), no. 5, 953–967. MR 3262197, DOI 10.1112/blms/bdu049
P. V. M. Blagojević, F. Frick, and G. M. Ziegler, Barycenters of Polytope Skeleta and Counterexamples to the Topological Tverberg Conjecture, via Constraints, arXiv preprint arXiv:1510.07984 (2015).
Pavle V. M. Blagojević, Benjamin Matschke, and Günter M. Ziegler, Optimal bounds for the colored Tverberg problem, J. Eur. Math. Soc. (JEMS) 17 (2015), no. 4, 739–754. MR 3336834, DOI 10.4171/JEMS/516
V. L. Dol′nikov, A combinatorial inequality, Sibirsk. Mat. Zh. 29 (1988), no. 3, 53–58, 219 (Russian); English transl., Siberian Math. J. 29 (1988), no. 3, 375–379 (1989). MR 953021, DOI 10.1007/BF00969645
Paul Erdős, Problems and results in combinatorial analysis, Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973) Atti dei Convegni Lincei, No. 17, Accad. Naz. Lincei, Rome, 1976, pp. 3–17 (English, with Italian summary). MR 0465878
F. Frick, Counterexamples to the topological Tverberg conjecture, Oberwolfach Reports 12 (2015), no. 1, 318–321.
David Gale, Neighborly and cyclic polytopes, Proc. Sympos. Pure Math., Vol. VII, Amer. Math. Soc., Providence, R.I., 1963, pp. 225–232. MR 0152944
Joshua E. Greene, A new short proof of Kneser’s conjecture, Amer. Math. Monthly 109 (2002), no. 10, 918–920. MR 1941810, DOI 10.2307/3072460
Mikhail Gromov, Singularities, expanders and topology of maps. Part 2: From combinatorics to topology via algebraic isoperimetry, Geom. Funct. Anal. 20 (2010), no. 2, 416–526. MR 2671284, DOI 10.1007/s00039-010-0073-8
M. Kneser, Aufgabe 360, Jahresbericht der Deutschen Mathematiker-Vereinigung 2 (1955), 27.
Igor Kříž, Equivariant cohomology and lower bounds for chromatic numbers, Trans. Amer. Math. Soc. 333 (1992), no. 2, 567–577. MR 1081939, DOI 10.1090/S0002-9947-1992-1081939-3
Igor Kriz, A correction to: “Equivariant cohomology and lower bounds for chromatic numbers” [Trans. Amer. Math. Soc. 333 (1992), no. 2, 567–577; MR1081939 (92m:05085)], Trans. Amer. Math. Soc. 352 (2000), no. 4, 1951–1952. MR 1665335, DOI 10.1090/S0002-9947-99-02494-0
Wolfgang Kühnel, Higher-dimensional analogues of Czászár’s torus, Results Math. 9 (1986), no. 1-2, 95–106. MR 841439, DOI 10.1007/BF03322352
Carsten E. M. C. Lange and Günter M. Ziegler, On generalized Kneser hypergraph colorings, J. Combin. Theory Ser. A 114 (2007), no. 1, 159–166. MR 2276965, DOI 10.1016/j.jcta.2006.02.003
L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978), no. 3, 319–324. MR 514625, DOI 10.1016/0097-3165(78)90022-5
I. Mabillard and U. Wagner, Eliminating Higher-Multiplicity Intersections, I. A Whitney Trick for Tverberg-Type Problems, arXiv preprint arXiv:1508.02349 (2015).
I. Mabillard and U. Wagner, Eliminating Higher-Multiplicity Intersections, II. The Deleted Product Criterion in the $r$-Metastable Range, arXiv preprint arXiv:1601.00876 (2016).
Jiří Matoušek, On the chromatic number of Kneser hypergraphs, Proc. Amer. Math. Soc. 130 (2002), no. 9, 2509–2514. MR 1900856, DOI 10.1090/S0002-9939-02-06371-2
Jiří Matoušek, A combinatorial proof of Kneser’s conjecture, Combinatorica 24 (2004), no. 1, 163–170. MR 2057690, DOI 10.1007/s00493-004-0011-1
Jiří Matoušek, Using the Borsuk-Ulam theorem, Universitext, Springer-Verlag, Berlin, 2003. Lectures on topological methods in combinatorics and geometry; Written in cooperation with Anders Björner and Günter M. Ziegler. MR 1988723
Frédéric Meunier, The chromatic number of almost stable Kneser hypergraphs, J. Combin. Theory Ser. A 118 (2011), no. 6, 1820–1828. MR 2793613, DOI 10.1016/j.jcta.2011.02.010
Steffen Oppermann and Hugh Thomas, Higher-dimensional cluster combinatorics and representation theory, J. Eur. Math. Soc. (JEMS) 14 (2012), no. 6, 1679–1737. MR 2984586, DOI 10.4171/JEMS/345
M. Özaydin, Equivariant maps for the symmetric group, Preprint, 17 pages, http://digital.library.wisc.edu/1793/63829, 1987.
Arnau Padrol, Many neighborly polytopes and oriented matroids, Discrete Comput. Geom. 50 (2013), no. 4, 865–902. MR 3138140, DOI 10.1007/s00454-013-9544-7
M. A. Perles and M. Sigron, Strong general position, arXiv preprint arXiv:1409.2899 (2014).
Johann Radon, Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten, Math. Ann. 83 (1921), no. 1-2, 113–115 (German). MR 1512002, DOI 10.1007/BF01464231
K. S. Sarkaria, A generalized Kneser conjecture, J. Combin. Theory Ser. B 49 (1990), no. 2, 236–240. MR 1064678, DOI 10.1016/0095-8956(90)90029-Y
K. S. Sarkaria, A generalized van Kampen-Flores theorem, Proc. Amer. Math. Soc. 111 (1991), no. 2, 559–565. MR 1004423, DOI 10.1090/S0002-9939-1991-1004423-6
A. Schrijver, Vertex-critical subgraphs of Kneser graphs, Nieuw Arch. Wisk. (3) 26 (1978), no. 3, 454–461. MR 512648
Ido Shemer, Neighborly polytopes, Israel J. Math. 43 (1982), no. 4, 291–314. MR 693351, DOI 10.1007/BF02761235
H. Tverberg, A generalization of Radon’s theorem, J. London Math. Soc. 41 (1966), 123–128. MR 187147, DOI 10.1112/jlms/s1-41.1.123
A. Yu. Volovikov, On the van Kampen-Flores theorem, Mat. Zametki 59 (1996), no. 5, 663–670, 797 (Russian, with Russian summary); English transl., Math. Notes 59 (1996), no. 5-6, 477–481. MR 1445447, DOI 10.1007/BF02308813
S. Vrećica and R. T. Živaljević, New cases of the colored Tverberg theorem, Jerusalem Combinatorics ’93 (H. Barcelo and G. Kalai, eds.), Contemp. Math., vol. 178, Amer. Math. Soc., 1994, pp. 325–325.
Günter M. Ziegler, Generalized Kneser coloring theorems with combinatorial proofs, Invent. Math. 147 (2002), no. 3, 671–691. MR 1893009, DOI 10.1007/s002220100188
Günter M. Ziegler, Erratum: “Generalized Kneser coloring theorems with combinatorial proofs” [Invent. Math. 147 (2002), no. 3, 671–691; MR1893009], Invent. Math. 163 (2006), no. 1, 227–228. MR 2208423, DOI 10.1007/s00222-005-0466-8
Rade T. Živaljević and Siniša T. Vrećica, The colored Tverberg’s problem and complexes of injective functions, J. Combin. Theory Ser. A 61 (1992), no. 2, 309–318. MR 1185000, DOI 10.1016/0097-3165(92)90028-S