A Generalization of Erdos’s Proof of Bertrand-Chebyshev Theorem

Bertrand’s postulate states that for every positive integer n, there is always at least one prime psuch that n < p < 2n. This was proved by Chebyshev in 1850, Ramanujan in 1919 and Erdos in 1932. Legendre’s conjecture states that there is a prime number between n2 and (n+1)2 for every positive integer n. It is one of the four Landau’s [...]

Read Full Post »

The Sunflower Lemma

Today’s post is about the Sunflower Lemma (a.k.a the Erdos-Rado Lemma). I learnt about Sunflower Lemma while reading Razborov’s Theorem from Papadimitriou’s computational complexity book. A sunflower is a family of p sets , called petals, each of cardinality at most l, such that all pairs of sets in the family have the same intersection, [...]

Read Full Post »