Path and Cycle Decompositions of Hypercube Graphs

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.

This program culminated in a poster session with several other summer programs at CMU. Our poster can be found below, 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 ℓ decomposes Q_n if the necessary conditions that ℓ < 2n and ℓ 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.