A sparse colorful polytopal KKM theorem

DOI10.1007/S00454-022-00464-YMaRDI QIDQ6204766zbMATH OpenOpenAlexFDO

Authors Daniel McGinnis, Shira Zerbib

Publication date 2 April 2024

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

colorful Carathéodory theoremfair division of multiple cakes

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42) Hypergraphs (05C65) Transversal (matching) theory (05D15) Helly-type theorems and geometric transversal theory (52A35) (n)-dimensional polytopes (52B11) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)

Abstract: Recently Sober'on proved a far-reaching generalization of the colorful KKM Theorem due to Gale: let $ngeqk$, and assume that a family of closed sets $(A_j^{i}midiin[n],jin[k])$ has the property that for every $$, the family $$ is a KKM cover of the $(k-1)$-dimensional simplex $Delt{a}^{k-1}$; then there is an injection $pi:[k]ightarrow[n]$ so that $$. We prove a polytopal generalization of this result, answering a question of Sober'on in the same note. We also discuss applications of our theorem to fair division of multiple cakes, $d$-interval piercing, and a generalization of the colorful Carath'eodory theorem.

Recommendations

• Colorful coverings of polytopes and piercing numbers of colorful \(d\)-intervals
• Fair division and generalizations of Sperner- and KKM-type results
• Colorful versions of the Lebesgue, KKM, and Hex theorem
• KKM type theorems with boundary conditions
• Multilabeled Versions of Sperner's and Fan's Lemmas and Applications

Cites work

• A generalization of Caratheodory's theorem
• A simple proof of K-K-M-S theorem
• Colorful coverings of polytopes and piercing numbers of colorful \(d\)-intervals
• Combinatorial formulae for multiple set-valued labellings
• Dividing a cake fairly
• Equilibrium in a discrete exchange economy with money
• Fair distributions for more participants than allocations
• Fair division with multiple pieces
• Fractional covers and matchings in families of weighted \(d\)-intervals
• How to Cut a Cake Fairly
• scientific article; zbMATH DE number 3422228 (Why is no real title available?)
• Lower bounds on the transversal numbers of \(d\)-intervals
• Maximum degree and fractional matchings in uniform hypergraphs
• Robust Tverberg and Colourful Carathéodory Results via Random Choice
• The intersection of a matroid and an oriented matroid
• Transversals of d-intervals
• Transversals of 2-intervals, a topological approach

Cited in

(1)

• Fair distribution of bundles

This page was built for publication: A sparse colorful polytopal KKM theorem

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