Boundaries of Hypertrees, and Hamiltonian Cycles in Simplicial Complexes

A $d$-hypertree on $[n]$ is a maximal acyclic $d$-dimensional simplicial complex with full $(d-1)$-skeleton on the vertex set $[n]$. Alternatively, in the language of algebraic topology, it is a minimal $d$-dimensional simplicial complex $T$ (assuming full $(d-1)$-skeleton) such that ${\tilde{H}}_{d-1}(T;\mathbb{F})=0$. The $d$-hypertrees are a basic object in combinatorial theory of simplicial complexes. They have been studied; and yet, many of their structural aspects remain poorly understood. In this paper we study the boundaries ${\mathrm{\partial }}_{d}T$ of $d$-hypertrees, and the fundamental $d$-cycles defined by them. Our findings include:

1. A full characterization of ${\mathrm{\partial }}_{d}T$ over ${\mathbb{F}}_2$ for $d \leq 2$,andsomepartialresultsfor$d \geq 3$.
2. Lower bounds on the maximum size of a largest simple $d$-cycle on $[n]$. In particular, for $d=2$, we construct a {\em Hamiltonian $d$-cycle} $H$ on $[n]$, i.e., a simple $d$-cycle of size $\left(\genfrac{}{}{0px}{}{n-1}{d}\right)+1$. For $d\ge 3$, we construct a simple $d$-cycle of size $\left(\genfrac{}{}{0px}{}{n-1}{d}\right)-O(n^{d-2})$.
3. Observing that the maximum of the expected distance between two vertices chosen uniformly at random in a tree ($1$-hypertree) on $[n]$ is at most $\sim n\mathrm{/}3$, attained on Hamiltonian paths, we ask a similar question about $d$-hypertrees. “How large can be the {\em average} size of a fundamental cycle of a $d$-hypertree $T$ (i.e., the expected size of the dependency created by adding a $d$-simplex on $[n]$, chosen uniformly at random, to $T$)?” For every $d\in \mathbb{N}$, we construct an infinite family of $d$-hypertrees $\{T\}$ with the average size of a fundamental cycle at least $c_d, |T| ,=, c_d,{n-1 \choose d}$,where$c_d$isaconstantdependingonthedimension$d$ alone.