Boundaries of Hypertrees, and Hamiltonian Cycles in Simplicial Complexes

Original · EN

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 Hd₋₁(T;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 ∂d T of d-hypertrees, and the fundamental d-cycles defined by them. Our findings include: 1. A full characterization of ∂d T over F₂ for d ≤ 2, and some partial results for d ≥ 3. 2. Lower bounds on the maximum size of a largest simple d-cycle on [n]. In particular, for d=2, we construct a Hamiltonian d-cycle H on [n], i.e., a simple d-cycle of size n-1 d + 1. For d≥ 3, we construct a simple d-cycle of size n-1 d - O(nᵈ⁻²). 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 n/3, attained on Hamiltonian paths, we ask a similar question about d-hypertrees. "How large can be the 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 ∈ N, we construct an infinite family of d-hypertrees {T} with the average size of a fundamental cycle at least cd |T| = cdn-1 d, where cd is a constant depending on the dimension d alone.