Optimal bounds for the colored Tverberg problem

DOI10.4171/JEMS/516zbMATH Open1327.52009arXiv0910.4987OpenAlexW2963084798MaRDI QIDQ2344495FDOQ2344495

Authors: Pavle V. M. Blagojević, Benjamin Matschke, Günter M. Ziegler 

Publication date: 15 May 2015

Published in: Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

Abstract: We prove a "Tverberg type" multiple intersection theorem. It strengthens the prime case of the original Tverberg theorem from 1966, as well as the topological Tverberg theorem of Barany et al. (1980), by adding color constraints. It also provides an improved bound for the (topological) colored Tverberg problem of Barany & Larman (1992) that is tight in the prime case and asymptotically optimal in the general case. The proof is based on relative equivariant obstruction theory.

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

Recommendations

• Optimal bounds for a colorful Tverberg-Vrećica type problem
• Tight lower bounds for the complexity of multicoloring
• Tight lower bounds for the complexity of multicoloring
• Asymptotically optimal frugal colouring
• Asymptotically optimal frugal colouring
• On the approximability of the maximum interval constrained coloring problem
• On the approximability of the maximum interval constrained coloring problem
• The coloured Tverberg theorem, extensions and new results
• Algorithms and Computation
• Almost optimal solutions for bin coloring problems

zbMATH Keywords

chessboard complexesequivariant obstruction theoryBarany-Larman conjectureoptimal colored Tverberg theorem

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10) Helly-type theorems and geometric transversal theory (52A35) Fixed points and coincidences in algebraic topology (55M20) Equivariant operations and obstructions in algebraic topology (55S91)

Cites Work

• Transformation groups
• Simplicial complexes of graphs
• Title not available (Why is that?)
• Shellability of chessboard complexes
• Chessboard Complexes and Matching Complexes
• Torsion in the matching complex and chessboard complex
• A Generalization of Radon's Theorem
• Using equivariant obstruction theory in combinatorial geometry
• 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
• \(3N\) colored points in a plane
• User's guide to equivariant methods in combinatorics. II
• On a Topological Generalization of a Theorem of Tverberg
• The colored Tverberg's problem and complexes of injective functions
• A Colored Version of Tverberg's Theorem
• Chessboard complexes indomitable
• Tverberg partitions and Borsuk-Ulam theorems.
• Optimal bounds for a colorful Tverberg-Vrećica type problem
• A geometric proof of the colored Tverberg theorem
• On the number of halving planes
• Tverberg's theorem with constraints
• Erratum to ``Notes on the topological Tverberg theorem [Discrete Math. 241, 207-233 (2001)]
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (50)

• Tverberg's theorem, disks, and Hamiltonian cycles
• No-dimensional Tverberg theorems and algorithms
• A local criterion for Tverberg graphs
• Eliminating Tverberg points. I. An analogue of the Whitney trick
• A User's guide to the topological Tverberg conjecture
• On the number of colored Birch and Tverberg partitions
• A topological central point theorem
• Optimal colored Tverberg theorems for prime powers
• Intersection patterns of finite sets and of convex sets
• Chessboard complexes indomitable
• Intersecting diametral balls induced by a geometric graph
• A geometric proof of the colored Tverberg theorem
• Regular polygonal partitions of a Tverberg type
• Splitting loops and necklaces: variants of the square peg problem
• Symmetric multiple chessboard complexes and a new theorem of Tverberg type
• A tight colored Tverberg theorem for maps to manifolds
• Almost optimal solutions for bin coloring problems
• Quantitative combinatorial geometry for concave functions
• Tolerance for colorful Tverberg partitions
• The colored Tverberg's problem and complexes of injective functions
• Generalized chessboard complexes and discrete Morse theory
• A simpler proof of the Boros-Füredi-Bárány-Pach-Gromov theorem
• Optimal bounds for a colorful Tverberg-Vrećica type problem
• Algorithms and Computation
• On the generalized Erdős-Kneser conjecture: proofs and reductions
• Robust Tverberg and Colourful Carathéodory Results via Random Choice
• On levels in arrangements of surfaces in three dimensions
• A Tverberg type theorem for matroids
• Counterexamples to the colorful Tverberg conjecture for hyperplanes
• Colored Tverberg theorem with new constraints on the faces
• Projective center point and Tverberg theorems
• Helly-type problems
• The crossing Tverberg theorem
• On Reay's relaxed Tverberg conjecture and generalizations of Conway's thrackle conjecture
• Tverberg’s theorem is 50 years old: A survey
• Beyond the Borsuk–Ulam Theorem: The Topological Tverberg Story
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Invariants of graph drawings in the plane
• On a conjecture of Karasev
• Envy-free division via configuration spaces
• Title not available (Why is that?)
• Theorems of Carathéodory, Helly, and Tverberg without dimension
• Dense point sets with many halving lines
• A tight colored Tverberg theorem for maps to manifolds (extended abstract)
• The coloured Tverberg theorem, extensions and new results
• A Colored Version of Tverberg's Theorem
• Multiple chessboard complexes and the colored Tverberg problem
• Plus minus analogues for affine Tverberg type results
• Quantitative combinatorial geometry for continuous parameters
• Fair splittings by independent sets in sparse graphs

This page was built for publication: Optimal bounds for the colored Tverberg problem

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