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
Tag: graph theory
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
Power Overwhelming 