What is the maximal $k$ such that there exists $E_1,\cdots,E_k$, subsets of $\{1,\cdots,n\}$, such that $|E_i|$ is odd for every $i$ and $|E_i \cap E_j|$ is even for $i \neq j$?
The way I have tried to approach it is by induction over $n$ then over the size of the smallest of the $E_1, \cdots, E_k$. I have proven that $k\geq n$ and believe that $k=n$.
If there is a certain $E_i$ with only element, say $E_1 = \{n\}$ up to a reordering and permutation, then the rest of the subsets do not contain $n$, and therefore are a valid family of subsets for $n-1$.
If there is not, I have tried proving it for there being $E_1 = \{1,2,3\}$ (and therefore $n\geq 4$). This does not really lead me anywhere, only providing me with the fact that every other $E_i$ is either (exclusively):
- Included in $\{4,\cdots,n\}$
- A subset of $\{4,\cdots,n\}$ with $\{1,2\}$ added
- A subset of $\{4,\cdots,n\}$ with $\{2,3\}$ added
- A subset of $\{4,\cdots,n\}$ with $\{1,3\}$ added
This has not led me to much, other than showing that the elements that fall in the first bullet point cannot be the subset of $\{4,\cdots,n\}$ in the other bullet points.
This question can be solved by using adjacent matrix as is used in this answer.
It is easy to see that $k \geqslant n$ by taking $E_1 = \{1\}$, …, $E_n = \{n\}$. To prove $k \leqslant n$ by contradiction, suppose there exist $E_1, \cdots, E_{n + 1}$ satisfying the conditions. Define an $(n + 1) × n$ matrix $C = (c_{i, j})$ on $\mathbb{F}_2$ by$$ c_{i, j} = \begin{cases} 1; & j \in E_i\\ 0; & j \not\in E_i \end{cases}. $$ Because $|E_i| \equiv 1 \pmod{2}$ for all $i$ and $|E_i \cap E_j| \equiv 0 \pmod{2}$ for all $i ≠ j$, then on $\mathbb{F}_2$ there is$$ CC^T = \begin{pmatrix} |E_1| & |E_1 \cap E_2| & \cdots & |E_1 \cap E_{n + 1}|\\ |E_2 \cap E_1| & |E_2| & \cdots & |E_2 \cap E_{n + 1}|\\ \vdots & \vdots & \ddots & \vdots\\ |E_{n + 1} \cap E_1| & |E_{n + 1} \cap E_2| & \cdots & |E_{n + 1}| \end{pmatrix} = \begin{pmatrix} 1 & 0 & \cdots & 0\\ 0 & 1 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots & 1 \end{pmatrix}, $$ and the rank of $CC^T$ is $r(CC^T) = n + 1$. However, $r(CC^T) \leqslant \min(r(C), r(C^T)) \leqslant n$, a contradiction. Hence $k \leqslant n$.