## Archive for **January 2009**

## 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.

## The Erdos-Ginzburg-Ziv Theorem

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 be a polynomial over a field in the variables . Suppose that the total degree of is and that the coefficient in of is non-zero. For , let be a set of elements of . Then there exists such that .

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

**Theorem** (Cauchy-Davenport). Let be a prime and let be subsets of . Then either or .

*Proof*. We first observe that if , then for every we have , so that is non-empty. This implies that can be written as the sum of elements and . Since this holds for all we have , as required.

Suppose now that and that , contrary to the claimed result. Let be any subset of of size containing . Define a polynomial . Clearly, for all . Moreover, the coefficient of in equals , and is therefore non-zero in , since . Applying the Combinatorial Nullstellensatz to , we conclude that there exists such that , contradicting our earlier observation. This contradiction establishes the desired result.

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

**Theorem** (Erdos-Ginzburg-Ziv). Let be an integer. For any sequence of (not necessarily distinct) elements of , there exists a set of size such that (in ).

*Proof*. The proof is by induction on the number of primes in the prime factorization of . Suppose that the result holds for prime and now consider for some prime and some integer . Consider any element subsequence of ; by the claimed result for prime values, this element subsequence contains elements whose sum is a multiple of . We can therefore remove this element subsequence and repeat the argument to obtain disjoint sets such that for , and is a multiple of . For , define . We now apply the induction hypothesis to the sequence to conclude that there exists of size such that is a multiple of . This implies that if , then and is a multiple of , as required.

It remains now to establish the base case of the induction, namely the case when equals a prime . Suppose that . If for some we have , then so that is a multiple of and we are done. Suppose then that for , , and define sets . By repeated application of the Cauchy-Davenport Theorem, we see that . Thus every element of can be written as a sum of exactly elements of our sequence. In particular, can be so written, so that , taken together with the elements of our sequence that sum to , gives a element subsequence whose sum is 0 in , as required. This completes the proof.

## 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.

## 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 , a -diregular directed graph has an directed even cycle.

** Theorem** [Lovasz Local Lemma (symmetric version)] Let be a dependency graph for events . Suppose that the maximum degree of is and that there is a real number for which for all . If , then .

In the statement above, the vertices of consist of and is mutually independent of all the ‘s for which there is no edge in .

**Theorem** [Alon and Linial] Let and let be a directed graph where every vertex has indegree and outdegree . Then has a directed even cycle.

*Proof*. Consider a random 2-colouring of the vertices of . For each vertex of , let denote the event that and all of its outneighbours have the same colour. Then . Moreover, is independent of all for which neither nor any outneighbour of is an outneighbour of . However, each of the outneighbours of has indegree , so we may apply the local lemma with . For , we have , so with positive probability, every vertex of has an outneighbour of the opposite colour.

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