TR-2007-10

A result on crossing families of odd sets

Tamás Király

The following question is answered: given a crossing family F of odd subsets of an even-sized ground set V, what is the condition of the existence of a pairing M of the elements of V for which d_M(X)=1 for every X in F? We show that the pairing exists if and only if F does not have a specific configuration of 4 sets. We present a consequence related to the conjecture of Woodall on dijoins.

Bibtex entry:

@techreport{egres-07-10,

AUTHOR	=	{Kir{\'a}ly, Tam{\'a}s},
TITLE	=	{A result on crossing families of odd sets},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2007},
NUMBER	=	{TR-2007-10}

}