Semi-perfect 1-Factorizations of the Hypercube

by Natalie Behague

Abstract:

A 1-factorization of a graph $H$ is a partition of the edges of $H$ into disjoint perfect matchings ${M_1,M_2,\ldots,M_n}$ , also known as 1-factors. A 1-factorization $\mathcal{M} = {M_1,M_2,\ldots,M_n}$ of a graph $G$ is called perfect if the union of any pair of 1-factors $M_i, M_j$ with $i \ne j$ is a Hamilton cycle. The existence or non-existence of perfect 1-factorizations has been studied for various families of graphs. Perhaps the most famous open problem in the area is Kotzig’s conjecture, which states that the complete graph $K_{2n}$ has a perfect 1-factorization. In my work I have focused on another well-studied family of graphs: the hypercubes $Q_d$ in $d$ dimensions. There is no perfect 1-factorization of $Q_d$ for $d>2$ . As a result, we need to consider a weaker concept.

A 1-factorization $\mathcal{M}$ is called $k$ -semi-perfect if the union of any pair of 1-factors $M_i, M_j$ with $1 \le i \le k$ and $k+1 \le j \le n$ is a Hamilton cycle. It was proved that there is a 1-semi-perfect 1-factorization of $Q_d$ for every integer $d \ge 2$ by Gochev and Gotchev, Královič and Královič, and Chitra and Muthusamy, in answer to a conjecture of Craft. My main result is a proof that there is a $k$ -semi-perfect 1-factorization of $Q_d$ for all $k$ and all $d$ , except for one possible exception when $k=3$ and $d=6$ . I will conclude with some questions concerning other generalisations of perfect 1-factorizations.

Event Timeslots (1)

Thursday
4:30 pm - 4:55 pm
Natalie Behague