Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties

Question

Let $n$ be a large positive integer. Given a collection $\mathfrak S$ of subsets of $[n] := \{1,2,\ldots,n\}$, and a vector $z=(z_1,\ldots,z_n)\in \{\pm 1\}^n$, define $$ f_{\mathfrak S}(z) := \sum_{\sigma \in \mathfrak S} z_\sigma, $$ where $z_\sigma := \prod_{j \in \sigma} z_j$. For any $j \in [n]$, let $d_{\mathfrak S}(j) = |\partial_j \mathfrak S|$ be "degree" of $j$ w.r.t $\mathfrak S$, where $$ \partial_j \mathfrak S := \{\sigma\setminus\{j\} \mid \sigma \in \mathfrak S, \,j \in \sigma\} = \{s \subseteq [n] \mid j \not \in s\text{ and }s \cup \{j\} \in \mathfrak S\}. $$ Also define the minimal degree w.r.t $\mathfrak S$ as $d^\star_{\mathfrak S} := \min_{j \in [n]} d_{\mathfrak S}(j)$.

Examples

• Pairs. If $\mathfrak S$ is the collection of distinct unordered pairs (i.e doubletons) of elements of $[n]$, then it is easy to see that $\partial_j \mathfrak S$ is the collection of all singletons of $[n]$ except $\{j\}$, and so $d_{\mathfrak S}^\star = n-1$ for all $j \in [n]$.

• Simplicial Complex. On the other hand, if $\mathfrak S$ is a simplicial complex, then $\partial_j S$ is the collection of elements of $\mathfrak S$ which don't contain $j$. For example, if $\mathfrak S = K_{n,d}$ is the collection of all subsets of $[n]$ with $d$ or fewer elements (where $d \in [n]$), then $\partial_j \mathfrak S$ is isomorphic to $K_{n-1,d-1}$, and so $$ d_{\mathfrak S}^\star = |K_{n-1,d-1}| = \sum_{i=0}^{d-1} {n-1 \choose i}. $$

• Monster. Finally, if $1 \le k \le n$, and $G_1,\ldots,G_k$ is a partition of $[n]$, and $\mathfrak S$ is the collection of subsets of $[n]$ which contain exactly one element from each $G_i$, then $d_{\mathfrak S}^\star = p^{k-1}$, where $p := n/k$.

Let us say that $\mathfrak S$ is "nice" if the following three conditions are satisfied:

• (1) Exponential Degree: $d_{\mathfrak S}^\star \ge 2^{\alpha n}$ for some constant $\alpha \in (0, 1]$.
• (2) Efficiency: $f_{\mathfrak S}(z)$ can be computed in linear time time $O(n)$, for any $z \in \{\pm 1\}^n$.
• (3) Invariance: $f_{\mathfrak S}(\overline z) = f_{\mathfrak S}(z)$ for any $z,\overline z \in \{\pm 1\}^n$ such that the components of $\overline z$ are a permutation of the components of $z$.

It is clear that the "pairs" example verifies the conditions (2) and (3), but not (1). The "simplicial complex" example verifies conditions (1 and 3) or (2 and 3). This is because thanks to https://cstheory.stackexchange.com/a/52570/44644, $f_{\mathfrak S}$ can be computed in time of order $O(nd)$; if the time complexity is really $\Theta(nd)$ (see Question 2 below), then it can be linear is if $d=O(1)$, which forces $d_{\mathfrak S}^\star$ to be of polynomial order $n^{d-1}$.

Finally, still thanks to the previous reference, for appropriate choice of $k$ (for example assume WLOG that $n$ is even, and take $k=n/2$) the "monster" example verifies conditions (1) and (2), but not (3). Condition (1) is clear to see. For condition (2), simply note that by construction $f_{\mathfrak S}(z) := \sum_{\sigma \in \mathfrak S} z_\sigma = \sum_{i=1}^k \prod_{j \in G_i} z_j$, which definitely takes $O(n)$ time to compute. Condition (3) fails because every partitioning of $[n]$ induces a partial order on $[n]$, and so $f_{\mathfrak S}(\overline z)$ will be different from $f_{\mathfrak S}(z)$ in general.

Question 1

What is an explicit construction of a "nice" $\mathfrak S$ ?

N.B: I'm fine with randomized constructions, which verify the above 3 conditions in an appropriate probabilistic sense.

Question 2

Is $\mathfrak S = K_{n,d}$ efficient ?

Answer 1

Here's an elaboration on my comment, assuming I didn't get lost in all the notation above:

For $\mathfrak{S}=\mathcal{P}([n])$, the power set of $[n]$, it holds that \begin{equation*} f_{\mathfrak{S}}(z) = \sum_{S\subseteq [n]} z^S = 2^n\prod_{i=1}^n \left(\frac{1+z_i}{2}\right), \end{equation*} which implies that $f_{\mathfrak{S}}(z)$ is $2^n$ if $z_i=1$ for all $i\in [n]$ and otherwise is zero. As best I can tell, this example trivially satisfies all the criteria above.

The case of $\mathfrak{S}=K_{n,d}$ is slightly trickier, but it can be computed using $O(d)$ arithmetic operations (which seemed to be the measure in the other link as well); in particular, this is without considering the time it takes to read and store large numbers (which seems to be the case in the linked answer as well, so hopefully this is okay). If $z$ has $k$ entries with $-1$, we may assume the first $k$ entries are $-1$ and the rest are $+1$ by invariance. Then looking at each monomial separately, we find \begin{equation*} f_{K_{n,d}}(z) = A_{n,d,k,\mathsf{even}}-A_{n,d,k,\mathsf{odd}} \end{equation*} where $A_{n,d,k,\mathsf{even}}$ is the number of subsets of $[n]$ of size at most $d$ with even intersection with $\{1,\ldots,k\}$ and analogously for $A_{n,d,k,\mathsf{odd}}$.

To calculate $A_{n,d,k,\mathsf{even}}$, standard combinatorics implies this is just \begin{equation} \label{eq:even} A_{n,d,k,\mathsf{even}} = \sum_{j=0, \text{$j$ even}}^d {k \choose j}\left(\sum_{\ell=0}^{d-j} {n-k \choose \ell}\right) = \sum_{j=0, \text{$j$ even}}^d {k \choose j} S_{n,k,d-j}, \end{equation} where \begin{equation*} S_{n,k,r}\triangleq \sum_{\ell=0}^{r} {n-k \choose \ell}. \end{equation*} The key now is to calculate the $S_{n,k,r}$ using few arithmetic operations by being careful. The key is using the recurrences \begin{equation*} {m \choose i} = {m \choose i-1}\cdot \frac{m-i+1}{i}, \end{equation*} one can compute all ${n-k \choose 0},\ldots, {n-k \choose d}$ using $O(d)$ arithmetic operations total. Then, using the recurrence \begin{equation*} S_{n,k,r+1} = S_{n,k,r} + {n-k \choose r+1}, \end{equation*} one can compute each of the $S_{n,k,0},\ldots,S_{n,k,d}$ using $O(d)$ more arithmetic operations. After similarly computing all of ${k \choose 0}, \ldots, {k \choose d}$ using $O(d)$ arithmetic operations, the identity for $A_{n,d,k,\mathsf{even}}$ requires $O(d)$ more arithmetic operations given what has already been calculated. The same thing can be done for $A_{n,d,k,\mathsf{odd}}$. Of course, if one cares about time, it takes $O(n)$ to count the number of $-1$ entries, and if you're concerned about bit complexities, which should all be like $O(d\log n)$, you'll probably get something like $n+\tilde{O}(d^2\log n)$ for total time complexity using fancy multiplication algorithms.