Families of sets with parity conditions

Question

While crunching some numbers for this question, I came across a different one. An answer would give an estimate for complexity of my procedure, as well as potentially give an insight to the former question itself.

Let $[n] = \{1, \ldots, n\}$. Say that a family $S \subseteq 2^{[n]}$ belongs to $\mathcal{F}_n$ iff for any $X \in S$ the number of $Y \in S$ containing $X$ as a subset is odd (including $Y = X$ itself). E.g. (below $1$ and $2$ are singleton sets $\{1\}$ and $\{2\}$, and $12 = \{1, 2\}$ by violent notation abuse)

• $\mathcal{F}_0 = \{\varnothing, \{\varnothing\}\}$ (assuming $[0] = \varnothing$),
• $\mathcal{F}_1 = \{\varnothing, \{\varnothing\}, \{1\}\}$,
• $\mathcal{F}_2 = \{\varnothing, \{\varnothing\}, \{1\}, \{2\}, \{12\}, \{1, 2\}, \{\varnothing, 1, 2\}\}$.

This question is concerned with the size of $\mathcal{F}_n$ as a function of $n$. Some trivial bounds are $2^{n \choose n / 2} \leq |\mathcal{F}_n| \leq 2^{2^n}$. Taking logarithms, we have ${n \choose n / 2} \leq \log_2 |\mathcal{F}_n| \leq 2^n$. For large $n$, the lower and upper bound are $\Theta(\sqrt{n})$ apart.

First few values of $|\mathcal{F}_n|$, and entries in the logarithmic bound are listed below:

$n$	$|\mathcal{F}_n|$	$\log_2{|\mathcal{F}_n|}$	${n \choose n / 2}$	$2^n$
$0$	$2$	$1$	$1$	$1$
$1$	$3$	$ \approx 1.58496$	$1$	$2$
$2$	$7$	$ \approx 2.80735$	$2$	$4$
$3$	$43$	$ \approx 5.42626$	$3$	$8$
$4$	$1687$	$ \approx 10.72024$	$6$	$16$
$5$	$2204623$	$ \approx 21.07210$	$10$	$32$
$6$	$2809835768527$	$ \approx 41.35362$	$20$	$64$

Questions: is any of the bounds above for $\log_2 |\mathcal{F}_n|$ asymptotically tight? If no, what's the correct asymptotics for $\log_2 |\mathcal{F}_n|$?

UPD: a reference provided in Tim's answer (namely Thm. 18 in Section 3.4) presents a subset of $\mathcal{F}_n$ of size $2^{2^{n - 1}}$, namely all $S \subseteq 2^{[n]}$ satisfiying a stronger condition: a set $X \subseteq [n]$ is in $S$ iff it's contained in an odd number of elements of $S$. This establishes $2^{n - 1} \leq \log_2{|\mathcal{F}_n|} \leq 2^n$. One then hopes that $\log_2{|\mathcal{F}_n|} \sim c 2^n$ for a certain constant $c \in [1/2, 1]$. Does such a $c$ exist? Can it be bounded, or even obtained precisely?

For reference, here is my procedure for calculating $|\mathcal{F}_n|$. We recursively obtain all possible $S \in \mathcal{F}_n$ starting from $S = \varnothing$ by repeatedly adding $X$ not containing any prior elements of $S$ (this can not violate the premise for already added elements of $S$). Let $T$ be the set of candidates to be next added to $S$. Initially $T = 2^{[n]}$. If $X$ is any maximal set in $T$ (say, lexicographically largest), we either skip it, branching to $S \to S, T \to T - X$, or add $X$ to $S$, branching to $S \to S + X, T \to T \operatorname \triangle 2^X$. The number of successful branches from any intermediate point only depends on $T$, which allows for some efficient caching.

Answer 1

Based on your data so far, one might wildly guess that $\log_2(\mathcal{F}_n) \approx\frac232^n.$ Another wild guess would be $\approx \frac{2^n+\binom{n}{n/2}}2.$

Here is a somewhat vague argument that a lower bound on the order of $\frac122^n$ might be possible. With more care it might even give a very good estimate of $\log_2(\mathcal{F}_n).$

In brief, your branching procedure has an evolving pair of $S,T$ where $S$ will be the family and $T$ is the sets available to currently be added (i.e. in an even number of already chosen sets). Instead, go through all the subsets (in a top down order) and for each, if it is available, make a binary choice and branch. If not available, reject forever (for that particular branch). How often do we get a chance to make the binary choice? It seems reasonable that this happens about half the time. It seems pretty random (after a while) if the number of supersets of $X$ in $S$ will be even or odd. Hence $\log_2(\mathcal{F}_n) \approx 2^{n-1}.$

Here is a slight change in your procedure. It might run faster. At least I find it easier conceptually. Decide at the first step which $n-1$-sets (if any) will be in $S.$ At the next step look at all the available $n-2$-sets and pick a subset of them. Continue. So my naive argument is that the expected number of choices should be around $$\prod_0^{n-1}2^{\binom{n}{j}/2}.$$ Or a bit more since at the first step we have $2^\binom{n}{n-1}$ choices rather than the estimated $2^{n/2}$ for this size.

Note that there is the family $\{[n]\}\in \mathcal{F}_n$ but, other than that, no $S \in \mathcal{F}_n$ has $[n]\in S.$ This is because the next largest member of $S$ would be contained in only itself and $[n].$

An interesting experiment, which I did not do, might be to pick an $n$ and carry this out (many times) using a (virtual) fair coin. Then look at the typical behavior.

AT the first step we have $2^n$ choices. At the next step we consider the $n-2$-sets. Suppose that we previously choose $m$ of the $n$ subsets of size $n-1$. Then the number of available $n-2$-sets will be $c_m=\Sigma\binom{m}{t}\binom{n-m}{m-2-t}$ where the sum is over the $t$ with the same parity as $m$. So actually, $c_0=c_n=\binom{n}{n-2}$ and $c_1=c_{n-1}=\binom{n}{n-2}-(n-1).$ for $n=12$ the counts are $66, 55, 46, 39, 34, 31, 30, 31, 34, 39, 46, 55, 66.$ Almost all these numbers exceed half of $\binom{12}{10}=66.$ And this seems typical for other $n$. However the central numbers, which are less than half, come up (much) more often. So a weighted average is $$\frac{\sum_0^{12}\binom{12}{m}c_m}{2^{12}}.$$ That comes to exactly $33.$ In retrospect, it is easy to see that exactly half the possible choices for $n-1$-sets are such that a given $n-2$-set is then available. Then again, maybe it is better to take the $\log$ of the average rather than the average of the$\log$s. $$\log_2(\frac{\sum_0^{12}\binom{12}{m}2^{c_m}}{2^{12}})=55.0852$$ That seems too large.

Past there the analysis is less trivial. At the next to last stage we have (almost always) already committed to a healthy number of members of $S.$ So we would expect the number of available singleton sets to be about $n/2.$ As long as it is not zero, half the choices of available singletons will allow us to add (or not add) $\emptyset$ to $S$ and the other half will not.