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 dM(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:

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

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