Intersection patterns of finite sets and of convex sets

DOI10.1090/PROC/13443zbMATH Open1360.05058arXiv1607.01003OpenAlexW2964015975MaRDI QIDQ2980804FDOQ2980804

Authors: Florian Frick 

Publication date: 4 May 2017

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1607.01003

Recommendations

• Chromatic numbers of stable Kneser hypergraphs via topological Tverberg-type theorems
• On the chromatic number of general Kneser hypergraphs
• On some topological and combinatorial lower bounds on the chromatic number of Kneser type hypergraphs
• scientific article; zbMATH DE number 4075095
• Topological lower bounds for the chromatic number: a hierarchy

zbMATH Keywords

chromatic number\(r\)-uniform hypergraphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Helly-type theorems and geometric transversal theory (52A35)

Cites Work

• Many neighborly polytopes and oriented matroids
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
• Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry
• Kneser's conjecture, chromatic number, and homotopy
• A short proof of Kneser's conjecture
• The Chromatic Number of Kneser Hypergraphs
• Title not available (Why is that?)
• A New Short Proof of Kneser's Conjecture
• Neighborly polytopes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nerve complexes of circular arcs
• On a common generalization of Borsuk's and Radon's theorem
• A Generalization of Radon's Theorem
• Higherdimensional analogues of Császár's torus
• Generalized Kneser coloring theorems with combinatorial proofs
• A combinatorical proof of Kneser's conjecture
• Equivariant Cohomology and Lower Bounds for Chromatic Numbers
• A generalized Kneser conjecture
• On a Topological Generalization of a Theorem of Tverberg
• The colored Tverberg's problem and complexes of injective functions
• Optimal bounds for the colored Tverberg problem
• On the chromatic number of general Kneser hypergraphs
• The chromatic number of almost stable Kneser hypergraphs
• A certain combinatorial inequality
• Stable Kneser hypergraphs and ideals in $\mathbb {N}$ with the Nikodým property
• Barycenters of polytope skeleta and counterexamples to the topological Tverberg conjecture, via constraints
• Eliminating higher-multiplicity intersections. III. Codimension 2
• Tverberg plus constraints
• Title not available (Why is that?)
• A Generalized van Kampen-Flores Theorem
• Higher-dimensional cluster combinatorics and representation theory
• On generalized Kneser hypergraph colorings
• On the chromatic number of Kneser hypergraphs
• On the van Kampen-Flores theorem
• Eliminating higher-multiplicity intersections. II. The deleted product criterion in the \(r\)-metastable range

Cited In (13)

• Intersection patterns of linear subspaces with the hypercube
• On the number of star‐shaped classes in optimal colorings of Kneser graphs
• Intersection Patterns of Convex Sets via Simplicial Complexes: A Survey
• On the generalized Erdős-Kneser conjecture: proofs and reductions
• Finite sets as complements of finite unions of convex sets
• Title not available (Why is that?)
• Tverberg’s theorem is 50 years old: A survey
• Finite sets and symmetric simplicial sets
• Intersection patterns of convex sets
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Title not available (Why is that?)
• Intersection Disjunctions for Reverse Convex Sets
• Fair splittings by independent sets in sparse graphs

This page was built for publication: Intersection patterns of finite sets and of convex sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2980804)