Consider the following simple problem: let be a sequence of independent fair coin tosses. How many times do we have to toss the coin in expectation in order to observe the sequence HTH (H stands for heads and T for tails)? We will answer this question here with three different ways. The first way is […]
This post is about Sperner systems and about turning the famous LYM inequality into an identity. Typically, people refer to this inequality as the LYM inequality (Lubell-Yamamoto-Meshalkin) but it is worth pointing out that the inequality follows as a corollary from the more general Bollobás inequality. While thinking of this inequality I asked myself about the cases that […]
Double counting is a simple yet so powerful way to prove non-trivial theorems. Here, we present some applications of the double counting principle. Our main source is the excellent book “Extremal Combinatorics” by Stasys Jukna [1]. A newer edition from the one in the picture (which shows the book I have) is also available now. […]
tsourakakis.com 