TR-2014-11

On weighted kernels of two posets

Tamás Fleiner, Zsuzsanna Jankó

Published in:
Order 33, 51–65 (2016). DOI link

A recent result of Aharoni Berger and Gorelik [1] is a weighted generalization of the well-known theorem of Sands Sauer and Woodrow [7] on monochromatic paths. The authors prove the existence of a so called weighted kernel for any pair of weighted posets on the same ground set. In this work, we point out that this result is closely related to the stable marriage theorem of Gale and Shapley [6], and we generalize Blair's theorem by showing that weighted kernels form a lattice under a certain natural order. To illustrate the applicability of our approach, we prove further weighted generalizations of the Sands Sauer Woodrow result.

Bibtex entry:

@techreport{egres-14-11,

AUTHOR	=	{Fleiner, Tam{\'a}s and Jank{\'o}, Zsuzsanna},
TITLE	=	{On weighted kernels of two posets},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2014},
NUMBER	=	{TR-2014-11}

}