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)

Request Permissions   Purchase Content 
 

 

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?)


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