Category Mathematics
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 […]
Martingales & Coins: Waiting for Heads-Tails-Heads
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 […]
tsourakakis.com 