Category Probabilistic Method

Discrepancy I

Consider a set system, a.k.a. hypergraph, where is the ground set and where . We wish to color the ground set $V$ with two colors, say red and blue, in such way that all sets in the family are colored in a  “balanced” way, i.e., each set has nearly the same number of red and blue points. […]

Distinct Sums

A set of positive integers is said to have distinct sums (DS) if all sums where   are distinct. We are interested in understanding the function .  We obtain a simple lower bound on by observing that the set  has DS as long as . Therefore, . Interestingly, this lower bound is not far away from being optimal, in […]

Giant component with Depth First Search

I just finished reading a short paper of Michael Krivelevich and Benny Sudakov, two leading experts in probabilistic combinatorics, which appeared in Arxiv about a month ago [1]. It is a simple proof of the classical result that the random binomial graph exhibits a phase transition around . When then the largest component has size […]

Zarankiewicz’s Problem

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

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

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

Large Girth and Chromatic Number

Paul Erdös is an inspiring figure.  Not only for mathematicians and computer scientists but for everyone. His simplicity, his love for his friends, for music and of course for mathematics indicate a man who followed his feelings which had the word love in them. If you get to meet people that knew him personally and […]