On dissections of the n-cube (Q580367)

Given a family \({\mathfrak C}\) of subcubes of the n-cube \(B_ n\) \((n\in {\mathbb{N}}^ X)\), the authors examine the number \(\sigma\) of components of the subgraph of \(B_ n\) that is induced by the vertex set \(B_ n\setminus U{\mathfrak C}.\) Theorem 1: If \(c:=1/16\) and \(\Gamma (n):=(\log_ 2n)^ 2\), then \(\sigma\leq | {\mathfrak C}| \cdot 2^{(n-c\Gamma (n))}\). This inequality yields lower bounds of the formula size of parity and other Boolean functions in the case of depth 3 (Theorem 2).