Tag Archives: double counting

Zarankiewicz’s Problem

February 1, 2012 · by · in Combinatorics, Extremal Set Theory, Mathematics, Probabilistic Method, Riddle of the day, Think... · Leave a comment

Zarankiewicz’s problem plays an important role in extremal combinatorics. Let’s first learn few things about Kazimierz Zarankiewicz from Wikipedia. Unfortunately, his life had a lot of suffering. He had to live the nightmare of concentration camps during World War II and he was a revolutionary. He was not a guerrilla but continued to teach despite the Nazi […]

Ahlswede-Zhang identity

December 29, 2011 · by · in Combinatorics, Extremal Set Theory, Mathematics, Probabilistic Method · Leave a comment

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

December 23, 2011 · by · in Books, Combinatorics, Computer Science, Mathematics, Notes, Probabilistic Method, Problem of the day, Think... · 1 Comment

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. […]