Distinguishing finite families of sets by algebras of bounded size

Question

Say that an algebra of sets $K$ distinguishes set $B$ from set $C$ provided that for some $A\in K$, we have exactly one of $A\cap B$ and $A\cap C$ non-empty. Given families $F$ and $G$ of sets, say that $K$ distinguishes $F$ from $G$ provided that it distinguishes every member of $F$ from every member of $G$.

Question 1: Is there a fixed finite $N$ such that for any finite families $G$ and $H$ of finite sets with $G\cap H=\varnothing$, there is an algebra $K$ of sets with $|K|\le N$ that distinguishes $G$ from $H$?

Question 2: If the answer is negative, is it still negative if we constrain $G$ and $H$ by requiring that all the members of $G\cup H$ have the same cardinality?

I would guess the answer to both is negative, but don't know how to prove it or find a reference. (This came up as part of something in finite model theory.)

Answer 1

The answer to Question 2 is also negative. I can show this using the Hales-Jewett Theorem. I am certain there must be a (much) nicer way to do this, but at the moment this is the only way I can think of.

Fix your constant $N$, and (aiming to answer question 2) fix some $\ell$ such that we want to have all the members of $G$ and $H$ have size $\ell$. Let $[2\ell] = \{1,2,\dots,2\ell\}$. Applying the Hales-Jewett Theorem, let $D$ be a (huge) number large enough that for any $2^N$-coloring of the $D$-dimensional hypercube $[2\ell] \times [2\ell] \times \dots [2\ell]$ ($D$ times), there is a monochromatic combinatorial line. Every combinatorial line in this hypercube has $2\ell$ points in it, ordered in a natural way. Let $A \in G$ if and only if there is some combinatorial line $L$ in our hypercube where $A$ is the set of odd-numbered points in the natural ordering of $L$. Let $H$ be defined similarly, but take the even-numbered points rather than the odd-numbered points.

To see that this works, suppose $K$ is any collection of $\leq\!N$ sets. Define a $2^{|K|}$-coloring of the $D$-dimensional hypercube $[2\ell] \times [2\ell] \times \dots [2\ell]$ by setting the "color" of a point $x$ to be $\{ A \in K :\, x \in A \}$. By our choice of $D$, this coloring of the hypercube contains a monochromatic combinatorial line $L$. But $K$ does not distinguish between the set of even-numbered points of $L$ and the set of odd-numbered points of $L$, though one of these is in $G$ and the other in $H$.

Answer 2

The answer to Question 1 is negative. Let $G=\{\{1, \dots, N+1\}\}$ and $H$ consist of all subsets of $\{1, \dots, N+1\}$ of size $N$. If $K$ is a distinguisher for $G$ and $H$, then for each $i \in \{1, \dots, N+1\}$ there must be a set $A \in K$ such that $A \cap \{1, \dots, N+1\}=\{i\}$. Thus, $|K| \geq N+1$.

Here is a simple proof that the answer to Question 2 is also negative, even if all sets in $G$ and $H$ have size $3$. Colour the edges of $K_{m}^{(3)}$ (the complete 3-uniform hypergraph on $m$ vertices) red and blue such that there is no monochromatic $K_{N}^{(3)}$. By classic results on lower bounds of Ramsey numbers, we may take $m >2^{cN^2}$, where $c$ is a positive constant. Let $G$ be the set of red edges, and $H$ be the set of blue edges. Suppose there is a distinguisher $K$ of $G$ and $H$ with $|K| \leq N$. Since the atoms of $K$ also distinguish $G$ and $H$, there is a distinguisher $K'$ of $G$ and $H$ which is a partition of $[m]$ and $|K'| \leq 2^N$. By averaging, some set $A \in K'$ has at least $\frac{m}{2^N} > N$ vertices. Since there is no monochromatic $K_{N}^{(3)}$, there must be some red edge $R$ and some blue edge $B$ with $R \subseteq A$ and $B \subseteq A$. Since $K'$ is a partition of $[m]$, it follows that $K'$ does not distinguish $R$ and $B$, which is a contradiction.

Answer 3

Here is a simple argument (simpler than other answers so far) that the answer to Q2 is negative — specifically, that for any $\newcommand{\l}{\ell}\l \geq 2$ and any $N\!$, there are disjoint families $G$, $H$ of sets of size $\l$ (“$\ell$-sets”) such that any distinguisher for $G$ and $H$ has size $\geq N\!$.

Our first goal will be: Find disjoint families $G$ and $H$ of $\ell$-sets such that for each edge $(i,j)$ of the complete graph $K_{2^N}$, $G$ and $H$ contain a pair of sets $g_{i,j}$, $h_{i,j}$ differing only in replacing $i$ with $j$.

