University of Delaware
Department of Mathematical Sciences
Discrete Mathematics Seminar

Friday, May 1, 2:30 pm, Room 210 Ewing Hall

A Design Type Result Via Hamiltonia Cycles

Gyola O. H. Katona
Director, Mathematical Institute of the Hungarian Academy of Sciences

Let X be a finite set of n elements and tex2html_wrap_inline22 be integers. Unordered pairs tex2html_wrap_inline24 of disjoint q-element subsets of X will be considered. We say that two such pairs tex2html_wrap_inline30 are far if tex2html_wrap_inline32 implies tex2html_wrap_inline34 and tex2html_wrap_inline36 implies tex2html_wrap_inline38. We will prove that if n is large enough then the family of all q-element subsets of X with one possible exception (if the number of q-element subsets is odd) can be partitioned into disjoint pairs of q-element subsets which are pairwise far. The proof uses a generalization of Dirac's theorem on Hamiltonian cycles.