Path and Cycle Decompositions of Hypercube Graphs
Date:
During the summer of 2021, I participated in an REU at Carnegie Mellon University’s Summer Undergraduate Applied Mathematics Institute. Here two other students and I, advised by Professor David Offner, did novel research in graph theory which we are in the process of writing a paper about.
This program culminated in a poster session with several other summer programs at CMU. A link to our poster can be found here, and you can find our project listed on the SUAMI 2021 page here. The abstract for our project is also pasted below.
A graph $H$ decomposes a graph $G$ if the edge set of $G$ can be partitioned into edge-disjoint subgraphs isomorphic to $H$. We consider decompositions of the $n$-dimensional hypercube $Q_n$ into paths and cycles. A conjecture by Erde (2014) asserts that if $n$ is even, then a path of length $\ell$ decomposes $Q_n$ if the necessary conditions that $\ell < 2n$ and $\ell$ divides the number of edges of $Q_n$ hold.
Offner et al. (2021) proved, among other results, that if $n$ is the sum of at most two powers of $2$, then the cycle with the largest length divisible by $n$ while still satisfying the necessary conditions provided by Erde decomposes $Q_n$. We improved this result to the case of $n$ being the sum of at most three powers of $2$, and strengthened other results of Offner et. al.