4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ What set do you mean by [n]? $\endgroup$ – Adam Nov 10 '13 at 22:09
  • $\begingroup$ Traditionally in combinatorics, $[n]:=\{1,\ldots,n\}$, and $|S|=\text{cardinality}(S)$ $\endgroup$ – Stromael Nov 10 '13 at 22:33
  • $\begingroup$ Have you tried using induction? $\endgroup$ – Adam Nov 10 '13 at 22:52
  • $\begingroup$ 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. $\endgroup$ – Stromael Nov 10 '13 at 23:34
3
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ I really like that reformulation. Linear algebra fixes everything. (Minor nitpick: saying "inner product" is perhaps misleading, but it's bilinear in any case.) $\endgroup$ – J Swanson Dec 30 '13 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.