TR-2007-10

A result on crossing families of odd sets

Tamás Király



Abstract

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:

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


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