A sparse colorful polytopal KKM theorem

DOI10.1007/S00454-022-00464-YarXiv2112.14421OpenAlexW4311309989MaRDI QIDQ6204766FDOQ6204766

Authors: Daniel McGinnis, Shira Zerbib 

Publication date: 2 April 2024

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

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.

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

(n)-dimensional polytopes (52B11) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) 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)

Cites Work

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

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)