Category Combinatorics

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

The Ballot Theorem

Today’s post is going to be about politics. Consider an election where there are two candidates, call them A and B, who receive votes respectively, and let us assume that . Assume that all possible “trajectories” are equally likely. What is the probability that candidate B is ahead of A throughout the vote counting procedure? […]

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

Recurrences and the riddle of the day

Sometimes solving exactly a recurrence can be demanding. The use of software can be useful 🙂 Something that I slept under the rag above and I want to mention it since this post by no means is supposed to be intimidating to a novice, is that in many applications (lemmas,theorems etc.) one needs the asymptotic behavior […]

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