Multilabeled versions of sperner's and fan's lemmas and applications

Frederic Meunier; Francis Edward Su

doi:10.1137/18M1192548

Multilabeled versions of sperner's and fan's lemmas and applications

Frederic Meunier
, Francis Edward Su

Harvey Mudd College

Research output: Contribution to journal › Article › peer-review

Abstract

We propose a general technique related to the polytopal Sperner lemma for proving old and new multilabeled versions of Sperner's lemma. A notable application of this technique yields a cake-cutting theorem where the number of players and the number of pieces can be independently chosen. We also prove multilabeled versions of Fan's lemma, a combinatorial analogue of the Borsuk-Ulam theorem, and exhibit applications to fair division and graph coloring.

Original language	English
Pages (from-to)	391-411
Number of pages	21
Journal	SIAM Journal on Applied Algebra and Geometry
Volume	3
Issue number	3
DOIs	https://doi.org/10.1137/18M1192548
Publication status	Published - 1 Jan 2019

Keywords

Cake-cutting
Consensus-halving
Fan's lemma
Graph coloring
Labelings
Sperner's lemma

Access to Document

10.1137/18M1192548

Cite this

@article{ad1a45a9d96b491aa3c1ed5741914e1b,

title = "Multilabeled versions of sperner's and fan's lemmas and applications",

abstract = "We propose a general technique related to the polytopal Sperner lemma for proving old and new multilabeled versions of Sperner's lemma. A notable application of this technique yields a cake-cutting theorem where the number of players and the number of pieces can be independently chosen. We also prove multilabeled versions of Fan's lemma, a combinatorial analogue of the Borsuk-Ulam theorem, and exhibit applications to fair division and graph coloring.",

keywords = "Cake-cutting, Consensus-halving, Fan's lemma, Graph coloring, Labelings, Sperner's lemma",

author = "Frederic Meunier and Su, \{Francis Edward\}",

note = "Publisher Copyright: {\textcopyright} 2019 Society for Industrial and Applied Mathematics",

year = "2019",

month = jan,

day = "1",

doi = "10.1137/18M1192548",

language = "English",

volume = "3",

pages = "391--411",

journal = "SIAM Journal on Applied Algebra and Geometry",

issn = "2470-6566",

number = "3",

}

TY - JOUR

T1 - Multilabeled versions of sperner's and fan's lemmas and applications

AU - Meunier, Frederic

AU - Su, Francis Edward

PY - 2019/1/1

Y1 - 2019/1/1

N2 - We propose a general technique related to the polytopal Sperner lemma for proving old and new multilabeled versions of Sperner's lemma. A notable application of this technique yields a cake-cutting theorem where the number of players and the number of pieces can be independently chosen. We also prove multilabeled versions of Fan's lemma, a combinatorial analogue of the Borsuk-Ulam theorem, and exhibit applications to fair division and graph coloring.

AB - We propose a general technique related to the polytopal Sperner lemma for proving old and new multilabeled versions of Sperner's lemma. A notable application of this technique yields a cake-cutting theorem where the number of players and the number of pieces can be independently chosen. We also prove multilabeled versions of Fan's lemma, a combinatorial analogue of the Borsuk-Ulam theorem, and exhibit applications to fair division and graph coloring.

KW - Cake-cutting

KW - Consensus-halving

KW - Fan's lemma

KW - Graph coloring

KW - Labelings

KW - Sperner's lemma

UR - https://www.scopus.com/pages/publications/85090658140

U2 - 10.1137/18M1192548

DO - 10.1137/18M1192548

M3 - Article

AN - SCOPUS:85090658140

SN - 2470-6566

VL - 3

SP - 391

EP - 411

JO - SIAM Journal on Applied Algebra and Geometry

JF - SIAM Journal on Applied Algebra and Geometry

IS - 3

ER -

Multilabeled versions of sperner's and fan's lemmas and applications

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this