Extremal hypercuts and shadows of simplicial complexes

• Published in: Israel journal of mathematics 2019, Vol.229 (1), p.133-163
• Main Authors: Linial, Nati, Newman, Ilan, Peled, Yuval, Rabinovich, Yuri
• Format: Article
• Language: English
• Subjects: Algebra; Analysis; Applications of Mathematics; Forests; Graph theory; Group Theory and Generalizations; Mathematical and Computational Physics; Mathematics; Mathematics and Statistics; Shadows; Theoretical
• ISSN: 0021-2172; 1565-8511
• DOI: 10.1007/s11856-018-1803-0

Let F be an n -vertex forest. An edge e ∉ F is said to be in F ’s shadow if F ∪ { e } contains a cycle. It is easy to see that if F is an “almost tree”, i.e., a forest that contains two components, then its shadow contains at least ⌊ ( n − 3 ) 2 4 ⌋ edges and this is tight. Equivalently, the largest number of edges in an n -vertex cut is ⌊ n 2 4 ⌋ . These notions have natural analogs in higher d -dimensional simplicial complexes which played a key role in several recent studies of random complexes. The higher-dimensional situation differs remarkably from the one-dimensional graph-theoretic case. In particular, the corresponding bounds depend on the underlying field of coefficients. In dimension d = 2 we derive the (tight) analogous theorems. We construct 2-dimensional “ℚ-almost-hypertrees” (defined below) with an empty shadow. We prove that an “ F 2 -almost-hypertree” cannot have an empty shadow, and we determine its least possible size. We also construct large hyperforests whose shadow is empty over every field. For d ≥ 4 even, we construct a d -dimensional F 2 -almost-hypertree whose shadow has vanishing density. Several intriguing open questions are mentioned as well.