Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Intersection patterns of finite sets and of convex sets


Author: Florian Frick
Journal: Proc. Amer. Math. Soc. 145 (2017), 2827-2842
MSC (2010): Primary 05C15, 52A35
DOI: https://doi.org/10.1090/proc/13443
Published electronically: December 30, 2016
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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, https://doi.org/10.1007/s00454-016-9803-5
  • [2] Meysam Alishahi and Hossein Hajiabolhassan, On the chromatic number of general Kneser hypergraphs, J. Combin. Theory Ser. B 115 (2015), 186-209. MR 3383256, https://doi.org/10.1016/j.jctb.2015.05.010
  • [3] Noga Alon, Lech Drewnowski, and Tomasz Łuczak, Stable Kneser hypergraphs and ideals in $ \mathbb{N}$ with the Nikodým property, Proc. Amer. Math. Soc. 137 (2009), no. 2, 467-471. MR 2448565, https://doi.org/10.1090/S0002-9939-08-09588-9
  • [4] 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, https://doi.org/10.2307/2000624
  • [5] S. Avvakumov, I. Mabillard, A. Skopenkov, and U. Wagner, Eliminating Higher-Multiplicity Intersections, III. Codimension 2, arXiv preprint arXiv:1511.03501 (2015).
  • [6] 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, https://doi.org/10.1007/BF01896131
  • [7] I. Bárány, A short proof of Kneser's conjecture, J. Combin. Theory Ser. A 25 (1978), no. 3, 325-326. MR 514626, https://doi.org/10.1016/0097-3165(78)90023-7
  • [8] 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, https://doi.org/10.1112/jlms/s2-23.1.158
  • [9] 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, https://doi.org/10.1112/blms/bdu049
  • [10] 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).
  • [11] 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, https://doi.org/10.4171/JEMS/516
  • [12] V. L. Dolnikov, 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, https://doi.org/10.1007/BF00969645
  • [13] Paul Erdős, Problems and results in combinatorial analysis, Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973) Accad. Naz. Lincei, Rome, 1976, pp. 3-17. Atti dei Convegni Lincei, No. 17 (English, with Italian summary). MR 0465878
  • [14] F. Frick, Counterexamples to the topological Tverberg conjecture, Oberwolfach Reports 12 (2015), no. 1, 318-321.
  • [15] David Gale, Neighborly and cyclic polytopes, Proc. Sympos. Pure Math., Vol. VII, Amer. Math. Soc., Providence, R.I., 1963, pp. 225-232. MR 0152944
  • [16] Joshua E. Greene, A new short proof of Kneser's conjecture, Amer. Math. Monthly 109 (2002), no. 10, 918-920. MR 1941810, https://doi.org/10.2307/3072460
  • [17] 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, https://doi.org/10.1007/s00039-010-0073-8
  • [18] M. Kneser, Aufgabe 360, Jahresbericht der Deutschen Mathematiker-Vereinigung 2 (1955), 27.
  • [19] Igor Kříž, Equivariant cohomology and lower bounds for chromatic numbers, Trans. Amer. Math. Soc. 333 (1992), no. 2, 567-577. MR 1081939, https://doi.org/10.2307/2154049
  • [20] 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, https://doi.org/10.1090/S0002-9947-99-02494-0
  • [21] Wolfgang Kühnel, Higher-dimensional analogues of Czászár's torus, Results Math. 9 (1986), no. 1-2, 95-106. MR 841439, https://doi.org/10.1007/BF03322352
  • [22] 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, https://doi.org/10.1016/j.jcta.2006.02.003
  • [23] L. Lovász, Kneser's conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978), no. 3, 319-324. MR 514625, https://doi.org/10.1016/0097-3165(78)90022-5
  • [24] I. Mabillard and U. Wagner, Eliminating Higher-Multiplicity Intersections, I. A Whitney Trick for Tverberg-Type Problems, arXiv preprint arXiv:1508.02349 (2015).
  • [25] 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).
  • [26] Jiří Matoušek, On the chromatic number of Kneser hypergraphs, Proc. Amer. Math. Soc. 130 (2002), no. 9, 2509-2514 (electronic). MR 1900856, https://doi.org/10.1090/S0002-9939-02-06371-2
  • [27] Jiří Matoušek, A combinatorial proof of Kneser's conjecture, Combinatorica 24 (2004), no. 1, 163-170. MR 2057690, https://doi.org/10.1007/s00493-004-0011-1
  • [28] 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
  • [29] 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, https://doi.org/10.1016/j.jcta.2011.02.010
  • [30] 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, https://doi.org/10.4171/JEMS/345
  • [31] M. Özaydin, Equivariant maps for the symmetric group, Preprint, 17 pages, http://digital.library.wisc.edu/1793/63829, 1987.
  • [32] Arnau Padrol, Many neighborly polytopes and oriented matroids, Discrete Comput. Geom. 50 (2013), no. 4, 865-902. MR 3138140, https://doi.org/10.1007/s00454-013-9544-7
  • [33] M. A. Perles and M. Sigron, Strong general position, arXiv preprint arXiv:1409.2899 (2014).
  • [34] Johann Radon, Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten, Math. Ann. 83 (1921), no. 1-2, 113-115 (German). MR 1512002, https://doi.org/10.1007/BF01464231
  • [35] K. S. Sarkaria, A generalized Kneser conjecture, J. Combin. Theory Ser. B 49 (1990), no. 2, 236-240. MR 1064678, https://doi.org/10.1016/0095-8956(90)90029-Y
  • [36] K. S. Sarkaria, A generalized van Kampen-Flores theorem, Proc. Amer. Math. Soc. 111 (1991), no. 2, 559-565. MR 1004423, https://doi.org/10.2307/2048349
  • [37] A. Schrijver, Vertex-critical subgraphs of Kneser graphs, Nieuw Arch. Wisk. (3) 26 (1978), no. 3, 454-461. MR 512648
  • [38] Ido Shemer, Neighborly polytopes, Israel J. Math. 43 (1982), no. 4, 291-314. MR 693351, https://doi.org/10.1007/BF02761235
  • [39] H. Tverberg, A generalization of Radon's theorem, J. London Math. Soc. 41 (1966), 123-128. MR 0187147
  • [40] 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, https://doi.org/10.1007/BF02308813
  • [41] 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.
  • [42] Günter M. Ziegler, Generalized Kneser coloring theorems with combinatorial proofs, Invent. Math. 147 (2002), no. 3, 671-691. MR 1893009, https://doi.org/10.1007/s002220100188
  • [43] Günter M. Ziegler, Erratum: ``Generalized Kneser coloring theorems with combinatorial proofs'' [Invent. Math. 147 (2002), no. 3, 671-691; MR 1893009], Invent. Math. 163 (2006), no. 1, 227-228. MR 2208423, https://doi.org/10.1007/s00222-005-0466-8
  • [44] 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, https://doi.org/10.1016/0097-3165(92)90028-S

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05C15, 52A35

Retrieve articles in all journals with MSC (2010): 05C15, 52A35


Additional Information

Florian Frick
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
Email: ff238@cornell.edu

DOI: https://doi.org/10.1090/proc/13443
Received by editor(s): July 9, 2016
Received by editor(s) in revised form: August 14, 2016, and August 15, 2016
Published electronically: December 30, 2016
Communicated by: Patricia L. Hersh
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society