# Uniformly at Random

## The greatest generals of antiquity

The following anecdote concerning the meeting of Hannibal of Carthage and the elder Scipio Africanus at Ephesus some years after their famous campaigns against each other in the Second Punic War is well-known. This version of the story is from Appian’s History of the Syrian Wars.

It is said that at one of their meetings in the gymnasium Scipio and Hannibal had a conversation on the subject of generalship, in the presence of a number of bystanders, and that Scipio asked Hannibal whom he considered the greatest general, to which the latter replied, “Alexander of Macedonia.”

To this Scipio assented since he also yielded the first place to Alexander. Then he asked Hannibal whom he placed next, and he replied, “Pyrrhus of Epirus,” because he considered boldness the first qualification of a general; “for it would not be possible,” he said, “to find two kings more enterprising than these.”

Scipio was rather nettled by this, but nevertheless he asked Hannibal to whom he would give the third place, expecting that at least the third would be assigned to him; but Hannibal replied, “To myself; for when I was a young man I conquered Spain and crossed the Alps with an army, the first after Hercules. I invaded Italy and struck terror into all of you, laid waste 400 of your towns, and often put your city in extreme peril, all this time receiving neither money nor reinforcements from Carthage.”

As Scipio saw that he was likely to prolong his self-laudation he said, laughing, “Where would you place yourself, Hannibal, if you had not been defeated by me?” Hannibal, now perceiving his jealousy, replied, “In that case I should have put myself before Alexander.” Thus Hannibal continued his self-laudation, but flattered Scipio in a delicate manner by suggesting that he had conquered one who was the superior of Alexander.

Written by uncudh

January 27, 2009 at 4:42 pm

Posted in history

Tagged with , , ,

## The Erdos-Ginzburg-Ziv Theorem

with one comment

Here we present a proof of the Erdos-Ginzburg-Ziv Theorem. We shall deduce this result using the Cauchy-Davenport Theorem, which in turn can be derived from Noga Alon’s Combinatorial Nullstellensatz. We begin by stating without proof the Combinatorial Nullstellensatz.

Combinatorial Nullstellensatz. Let $f$ be a polynomial over a field $K$ in the variables ${\bf x} = (x_1,\ldots,x_n)$. Suppose that the total degree of $f$ is $\sum_{i=1}^n d_i$ and that the coefficient in $f$ of $\prod_{i=1}^n x_i^{d_i}$ is non-zero. For $i = 1,\ldots,n$, let $L_i$ be a set of $d_i + 1$ elements of $K$. Then there exists ${\bf t} \in L_1 \times \cdots \times L_n$ such that $f({\bf t}) \neq 0$.

We wish to deduce the following classical theorem, following the proof of Noga Alon in his paper “Combinatorial Nullstellensatz”.

Theorem (Cauchy-Davenport). Let $p$ be a prime and let $A,B$ be subsets of $Z_p$. Then either $A+B = Z_p$ or $|A+B| \geq |A|+|B|-1$.

Proof. We first observe that if $|A|+|B| > p$, then for every $c \in Z_p$ we have $|A|+|c-B| > p$, so that $A \cap (c-B)$ is non-empty. This implies that $c$ can be written as the sum of elements $b \in B$ and $c-b \in A$. Since this holds for all $c \in Z_p$ we have $A+B = Z_p$, as required.

Suppose now that $|A|+|B| \leq p$ and that $|A+B| \leq |A|+|B|-2$, contrary to the claimed result. Let $C$ be any subset of $Z_p$ of size $|A|+|B|-2$ containing $A+B$. Define a polynomial $f(x,y) = \prod_{c \in C} (x+y-c)$. Clearly, $f(a,b)=0$ for all $(a,b) \in A \times B$. Moreover, the coefficient of $x^{|A|-1}y^{|B|-1}$ in $f$ equals ${|A|+|B|-2 \choose |A|-1}$, and is therefore non-zero in $Z_p$, since $|A|+|B|-2 < p$. Applying the Combinatorial Nullstellensatz to $f$, we conclude that there exists $(a,b) \in A \times B$ such that $f(a,b) \neq 0$, contradicting our earlier observation. This contradiction establishes the desired result.

This result can also be proved directly by induction on the size of $B$. Using the Cauchy-Davenport Theorem we now show the following result, following the presentation of Alon and Dubiner.

Theorem (Erdos-Ginzburg-Ziv). Let $n\geq 2$ be an integer. For any sequence $a_1,\ldots,a_{2n-1}$ of (not necessarily distinct) elements of $Z_n$, there exists a set $I \subseteq \{1,\ldots,2n-1\}$ of size $n$ such that $\sum_{i\in I} a_i = 0$ (in $Z_n$).

Proof. The proof is by induction on the number of primes in the prime factorization of $n$. Suppose that the result holds for prime $n$ and now consider $n = pm$ for some prime $p$ and some integer $m > 1$. Consider any $2p-1$ element subsequence of $a_1,\ldots,a_{2pm-1}$; by the claimed result for prime values, this $2p-1$ element subsequence contains $p$ elements whose sum is a multiple of $p$. We can therefore remove this $p$ element subsequence and repeat the argument to obtain disjoint sets $I_1,\ldots,I_{2m-1} \subseteq \{1,\ldots,2pm-1\}$ such that for $i=1,\ldots,m$, $|I_i| = p$ and $\sum_{j\in I_i} a_j$ is a multiple of $p$. For $i=1,\ldots,2m-1$, define $a_i' = \sum_{j\in I_i} a_j/p$. We now apply the induction hypothesis to the sequence $a_1',\ldots,a_{2m-1}'$ to conclude that there exists $J \subseteq \{1,\ldots,2m-1\}$ of size $m$ such that $\sum_{j\in J} a_j'$ is a multiple of $m$. This implies that if $I = \cup_{j\in J} I_j$, then $|I| = pm = n$ and $\sum_{i\in I} a_i$ is a multiple of $pm = n$, as required.

It remains now to establish the base case of the induction, namely the case when $n$ equals a prime $p$. Suppose that $a_1 \leq \cdots \leq a_{2p-1}$. If for some $i$ we have $a_i = a_{i+p-1}$, then $a_i = \cdots = a_{i+p-1}$ so that $a_i + \cdots + a_{i+p-1} = pa_i$ is a multiple of $p$ and we are done. Suppose then that for $i=1,\ldots,p-1$, $a_i \neq a_{i+p-1}$, and define sets $A_i = \{a_i,a_{i+p-1}\}$. By repeated application of the Cauchy-Davenport Theorem, we see that $|A_1 + \cdots + A_{p-1}| = p$. Thus every element of $Z_p$ can be written as a sum of exactly $p-1$ elements of our sequence. In particular, $-a_{2p-1}$ can be so written, so that $a_{2p-1}$, taken together with the $p-1$ elements of our sequence that sum to $-a_{2p-1}$, gives a $p$ element subsequence whose sum is 0 in $Z_p$, as required. This completes the proof.

Written by uncudh

January 25, 2009 at 3:29 am

Posted in math

Tagged with

## I am An-ti-‘u-ku-us

The following is an inscription, originally in Akkadian, from the reign of Antiochus I Soter, second king of the Seleucid Empire (see Nicholas Ostler, Empires of the Word).  The incongruity of a Greek ruler describing himself in such a way (not to mention in Akkadian!)  is remarkable.

I am An-ti-‘u-ku-us [Antiochus], the great king, the legitimate king, the king of the world, king of E [Babylon], king of all countries, the caretaker of the temples Esagila and Ezida, the first born of Si-lu-uk-ku [Seleucus], Ma-ak-ka-du-na-a-a [Macedonian], king of Babylon.

Written by uncudh

January 25, 2009 at 1:24 am

Posted in history

Tagged with , , ,

## Even cycles in directed graphs

Here is a nice application of the Lovasz Local Lemma, due to Alon and Linial, whereby it is proved that for sufficiently large $k$, a $k$-diregular directed graph has an directed even cycle.

Theorem [Lovasz Local Lemma (symmetric version)] Let $G = (V,E)$ be a dependency graph for events $A_1,\ldots,A_n$. Suppose that the maximum degree of $G$ is $d$ and that there is a real number $p$ for which $\Pr[A_i] \leq p$ for all $i=1,\ldots,n$. If $4pd \leq 1$, then $\Pr[\cap\overline{A_i}] > 0$.

In the statement above, the vertices of $G$ consist of $V = {1,\ldots,n}$ and $A_i$ is mutually independent of all the $A_j$‘s for which there is no edge ${i,j}$ in $E$.

Theorem [Alon and Linial] Let $k \geq 8$ and let $G$ be a directed graph where every vertex has indegree and outdegree $k$. Then $G$ has a directed even cycle.

Proof. Consider a random 2-colouring of the vertices of $G$. For each vertex $v$ of $G$, let $A_v$ denote the event that $v$ and all of its outneighbours have the same colour. Then $p = \Pr[A_v] = 2^{-k}$. Moreover, $A_v$ is independent of all $A_u$ for which neither $u$ nor any outneighbour of $u$ is an outneighbour of $v$. However, each of the $k$ outneighbours of $v$ has indegree $k$, so we may apply the local lemma with $d = k^2$. For $k \geq 8$, we have $4\cdot 2^{-k}k^2 \leq 1$, so with positive probability, every vertex of $G$ has an outneighbour of the opposite colour.

Now let $P$ be a maximal properly 2-coloured directed path in $G$, ending at a vertex $v$. Let $w$ be any outneighbour of $v$ coloured differently from $v$. By the maximality of $P$, $w$ must lie on $P$ itself. Thus the cycle obtained by starting at $w$, following $P$ to $v$, and then returning to $w$ via the edge $(v,w)$, is a properly 2-coloured cycle, and hence, even. This completes the proof.

Written by uncudh

January 7, 2009 at 5:57 pm

Posted in math

Tagged with ,