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 
Proof: We are going to construct a bijection between
- Functions
(of which there are
) and
- Trees on
with two distinguished nodes
and
(possibly
).
This will imply the answer.
Let’s look at the first piece of data. We can visualize it as 
You’ll notice that in each component, some of the points lie in a cycle and others do not. I’ve colored the former type of points blue, and the corresponding arrows magenta.
Thus a directed pseudoforest can also be specified by
- a choice of some vertices to be in cycles (blue vertices),
- a permutation on the blue vertices (magenta arrows), and
- attachments of trees to the blue vertices (grey vertices and arrows).
Now suppose we take the same information, but replace the permutation on the blue vertices with a total ordering instead (of course there are an equal number of these). Then we can string the blue vertices together as shown below, where the green arrows denote the selected total ordering (in this case 
This is exactly the data of a tree on the
is 
-colorable
.
.
for any integer 
is the cycle graph on 
vertices). To see this, we only have to show that given a list of two colors at each vertex of 
, 
are such that some color at 
is not in the list at 
, \dots, 
be an integer and define
, where 
is the set of functions ![{u : [n] \rightarrow [n]}](https://s0.wp.com/latex.php?latex=%7Bu+%3A+%5Bn%5D+%5Crightarrow+%5Bn%5D%7D&bg=ffffff&fg=000000&s=0 "{u : [n] \rightarrow [n]}")
and ![{V = [n]}](https://s0.wp.com/latex.php?latex=%7BV+%3D+%5Bn%5D%7D&bg=ffffff&fg=000000&s=0 "{V = [n]}")
. Then consider 
colors 
for 
. On a vertex 
, we list colors 
, 
, \dots, 
. On a vertex 
, we list colors 
, 
, \dots, 
. By construction it is impossible to properly color 
is illustrated in the figure below (image in 
then 
.
. For example, the line graph (also called edge graph) of any simple graph 
choosable, where
.
vertices contains at most 
edges. Thus for such graphs we have 
and deduce:
-choosable.
which we have seen in Example 
.
be a field, and let ![{f \in F[x_1, \dots, x_n]}](https://s0.wp.com/latex.php?latex=%7Bf+%5Cin+F%5Bx_1%2C+%5Cdots%2C+x_n%5D%7D&bg=ffffff&fg=000000&s=0 "{f \in F[x_1, \dots, x_n]}")
be a polynomial of degree 
. Let 
such that 
for all 
.
of 
is not zero. Then we can pick 
, \dots, 
such that
be the set of colors at vertex 
, and 
). Consider the polynomial
is 
. Therefore, one can select a color from each 
.
correspond to differences in directed orientations. To be precise, we introduce the notation:
to every edge of 
, i.e. the edge points from the smaller number to the larger one.
to the be set of all even orientations of 
.
to the be set of all odd orientations of 
.
and 
. The indegrees of are 
, 
and 
. Therefore, this particular orientation is an element of 
. In terms of 
term.
is
or 
from each 
, as in Example 
is the orientation is even, and 
if the orientation is odd, as desired. 
, viewed as a directed graph. An 
is a subgraph of 
and 
, respectively.
. Then there are natural bijections
then there are bijections
, Then we define a suborietation of 
, by including exactly the edges of 
is in the opposite direction. It’s easy to see that this induces a bijection
, then given a list of 
colors at each vertex of 
-choosable.
as in Theorem 
.
. Construct a bipartite graph
and 
if 
is an endpoint of 
. Since 
we satisfy Hall’s condition (as 
is a condition for all subgraphs 
) and can match each edge in 
to a (copy of some) vertex in 
. Since there are exactly 
copies of each vertex in 
. Since 
, since 
in 
variables and ternary products. The objective is to maximize the fraction of satisfied equations.
but not 
.
linear algebra.
by selecting all-zero or all-one.
vs. 
decision problem for MAX-E3LIN is NP-hard.
or 
(given it is one or the other). A direct corollary of this is approximating MAX-SAT is also NP-hard.
vs. 
is optimal in light of a random assignment. In fact, one can replace 
, but we don’t do so here.
in MAX-E3LIN, we consider four formulas 
, 
, 
. Either three or four of them are satisfied, with four occurring exactly when 
. One does a similar construction for 
. We have
has a (non-adaptive) verifier with the following properties.
random bits, and queries just three (!) bits.
, then there is a proof 
which is accepted with probability at least 
, then every proof is accepted with probability at most 
.
, a set of keys 
for vertices of 
for 
. For every edge 
there is a function 
specifying a key 
for every label 
. The goal is to label the graph 
vs. 
, given 
and 
are sufficiently large in 
in the resulting MAX-E3LIN.
, then we get a solution of value 
in the resulting MAX-E3LIN.
is a 
. An 
is defined similarly.
variables:
binary variables, one for every 
binary variables, one for every 
,
string by 
.
for the MAX-E3LIN instance.
and 
be the dictator functions for the colorings. In that case, 
, 
, and 
, so the product is always 
be a random 
represents “noise” bits, which resolve the first problem by corrupting a bit of 
with probability 
equations.
of the equations.
, 
, 
.
, we define
maps subsets of 
and that 
if 
is odd.
, then we can reconstruct a solution to LABEL-COVER with value 
. (The use of 
here will be clear in a moment). This process is called “decoding”.
is a small set such that 
is large, then we can pick a key from 
and 
. We want to do something similar with 
and 
be constants (the actual values arise later).
of keys is heavy for 
if
heavy sets by Parseval.
so at least one compatible key-label pair is in 
.
distribution.
of 
. In particular, 
. Finally by \Cref{rem:po}, we see 
. Note that 
, since there are at most 
elements.
, and select a random element from 
. Hence we conclude probability of success is at least
, but this doesn’t imply it for every edge. Thus one likely needs to do another averaging argument.)
