Combinatorics intersecting sets question

Let $A_1 , . . . , A_m$ and $B_1 , . . . , B_m$ be subsets of $[n]$ such that $| A_i ∩ B_i |$ is odd for all $i$ and $| A_i ∩ B_j |$ is even for all $i \neq j$ . Show that $m ≤ n$.

I've tried using proof by contradiction but not success - any help greatly appreciated, thanks!

• What set do you mean by [n]?
Nov 10, 2013 at 22:09
• Traditionally in combinatorics, $[n]:=\{1,\ldots,n\}$, and $|S|=\text{cardinality}(S)$ Nov 10, 2013 at 22:33
• Have you tried using induction?
Nov 10, 2013 at 22:52
• The question essentially requires a suitable description of the size, modulo 2, of each $A_i\cap B_j,~(i,j\in[m])$. The combinatorial context suggests that a counting argument is applied to each such intersected pair. I'm no real combinatorics expert, however, so not sure how to take this much further immediately. Will think on it some more. Nov 10, 2013 at 23:34

The question looks like it's asking to be recast as a linear algebra problem. Consider the field with two elements, $\mathbb F_2$, and the vector space $\mathbb F_2^n$.

Interpret a subset $X$ of $[n]$ as the vector $x = (x_1, x_2, \ldots x_n)$ where $x_i$ is $1$ iff $i \in X$. Define the usual bilinear form $\langle \cdot \rangle : \mathbb F_2^n \times \mathbb F_2^n \to \mathbb F_2$:

$$\langle x , y \rangle = \sum_{i=1}^n x_iy_i$$

Let $X, Y \subseteq [n]$, and let their corresponding vectors in $\mathbb F_2^n$ be $x$ and $y$ respectively. Then $|X \cap Y|$ is even if and only if $\langle x, y \rangle = 0$.

Now consider the given $A_1, \ldots, A_m$ and $B_1, \ldots, B_m$. Let their corresponding vectors be $a_1, \ldots, a_m$ and $b_1, \ldots, b_m$. We know that for all $i,j$, we have $\langle a_i, b_j \rangle$ is $1$ if $i=j$ and $0$ otherwise.

Claim: $(a_1, \ldots, a_m)$ is linearly independent.

Proof: Suppose we have

$$s_1a_1 + s_2a_2 + \cdots + s_ma_m = 0$$

with each $s_i \in \mathbb F_2$. Then applying $\langle \cdot, b_i \rangle$ on both sides, we get $s_i = 0$. This holds for all $i$, and so the linear independence is established.

Since we have a linearly independent set of size $m$ in a vector space of dimension $n$, we get $m \leq n$.

• I really like that reformulation. Linear algebra fixes everything. (Minor nitpick: saying "inner product" is perhaps misleading, but it's bilinear in any case.) Dec 30, 2013 at 10:19