The maximum diameter of 2-dimensional simplicial complexes

2025/11/13 by Parczyk, Olaf, Rathke, Silas, Szabó, Tibor
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2511.10144

Abstract

We study a problem of Santos about the largest possible diameter of a d-dimensional (abstract) simplicial complex on n vertices. For dimension 2, we determine the exact value of the maximum for every n using an explicit construction. We also come across a tantalizing open problem about the packing of squares of Hamilton cycles in the complete graph and obtain an infinite sequence of tight explicit constructions.

Citations

• A proof of Ringel's Conjecture
• Perfectly packing graphs with bounded degeneracy and many leaves
• Randomized construction of complexes with large diameter
• Resolution of the Oberwolfach problem
• The existence of designs via iterative absorption: hypergraph F-designs for arbitrary F
• Packing spanning graphs from separable families
• Constructions of asymptotically shortest k-radius sequences

Related

• Complexes of nearly maximum diameter
• Randomized construction of complexes with large diameter
• Large Simple d-Cycles in Simplicial Complexes
• 2-complexes with large 2-girth
• The Moore Bound for Regular Simplicial Complexes