Extremal problems on shadows and hypercuts in simplicial complexes

MaRDI QIDQ6253665zbMATH OpenFDO

Authors Nathan Linial, Ilan Newman, Yuval Peled, Yuri Rabinovich

Publication date 4 August 2014

Abstract: Let $F$ be an $n$-vertex forest. We say that an edge $eotinF$ is in the shadow of $F$ if $Fcupe$ 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 $lfloorfrac{n}^{2}4floor$ edges are in its shadow and this is tight. Equivalently, the largest number of edges an $n$-vertex cut can have is $lfloorfrac{n}^{2}4floor$. These notions have natural analogs in higher $d$-dimensional simplicial complexes, graphs being the case $d=1$. The results in dimension $d>1$ turn out to be remarkably different from the case in graphs. In particular the corresponding bounds depend on the underlying field of coefficients. We find the (tight) analogous theorems for $d=2$. We construct $2$-dimensional "$mathbbQ$-almost-hypertrees" (defined below) with an empty shadow. We also show that the shadow of an "$mathbb{F}_2$-almost-hypertree" cannot be empty, and its least possible density is $Theta(frac1n)$. In addition we construct very large hyperforests with a shadow that is empty over every field. For $dge4$ even, we construct $d$-dimensional $mathbb{F}_2$-almost-hypertree whose shadow has density $o_n(1)$. Finally, we mention several intriguing open questions.

This page was built for publication: Extremal problems on shadows and hypercuts in simplicial complexes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6253665)