Category Mathematics

flagmatic

By reading this recent paper in Arxiv, I first read about flagmatic, a useful tool for  researchers in extremal combinatorics. Here is the user guide too.

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

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

Visualizing the Configuration model

A way to generate a random -regular graph is via the configuration model. Here is a short description of the model. Imagine that each vertex has k tokens. This suggests that we have in total kn tokens, where is the number of vertices and you can freely think of . Also, let me mention that […]

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