I recently had a combinatorics paper appear in the EJC. In this post I want to brag a bit by telling the ``story'' of this paper: what motivated it, how I found the conjecture that I originally did, and the process that eventually led me to the proof, and so on. This work was part… Continue reading A story of block-ascending permutations
Category: Combinatorics
Joyal’s Proof of Cayley’s Tree Formula
I wanted to quickly write this proof up, complete with pictures, so that I won't forget it again. In this post I'll give a combinatorial proof (due to Joyal) of the following: Theorem 1 (Cayley's Formula) The number of trees on $latex {n}&fg=000000$ labelled vertices is $latex {n^{n-2}}&fg=000000$. Proof: We are going to construct a… Continue reading Joyal’s Proof of Cayley’s Tree Formula
Combinatorial Nullstellensatz and List Coloring
More than six months late, but here are notes from the combinatorial nullsetllensatz talk I gave at the student colloquium at MIT. This was also my term paper for 18.434, ``Seminar in Theoretical Computer Science''. 1. Introducing the choice number One of the most fundamental problems in graph theory is that of a graph coloring,… Continue reading Combinatorial Nullstellensatz and List Coloring
A Sketchy Overview of Green-Tao
These are the notes of my last lecture in the 18.099 discrete analysis seminar. It is a very high-level overview of the Green-Tao theorem. It is a subset of this paper. 1. Synopsis This post as in overview of the proof of: Theorem 1 (Green-Tao) The prime numbers contain arbitrarily long arithmetic progressions. Here, Szemerédi's… Continue reading A Sketchy Overview of Green-Tao
Formal vs Functional Series (OR: Generating Function Voodoo Magic)
Epistemic status: highly dubious. I found almost no literature doing anything quite like what follows, which unsettles me because it makes it likely that I'm overcomplicating things significantly. 1. Synopsis Recently I was working on an elegant problem which was the original problem 6 for the 2015 International Math Olympiad, which reads as follows: Problem… Continue reading Formal vs Functional Series (OR: Generating Function Voodoo Magic)
18.099 Transcript: Bourgain’s Theorem
As part of the 18.099 Discrete Analysis reading group at MIT, I presented section 4.7 of Tao-Vu's Additive Combinatorics textbook. Here were the notes I used for the second half of my presentation. 1. Synopsis We aim to prove the following result. Theorem 1 (Bourgain) Assume $latex {N \ge 2}&fg=000000$ is prime and $latex {A,… Continue reading 18.099 Transcript: Bourgain’s Theorem
18.099 Transcript: Chang’s Theorem
As part of the 18.099 discrete analysis reading group at MIT, I presented section 4.7 of Tao-Vu's Additive Combinatorics textbook. Here were the notes I used for the first part of my presentation. 1. Synopsis In the previous few lectures we've worked hard at developing the notion of characters, Bohr sets, spectrums. Today we put… Continue reading 18.099 Transcript: Chang’s Theorem
Power Overwhelming 