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

# Tag: 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

## 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)

## Approximating E3-LIN is NP-Hard

This lecture, which I gave for my 18.434 seminar, focuses on the MAX-E3LIN problem. We prove that approximating it is NP-hard by a reduction from LABEL-COVER. 1. Introducing MAX-E3LIN In the MAX-E3LIN problem, our input is a series of linear equations $latex {\pmod 2}&fg=000000$ in $latex {n}&fg=000000$ binary variables, each with three terms. Equivalently, one… Continue reading Approximating E3-LIN is NP-Hard