Representation theory of the symmetric group: basics

In this post we lay out some introductory material on the representation theory of $ S_n$ over $ \mathbb{C}$.

Talagrand's concentration inequality

In this post we basically go over a proof of Talagrand's concentration inequality, following material from Bela Bollobas' part III course on probabilistic combinatorics. Things can get rather messy, so hopefully writing this will force me to properly understand it.

The Hausdorff metric inherits compactness

In this post we prove that for a compact metric space $ X$, the set of closed subsets $ F(X)$ can be given a metric that captures `closeness' in a way that turns $ F(X)$ in a compact metric space in its own right. This has applications in various optimization problems, such as the isoperimetric inequality, where we want to argue an optimum exists by approximating it with a sequence of sets.

Roth's theorem via Fourier analysis

Roth's classical theorem says that a subset of $ \{1,\ldots,n\}$ of density $ \Omega \left(\frac{1}{\log\log n}\right)$ contains a length-3 arithmetic progression. In this post we give an exposition of a proof from Tim Gowers' part III course on additive combinatorics using Fourier analytic methods on $ \mathbb{Z}_n$.

The Erdos-Szekeres theorem

This nice classical theorem says simply that in any sequence of $ ab+1$ numbers there is either an increasing subsequence of length $ a+1$ or a decreasing subsequence of length $ b+1$. In this post, we'll prove it, give some applications, and show a high-dimensional generalization.

Lower bound for number of irregular pairs in the regularity lemma

In this post we'll show you need to allow at least linearly many irregular pairs in Szemeredi's regularity lemma. This came up in Andrew Thomason's part III course on extremal graph theory; it seems that everybody knows the result, but there's no nice proof online. So he gave us one, reproduced here.