Sperner's Colorings, Hypergraph Labeling Problems and Fair Division

DOI10.1137/1.9781611973730.60zbMath1371.05094OpenAlexW4238536092WikidataQ33418956 ScholiaQ33418956MaRDI QIDQ5363096

Jan Vondrák, Maryam Mirzakhani

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973730.60

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Related Items

Subdivision of hypergraphs and their colorings, Homotopy and Hom construction in the category of finite hypergraphs, Sperner’s Colorings and Optimal Partitioning of the Simplex, Fair Division and Generalizations of Sperner- and KKM-type Results, A tour through Mirzakhani’s work on moduli spaces of Riemann surfaces, The Prisoner Shouting Puzzle and Variations, Envy-free cake division without assuming the players prefer nonempty pieces, Improving the integrality gap for multiway cut, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg