TR-2008-13

Kernels, stable matchings, and Scarf's Lemma

Tamás Király, Júlia Pap

Published in:
RIMS Kôkyuroku Bessatsu B23 (2010), 131-145.



Abstract

Scarf's Lemma originally appeared as a tool to prove the non-emptiness of the core of certain NTU games. More recently, however, several applications have been found in the area of graph theory and discrete mathematics. In this paper we present and extend some of these applications. In particular, we prove results on the existence of kernels in orientations of h-perfect graphs. We describe a new direct link between Scarf's Lemma and Sperner's Lemma giving a new proof to the former.


Bibtex entry:

@techreport{egres-08-13,
AUTHOR = {Kir{\'a}ly, Tam{\'a}s and Pap, J{\'u}lia},
TITLE = {Kernels, stable matchings, and Scarf's Lemma},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2008},
NUMBER = {TR-2008-13}
}


Last modification: 5.12.2018. Please email your comments to Tamás Király!