Double counting |

Double counting is a simple yet so powerful way to prove non-trivial theorems. Here, we present some applications of the double counting principle. Our main source is the excellent book “Extremal Combinatorics” by Stasys Jukna [1]. A newer edition from the one in the picture (which shows the book I have) is also available now.

Basic idea: Let $M$ be a 0/1 matrix. Then the number of 1s (and of course of 0s) can be counted in two ways: A) Count for each row the number of 1s and sum over all rows. (B) Count for each column the number of 1s and sum over all columns.

Let’s start first with a basic double counting argument, known as the handshaking lemma.

Handshaking lemma: At a party the number of guests who shake hands an odd number of times is even.

Proof: Let $n,m$ be the number of guests and the number of pairs of guests who gave their hands respectively. Now let’s define a matrix $M$ which is $n \times m$ and its (i,j)-th entry is 1 if guest i is one of the two people in the j-th pair, otherwise it is 0. Now double count the number of ones. For convenience let’s call $deg(i)$ the number of times guest $i$ shook his hand with someone else in the party. Clearly double counting the number of 1s gives $\sum_{i=1}^n deg(i) = 2m$ . The 2 in the righthandside is because the number of ones per column is 2. Now let’s break the lefthandside $\sum_{i:deg(i)=odd} deg(i)=2m-\sum_{i:deg(i)=even} deg(i)$ . We observe that the righthandside is definitely an even number and the lefthandside is a sum of odd numbers. In order to be even the number of summands has to be even! This means in terms of the party, the number of guests who shake hands an odd number of times is even. QED

Well that was easy. But never forget one of the teachings of the Aesop’s fables (never underestimate the power of something “small”). Let me solve a riddle which I had given you some weeks ago.

Riddle of December 2nd: You can always find in a simple undirected graph $G$ of minimum degree $\delta$ two spanning edge disjoint subgraphs of minimum degree at least $\lfloor \frac{\delta-1}{2} \rfloor$ . Give also an algorithmic procedure to find such subgraphs.

Proof Sketch: Well, we know from the handshaking lemma that the number of vertices with odd degree is even. Let’s add a matching to make each vertex have an even degree. The resulting graph is Eulerian. Color the edges incident to any vertex in a fair way. This gives you the result. Argue why. QED

Let’s now move to some a generalization of the handshaking lemma. Specifically, the lemma in terms of graphs tells us that the sum of degrees is equal to 2 times the number of edges. What about hypergraphs . Hypergraphs again have a set of vertices but edges may consist of more than two vertices. By double counting we obtain the following lemma.

Hypergraph handshaking lemma: Let $\mathcal{F}=\{A_1,\ldots,A_m\}$ be the edge set of a hypergraph $H$ on the vertex set $[n]$ . Then, $\sum_{x \in [n]} deg(x) = \sum_{ A \in \mathcal{F}} |A|$ .

Exercise 1 (eq. 1.8, Jukna, p.16): Let’s play further. Fix a subset $Y \subseteq [n]$ . Let’s prove $\sum_{x \in Y} deg(x) = \sum_{A \in \mathcal{F}} |Y \cap A|$ .

Proof: $\sum_{x \in Y} deg(x)=\sum_{x \in Y}\sum_{A \in \mathcal{F}} 1(x \in A)=\sum_{A \in \mathcal{F}}\sum_{x \in Y} 1(x \in A)=$

$\sum_{A \in \mathcal{F}}\sum_{x \in [n]} 1(x \in A \cap Y)=\sum_{A \in \mathcal{F}} |A \cap Y|$ QED.

Exercise 2 (eq. 1.9, Jukna, p.16): Let’s play even further. Let’s prove $\sum_{x \in Y} deg(x)^2 = \sum_{A \in \mathcal{F}}\sum_{x \in A} deg(x)=\sum_{A \in \mathcal{F}}\sum_{B \in \mathcal{F}} |A \cap B|$ .

Proof: $\sum_{x \in [n]}deg(x)^2=\sum_{x \in [n]}deg(x)*deg(x)=\sum_{x \in [n]}deg(x)\sum_{A \in \mathcal{F}} 1(x \in A)$

$\sum_{A \in \mathcal{F}} \sum_{x \in [n]}deg(x)1(x \in A)=\sum_{A \in \mathcal{F}}\sum_{x \in A} deg(x).$

I guess you have got the point: indicator variables, exchange summation order. Let’s do the last part of this exercise.

$\sum_{A \in \mathcal{F}}\sum_{B \in \mathcal{F}} |A \cap B|=\sum_{A \in \mathcal{F}}\sum_{B \in \mathcal{F}}\sum_{x \in [n]} 1(x \in A) \times 1(x \in B)=$

$\sum_{x \in [n]} (\sum_{A} 1(x \in A))(\sum_{B} 1(x \in B))=\sum_{x \in [n]} deg(x)^2.$

QED

Now let’s move to a graph theory exercise which nicely illustrates the double counting idea.

Problem: Let $G(A \cup B, E)$ be a bipartite graph with the following property: for any edge $(a,b)$ where $a \in A,b \in B$ , $deg(a) \geq deg(b)$ . Then $|A|\leq |B|$ .

Proof:

