19
$\begingroup$

I've just come across this proof of the Graham-Pollak Theorem by Sundar Vishwanathan (thanks to Konrad Swanepoel's sporadic comments about it on this site), that must be called beautiful after its author. The paper mentions (after lemma 3) that certain other linear algebra proofs can also be replaced by similar pigeonhole principle applications. But I couldn't find any, so I thought that we should collect some similar beautiful proofs here. I don't mind if it also uses parity or other tricks, but linear algebra should be replaced! For example, can anyone prove the Oddtown theorem?

$\endgroup$
3
  • 2
    $\begingroup$ Possibly related: cstheory.stackexchange.com/questions/5099/… $\endgroup$ Feb 11, 2016 at 22:41
  • $\begingroup$ Is it possible that there might be some kind of shifting-type proof of Oddtown? $\endgroup$ Feb 15, 2016 at 15:37
  • $\begingroup$ What about the "lights out" theorem, which says that for every finite graph $G$ there is a set $S\subseteq V(G)$ such that $|N[v]\cap S|$ is odd for every $v\in V(G)$? The special case where $G$ is a tree has an easy proof without linear algebra. Is there a graph-theoretical proof of the general result? $\endgroup$
    – bof
    Feb 5, 2021 at 22:15

5 Answers 5

20
$\begingroup$

What essentially happens in this proof? We repeat the usual proof, but replace the fundamental linear algebraic theorem

$n$ vectors in $K^{n-1}$ are linearly dependent over $K$

for $K=\mathbb{Q}$ by its counting proof.

Let me give here the proofs for finite $K$ and for $K=\mathbb{Q}$ explicitly. Let $v_1,\dots,v_n$ be vectors in $K^{n-1}$, we need to find their linear dependence.

  1. $K$ is finite, $|K|=q$. There exist $q^n$ linear combinations of $v_1,\dots,v_n$, which take only $q^{n-1}$ values. Two of them are equal by pigeonhole principle, that's what we need.

  2. The same trick works for $\mathbb{Q}$, it is essentially noted by Sundar Vishwanathan. Choose at first a positive integer $N$ such that $u_i:=Nv_i\in \mathbb{Z}^{n-1}$. Then denote by $M$ the maximum of absolute values of coordinates of $u_1,\dots,u_{n}$. Consider all $(K+1)^n$ linear combinations $c_1u_1+\dots+c_n u_n$, where $c_i\in \{0,1,\dots,K\}$. They belong to the set $\{-nMK,-nMK+1,\dots,nMK-1,nMK\}^{n-1}$. So, if $(2nMK+1)^{n-1}<(K+1)^n$ (true for large $K$), by the pigeonhole principle there are two equal values of linear combinations, hence $u_1,\dots,u_n$ are linearly dependent with integer coefficients, as desired.

Applications of linear algebra in combinatorics often use this fundamental theorem either over finite fields, like in the Oddtown theorem (where the same counting argument works even easier) or over $\mathbb{Q}$. I think, we really need $\mathbb{R}$ or $\mathbb{C}$ only when we come to eigenvalues.

Say, the counting proof of Oddtown sounds as this:

Let $\mathcal{F}$ be a collection of subsets of $\{1,\dots,n\}$, $|{\mathcal F}|\geqslant n+1$. We consider all $2^{n+1}$ subcollections of ${\mathcal F}$. For each such subcollection $A$ consider the symmetric difference of $A$ (that is, the set of $x\in \{1,\dots,n\}$, which belong to odd number of sets from $A$.) Some two symmetric differences, say of $A$ and $B$ coincide by pigeonhole principle. Hence the symmetric difference of $C:=A\Delta B$ is empty set, i.e. each $x$ belong to even number of sets from $C$. Now let $C=\{U_1,\dots,U_k\}$. Then we use double counting: $$ \sum_{i=2}^k |U_i\cap U_1|=\sum_{x\in U_1}\sum_{i=2}^k \chi_{U_i}(x)\equiv |U_1| \pmod 2, $$ hence if $|U_1|$ is odd, at least one intersection $|U_i\cap U_1|$ has also odd size.

It is the usual proof with counting argument of linear dependence incorporated.

$\endgroup$
4
  • 1
    $\begingroup$ So, do you have a proof of the Oddtown thm then? $\endgroup$
    – domotorp
    Feb 12, 2016 at 1:35
  • 2
    $\begingroup$ Yes, take usual proof and insert the proof of linear dependence of $n+1$ vectors in ${\mathbb F}_2^n$ by the above counting argument. $\endgroup$ Feb 12, 2016 at 6:03
  • $\begingroup$ Nice! Then could you redo the entire Babai-Frankl book in a similar fashion? $\endgroup$
    – domotorp
    Feb 12, 2016 at 12:23
  • $\begingroup$ Possibly. I have to look into at least. $\endgroup$ Feb 12, 2016 at 12:32
3
$\begingroup$

Perhaps the Mertzios–Unger proof of the friendship theorem counts as an example.

