Scarf's Theorem and Applications in Combinatorics

Scarf"s Theorem;Sperner"s Lemma;fractional stable matching;strong fractional kernel;rent partitionning;cake cutting;Combinatorics and Optimization

Rioux, Caroline

University of Waterloo

关键词: Scarf";    s Theorem;    Sperner";    s Lemma;    fractional stable matching;    strong fractional kernel;    rent partitionning;    cake cutting;    Combinatorics and Optimization;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/2627/1/main.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

A theorem due to Scarf in 1967 is examined in detail. Several versions ofthis theorem exist, some which appear at first unrelated.Two versionscan be shown to be equivalent to a result due to Sperner in 1928: fora proper labelling of the vertices in a simplicial subdivision of an n-simplex,there exists at least one elementary simplex which carries all labels {0,1,..., n}.A third version is more akin to Dantzig;;s simplex method and is also examined.In recent years many new applications in combinatorics have been found,and we present several of them. Two applications are in the area of fair division: cake cuttingand rent partitioning. Two others are graph theoretic: showing the existenceof a fractional stable matching in a hypergraph and the existence of a fractional kernel in adirected graph. For these last two, we also show the second implies the first.