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

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