$\endgroup$
4
  • $\begingroup$ Nice proof, but it seems to be almost identical to the proof of Humke from earlier that it cites in the intro: researchgate.net/publication/268313555_The_Friendship_Theorem $\endgroup$
    – domotorp
    Feb 12, 2016 at 14:49
  • $\begingroup$ @domotorp By the way I think that by "Humke" you meant Huneke. $\endgroup$
    – bof
    Feb 5, 2021 at 10:14
  • $\begingroup$ @bof Indeed, thanks! My comment is too old to edit it. $\endgroup$
    – domotorp
    Feb 5, 2021 at 12:53
  • $\begingroup$ @bof Sure, it can be. $\endgroup$
    – domotorp
    Feb 6, 2021 at 8:54
2
$\begingroup$

Theorem. Let $A$ and $B$ be families of subsets of $[n]$, such that for all $a \in A$ and $b \in B$, $|a \cap b|$ is odd. Then $|A||B| \leq 2^{n-1}$.

I will present two proofs of this theorem. One just uses linear algebra, while the other is a counting proof. Unfortunately, I could not completely eliminate linear algebra from the second proof, but the main trick is to use inclusion-exclusion.

Linear Algebra Proof. For each $a \in A$, we let $\mathbb{a}$ be its binary characteristic vector. Let $(\mathbb{A},\mathbb{B}) \subset \mathbb{F}_2^{2n}$ be the subspace spanned by all vectors of the form $(\mathbb{a}, \mathbb{b})$, where $a \in A$ and $b \in B$. Let $(\mathbb{B}, \mathbb{A})$ be the subspace spanned by all vectors of the form $(\mathbb{b}, \mathbb{a})$, where $a \in A$ and $b \in B$. If $\dim((\mathbb{A},\mathbb{B}))$ or $\dim((\mathbb{B}, \mathbb{A}))$ is at most $n-1$, then we are done.
By construction, the inner product $\langle \mathbf{x}, \mathbf{y} \rangle$ is $0$ for all $\mathbf{x} \in (\mathbb{A},\mathbb{B})$ and $\mathbf{y} \in (\mathbb{B}, \mathbb{A})$. Thus, we are done unless $\dim((\mathbb{A},\mathbb{B}))=\dim((\mathbb{B}, \mathbb{A}))=n$. Choose $a_1, \dots, a_n \in A$ and $b_1, \dots, b_n \in B$ such that $X=\{(\mathbb{a_1}, \mathbb{b_1}), \dots, (\mathbb{a_n}, \mathbb{b_n})\}$ is a basis for $(\mathbb{A},\mathbb{B})$. Observe that every even sum of vectors in $X$ is not of the form $(\mathbb{a}, \mathbb{b})$, where $a \in A$ and $b \in B$. Since exactly half the vectors in $(\mathbb{A},\mathbb{B})$ are even sums of vectors in $X$, $|A||B| \leq 2^{n-1}$, as required.

Counting Proof. Let $\mathbb{A}$ be the subspace generated by $A$. Suppose $\dim(\mathbb{A})=k$. By the even sum trick, this implies $|A| \leq 2^{k-1}$. It suffices to show that $|B| \leq 2^{n-k}$. Choose $a_1, \dots, a_k \in A$ such that $\mathbb{a_1}, \dots, \mathbb{a_k}$ is a basis for $\mathbb{A}$. Observe that $$ |B| \leq 2^n-\bigcup_{i=1}^k \mathbb{a_i}^\perp, $$ where $\mathbb{a_i}^\perp$ is the set of vectors orthogonal to $\mathbb{a_i}$. By inclusion-exclusion, we have $$ 2^n-\bigcup_{i=1}^k \mathbb{a_i}^\perp=2^n-k2^{n-1}+\binom{k}{2}2^{n-2}-\binom{k}{3}2^{n-3}+\dots=2^{n-k}, $$ where the last equality follows from the binomial theorem.

$\endgroup$
3
  • $\begingroup$ You're proving the wrong theorem: exwiki.org/mw/index.php?title=The_Oddtown_theorem $\endgroup$
    – domotorp
    Feb 12, 2016 at 1:32
  • $\begingroup$ I know the Oddtown theorem, but I do not know a non-(linear algebra) proof of it. I am not sure my example is what you are looking for either since the second proof still uses linear algebra. But it certainly is a 'counting' proof I feel. $\endgroup$
    – Tony Huynh
    Feb 12, 2016 at 2:18
  • 1
    $\begingroup$ This somewhat reminded me the AMM problem 11666 of Fon-Der-Flaass and myself. $\endgroup$ Feb 12, 2016 at 19:03
1
$\begingroup$

Another example is the proof of the friendship theorem of graph theory by Judith Q. Longyear and T. D. Parsons, The Friendship Theorem, Indag. Math. 75 (1972), 257–262.. Craig Huneke's combinatorial proof (The friendship theorem, Amer. Math. Monthly 109 (2002), 192–194; added note, Amer. Math. Monthly 110 (2003), 79) may be presented more elegantly, but I believe it's essentially the same argument.

$\endgroup$
-4
$\begingroup$

Check the book Linear Algebra methods in combinatorics by Babai and Frankl. The first theorem he proves in the book is the oddtown theorem, it follows the lines of the proofs others have presentes here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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