Making It Count: The Pigeonhole Principle

A counting argument is a method of counting the number of objects with a prescribed property. A good counting argument, apart from being merely clever and elegant, should be able to hold its own in more general mathematical settings. The Making It Count series is a tribute to the art of good counting. I will present nuggets not just from the usual sources like number theory and combinatorics, but also analysis, geometry and physics. It is only fitting to start the series with one of the most natural and widely used counting arguments: the humble and versatile Pigeonhole Principle!

The above problem is a specific instance of what are called Ramsey Numbers, named for Frank Ramsey. Every time I look at stars in the sky I think about Frank Ramsey, his tragic life and his wonderful theory. For two colours, the Ramsey Number R(r,s) is the smallest number of points such that the edges between them, when coloured, contain a monochromatic polygon with either r or s sides. So, the above problem proves that R(3,3) = 6. These numbers are hard to compute for even small values of r and s. For instance, R(10,10) is known to be between 798 and 23556. Establishing bounds for Ramsey Numbers is as important problem in graph theory.