I have been stuck on the following for a while. Earlier parts of the question proved a few results that I think may be applicable.

Earlier Proven Results:

  1. Suppose $A_1, A_2 , ... , A_k $ and $B_1 , B_2, ... , B_k$ are subsets of $[n]$ such that $|A_i \cap B_i|$ is even for all $i$ and $|A_i \cap B_j|$ is odd for all $j\not=i $. Then $k \leq n$

  2. The 'Two Families Theorem'.

The questions

  1. Let $\mathcal{A} , \mathcal{B} $ be two subsets of $\mathcal{P}(n) $ such that $|A\cap B| $ is even for all $A \in \mathcal{A} $, and $B \in \mathcal{B} $. Prove that $|\mathcal{A}| |\mathcal{B} | \leq 2^n $
  2. Let $\mathcal{A} , \mathcal{B} $ be two subsets of $\mathcal{P}(n) $ such that $|A\cap B| $ is odd for all $A \in \mathcal{A} $, and $B \in \mathcal{B} $. Prove that $|\mathcal{A}| |\mathcal{B} | \leq 2^{n-1} $

We were provided the following hint:
Fix $A_0\in\mathcal{A}$ and $B_0 \in \mathcal{B}$. Let $\mathcal{A}^{'}:= \{A\Delta A_0 :A \in \mathcal{A}\} $ and $\mathcal{B}^{'}:= \{B\Delta B_0 :B \in \mathcal{B}\} $
Then consider families of the form $\mathcal{A}^{'} $ or $\mathcal{A}^{'} \cup \mathcal{A} $

My attempts
I didn't really get the hint. I tried to arrive at a contradiction by assuming the sizes were larger than the bound and contradict the parity of the intersections. No success.


1 Answer 1


This is an attempt to answer question 1.

Without loss of generality we can assume that $\mathcal A$ and $\mathcal B$ are maximal, in particular they contain $\varnothing$.

From the hint, it follows that $A,A'\in\mathcal A$ then $A▵A'\in\mathcal A$ and the same for $\mathcal B$.

Then $\mathcal A$ and $\mathcal B$ are both subgroups of $\mathcal P(n)$ w.r.t. the group operation $\triangle$.

Assume for the moment that $\mathcal A\cap\mathcal B=\{\varnothing\}$.

Let $\mathcal C$ be the subgroup generated by $\mathcal A\cup\mathcal B$.

By basic group theory, $\mathcal C$ is isomorphic to $\mathcal A\times\mathcal B$.

Thererefore $|\mathcal A\times\mathcal B|\le |\mathcal P(n)|$ which proves the inequality in question 1.

Finally when $\mathcal A\cap\mathcal B$ is a non trivial subgroup of $\mathcal P(n)$, reason similarly in the quotient group.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .