Uniformly at Random

Archive for January 2009

The greatest generals of antiquity

leave a comment »

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

leave a comment »

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

leave a comment »

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 ,