Extremal problems on shadows and hypercuts in simplicial complexes

Let F be an n-vertex forest. We say that an edge e / ∈ F is in the shadow of F if F ∪{e} contains a cycle. It is easy to see that if F is “almost a tree”, that is, it has n−2 edges, then at least bn24 c edges are in its shadow and this is tight. Equivalently, the largest number of edges an n-vertex cut can have is bn24 c. These notions have natural analogs in higher d-dimensional simplicial complexes, graphs being the case d = 1. As it turns out in dimension d> 1 the corresponding bounds depend on the underlying field of coefficients F. We solve these questions in full for d = 2 and for F = Q and F2. The higher-dimensional results remarkably differ from the case in graphs. Thus we construct 2-dimensional “almost-hypertrees ” (properly defined below) with an empty shadow for F = Q. For F = F2 we determine the least possible density of the shadow which turns out to be vanishingly small but positive. We also study the least possible size of hypercuts and k-hypercuts in d-dimensional complexes. Finally, we mention several intriguing open questions