Boundaries of Hypertrees and Hamiltonian Cycles in Simplicial Complexes

Rogers Mathew, Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad

Published 2015-07-16Version 1

A $d$-dimensional hypertree ($d$-tree) $T$ on $[n]$ is a maximal acyclic $d$-dimensional simplicial complex on $[n]$ with full $(d-1)$-skeleton. It is a natural and meaningful generalization of the graph-theoretic notion of a tree. Despite their fundamental role in the combinatorial and algorithmic theory of simplicial complexes, many structural aspects of $d$-trees are presently poorly understood. Here we study the boundaries $\partial T$ of $d$-trees, and the set of fundamental cycles defined by $T$. Our findings include: - A full characterization of $\partial T$ over $\mathbb{F}_2$ for $d\leq 2$, and some partial results for $d \geq 3$. - Upper and lower bounds on the size of the maximum simple $d$-dimensional cycle on $[n]$. In particular, for $d=2$, we explicitly construct $d$-dimensional Hamiltonian cycles on $[n]$, i.e., simple $d$-dimensional cycles of size $|T|+1\;=\; {{n-1} \choose d} + 1$. For $d\geq 3$, we explicitly construct simple $d$-dimensional cycles of size ${{n-1} \choose d} - O(n^{d-2})$. - Observing that the maximum of the expected distance between two vertices in a tree on $[n]$ is $\thicksim n/3$, which is attained on the Hamiltonian path, we ask a similar question for $d$-trees. How large can the size of an average fundamental cycle of a $d$-tree $T$ (i.e, the dependency created by adding a random uniform $d$-simplex on $[n]$ to $T$) be? For every natural $d$, we explicitly construct a $d$-tree $T$ with the size of an average fundamental cycle at least $c_d\, |T| \,=\, c_d\,{n \choose {d-1}}$, where $c_d$ is a constant depending on the dimension $d$ alone.