$|A|=\sum_{a \in A} deg(a) \frac{1}{deg(a)}=\sum_{a \in A}\frac{1}{deg(a)}\sum_{b \in B}1(ab \in E(G))\leq$

$\sum_{a \in A}\sum_{b \in B} 1(ab \in E(G))\frac{1}{deg(b)}=\sum_{b \in B}\frac{1}{deg(b)}\sum_{a \in A} 1(ab \in E(G))$

$=\sum_{b \in B} 1=|B|.$ QED

Pál Turán

Now, I will move to more interesting exercises. Let’s start by Turán’s number $T(n,k,l)$ which is defined as the smallest number of $l$ -element subsets such that any $k$ -element subset of [n] contains at least one of these sets.

Exercise 3 (See Proposition 1.8, Jukna p.16): $T(n,k,l) \geq \frac{{n \choose l}}{{k \choose l}}$ .

Proof 1: We will double count the number of 1s of an appropriately defined matrix $M$ . Let $\mathcal{F}$ be the smallest $l$ -uniform family that has the Turán property. Let $M$ be a $|\mathcal{F}| \times {n \choose k}$ matrix where its (i,j)-th entry is 1 if the i-th member of $\mathcal{F}$ is contained in the j-th k-element subset of [n]. Clearly from a fixed element subset we can create ${n-l \choose k-l}$ k-element subsets. This suggests that there are ${n-l \choose k-l}$ 1s per row. Furthermore, by the Turán property each column has at least one 1. Therefore $|F|{n-l \choose k-l} \geq {n \choose k}$ which gives our theorem. QED

Proof 2: Turn proof 1 in a probabilistic proof using a first moment argument.

Exercise 4 (See Exercise 1.22, Jukna p.22): Let $\mathcal{F}$ be a family of $k$ -element subsets of [n] such that every $l$ -element subset is contained in at least one member of $\mathcal{F}$ . What can you say about the size of $\mathcal{F}$ using the previous exercise as your guide?

Proof: We define $M$ as a $|\mathcal{F}| \times {n \choose l}$ matrix where the (i,j)-th entry is an indicator variable of whether the $i$ -th member of $\mathcal{F}$ contains the $j$ -th $l$ -element subset. Clearly again by double counting the number of 1s we obtain the following lower bound $|\mathcal{F}| {k \choose l} \geq {n \choose l}$ . Hence, $latex |\mathcal{F}|\geq\frac{{n \choose l}}{{k \choose l}}$.

Now, let’s have a look at the shadow of a family of sets. It is an important concept that appears a lot in extremal combinatorics.

Exercise 5 (See Exercise 1.23, Jukna p.22): Let $\mathcal{F}$ be a family of $k$ -element subsets of [n]. Its shadow is the family of all those $(k-1)$ -element subsets which lie entirely in at least one member of $\mathcal{F}$ . Show that the shadow $\mathcal{S}_{\mathcal F}$ satisfies $|\mathcal{S}_{\mathcal F}| \geq \frac{k|\mathcal{F}|}{n-k+1}$ .

Proof: Let’s create a matrix $M$ with $|\mathcal{S}_{\mathcal F}|$ rows and $|\mathcal{F}|$ columns. We will place a 1 in its (i,j)-th entry if the $i$ -th element of the shadow is a subset of the $j$ -th element of $\mathcal{F}$ , otherwise we will place a 0. Now let’s double count the 1s. Clearly each column contains $k$ ones. Furthermore, each row contains at most $n-k+1$ 1s, i.e., it can be generated from $n-k+1$ $k$ -element subsets. Therefore, $k|\mathcal{F}|=\sum_{A \in \mathcal{S}_{\mathcal F}} deg(A)\leq (n-k+1)|\mathcal{S}_{\mathcal F}|$ . QED

Finally, I will conclude with a neat lemma, known as the Corrádi lemma. From Google scholar I get the feeling it was posted in a math competition in Hungary, see [2]. Before going into the statement and the proof of the lemma, three things. (1) Hungary has a lot of talent in discrete math. (2) The beauty of the lemma and all the above exercises is that -in my opinion- they can be solved from a smart high school student. (3) Try to solve it on your own to verify you have mastered double counting :-). In case you have no experience in extremal combinatorics, it will be on of your first steps teaching you also a useful technique.

Corrádi’s Lemma (See Lemma 2.1, Jukna p.23): Let $A_1,\ldots,A_N$ be $r$ -element sets and $X$ be their union. If $|A_i \cap A_j| \leq k$ for all $i \neq j$ then $|X| \geq \frac{r^2N}{r+(N-1)k}$ .

This is the problem of the day for you.

[1] Extremal combinatorics, Stasys Jukna.

[2] Problem at Schweitzer competition, Corrádi

Tags: double counting, extremal combinatorics, Jukna book

One comment

Ahlswede-Zhang identity | Lasting Gems · December 29, 2011 - 5:13 AM · Reply→

[…] Before we see it though let us see the rationale behind it. We may rewrite . This suggests that a double counting argument of permutations may turn out to be of use to us. […]

Double counting

One comment

Leave a Reply Cancel reply

Follow webpage via email

Double counting

Share this:

Like this:

One comment

Leave a Reply Cancel reply

Follow webpage via email