For this, write $M = 2^N$; now take the “ambient set” $U$ from which $G$, $H$ are drawn to consist of $[M] \cup S \cup T$, where $[M] = \{1, \ldots, M\}$, then $S$ is any set of size $\binom{M}{2}$ disjoint from $\{1, \ldots M\}$, and $T$ is any set of size $\l - 2$ disjoint from $[M] \cup S$. Write the elements of $S$ as $(s_{i,j})_{1 \leq i < j \leq M}$. (So for concreteness, $U$ could be $[M + \binom{M}{2} + (\l-2)]$.) Now take:

\begin{align*} g_{i,j} &= T \cup \{ s_{i,j} \} \cup \{i\} \quad \text{(for each $0 \leq i < j \leq M$)}\\ h_{i,j} &= T \cup \{ s_{i,j} \} \cup \{j\} \\ G & = \{ g_{i,j} \mid 0 \leq i < j \leq M \} \\ H & = \{ h_{i,j} \mid 0 \leq i < j \leq M \} \\ \end{align*}

This achieves the first goal: $S$ serves to keep $G$, $H$ disjoint, while $T$ brings their members up to size $\l$.

Now, I claim any distinguisher $D$ for $G$, $H$ must have size $\geq N$. Given such $D$, take $D' = \{ s \cap [M] \mid s \in D\}$; clearly $|D'| \leq |D|$, and $D'$ must still distinguish each pair $(g_{i,j},h_{i,j})$, since these differ only within $[M]$, so if some $s \in D$ distinguishes them, so does $s \cap [M]$. So in the partition of $[M]$ induced by all Boolean combinations of sets of $D'$, all classes must be singletons — otherwise if $i \neq j$ were in the same class, $D'$ wouldn’t distinguish $g_{i,j}$ from $h_{i,j}$. But there are at most $2^{|D'|}$ classes in this partition; so $2^{|D'|} \geq M = 2^N$, so $N \leq |D'| \leq |D|$ as desired.

This completes the proof: we have families $G$, $H$ of $\l$-sets (with $|G| = |H| = \binom{2^N}{2}$) for which any distinguisher must have size $\geq N$.

The size of the ambient set $U$ can be easily tightened up a bit by replacing $S \cup T$ above with a single set $S$ such that $\binom{S}{\ell-1} \geq \binom{M}{2}$, and taking $g_{i,j} = s_{i,j} \cup \{i\}$, $h_{i,j} = s_{i,j} \cup \{j\}$ for distinct sets $s_{i,j} \subseteq S$. I don’t see any such easy way to reduce the sizes of $G$ and $H$, but I’m sure that can be done.

Answer 4

Here's a messier but more elementary negative response to Question 2. First note that instead of taking $K$ to be an algebra of sets in the question, we can take $K$ to be a partition of $X = \bigcup(G\cup H)$, since if an algebra distinguishes two sets, the set of its atoms does as well. Second, note that we can weaken the definition of distinguishing to require only that $|A\cap B|\ne |A\cap C|$: call this quantitative distinguishing.

Suppose $2M\ge N+1$. Let $\scr K$ be the set of all partitions $K$ of $[2M]$ with the following properties: (a) all but one cell of $K$ is a singleton and (b) the one remaining cell has two elements. Any partition $K'$ of $[2M]$ of cardinality at most $N$ can be refined to a partition in $\scr K$.

For each subset $B$ of $[2M]$ of cardinality $M$, with equal probability and independently choose whether $B$ goes into the random set $F$ or the random set $G$.

I claim that the probability that $\scr K$ quantitatively distinguishes $F$ from $G$ converges to zero as $M\to\infty$.

Given $K\in\scr K$, let $a_1,...,a_{2M}$ be an enumeration of $[2M]$ such that $A=\{ a_1,a_2 \}$ is a cell of $K$ (choose this enumeration in some precise way for each $K$). Let ${\scr B}_K$ be the collection of all $B\subseteq[2M]$ such that exactly one member of each pair $a_{2k-1}$ and $a_{2k}$ is in $B$ for $k\in [M]$. Let $B^*=(B^c \cap A) \cup (B\backslash A) \in {\scr B}_K$. Then $K$ does not quantitatively distinguish $B$ and $B^*$ and $|B|=|B^*|=M$.

The probability that exactly one of $B$ and $B^*$ is in $F$ is $1/2$, in which case $K$ fails to quantitatively distinguish $F$ and $G$. Thus, the probability that $K$ quantitatively distinguishes $F$ and $G$ is at most $2^{-|{\scr B}_K|/2}=2^{-2^{M-1}}$. Thus, the probability that $\scr K$ quantitatively distinguishes $F$ and $G$ is at most $|{\scr K}| \cdot 2^{-2^{M-1}}=2N \cdot 2^{-2^{M-1}}$, which goes to zero for fixed $N$ as $M\to\infty$.