5
$\begingroup$

I have been trying to solve this problem for a while now. I am looking for a detailed proof.

$\endgroup$
3
  • 1
    $\begingroup$ Would you mind sharing some of the approaches that you've tried? $\endgroup$
    – epimorphic
    Apr 13, 2017 at 0:27
  • 1
    $\begingroup$ It is best to include the problem statement fully within the body of the Question. While a truncated version might fit in the title (and this may be a suitable title for attracting Readers), the body of the Question allows for a more complete description and avoids confusion. $\endgroup$
    – hardmath
    Apr 13, 2017 at 0:31
  • $\begingroup$ I tried deletion-contraction of edges. $\endgroup$
    – A. Tevatia
    Apr 13, 2017 at 0:38

1 Answer 1

5
$\begingroup$

There are two steps to the proof: proving that the number of acyclic orientations satisfies the deletion-contraction recurrence, and proving that (up to a factor of $(-1)^n$) it agrees with the chromatic polynomial evaluated at $-1$ on some base cases.

For the first step, given a pair of vertices $(u,v)$ with no edge between them in $G$, we want to compare acyclic orientations of $G$ to acyclic orientations of $G + uv$ and acyclic orientations of $G / uv.$ Their relationship is summarized in the following table: \begin{array}{cccc} & G & G+uv & G /uv \\ \text{orientations with path $u \to v$} & \times 1 & \times 1 & \times 0 \\ \text{orientations with path $v \to u$} & \times 1 & \times 1 & \times 0 \\ \text{orientations with neither path} & \times 1 & \times 2 & \times 1 \end{array} More precisely:

  1. There is a bijection between acyclic orientations of $G$ with a directed path $u \to v$, and acyclic orientations of $G + uv$ with a directed path $u \to v$ (not using the edge $uv$).

    An acyclic orientation of $G+uv$ with induces an acyclic orientation of $G$, which will keep a directed path if it has one. Conversely, an acyclic orientation of $G$ induces an acyclic orientation of $G+uv$, except for the choice of orientation of $uv$; but if a directed path $u\to v$ exists, that choice is forced, because the orientation $\overrightarrow{vu}$ would create a cycle.

  2. There is a bijection between acyclic orientations of $G$ with a directed path $v \to u$, and acyclic orientations of $G + uv$ with a directed path $v \to u$ (not using the edge $uv$).

    The proof is identical.

  3. There is a $1$-to-$2$ map between acyclic orientations of $G$ with no directed path between $u$ and $v$, and acyclic orientations of $G+uv$ with no directed path between $u$ and $v$ (not using the edge $uv$).

    Here, any such orientation of $G$ can be extended in exactly two ways to an orientation of $G+uv$: we have complete freedom in how to orient $uv$, since we will not create a directed cycle. (And any acyclic orientation of $G+uv$ comes from an acyclic orientation of $G$.)

  4. There is a bijection between acyclic orientations of $G$ with no directed path between $u$ and $v$, and acyclic orientations of $G/uv$.

    Given an acyclic orientation of $G/uv$, we can extend it to an acyclic orientation of $G$; give most edges the same orientation, and for any edge $uw$ or $vw$, give it the orientation of the edge between $(uv)$ and $w$ in $G/uv$. Going the other way, we only need to worry about what happens to vertices $w$ with both an edge $uv$ and $uw$, since these collapse to a single edge. But their orientations always agree, or else there would be a directed path $(u,w,v)$ or $(v,w,u)$.

So if $a(G)$ counts the acyclic orientations of $G$, we have $a(G) = a(G+uv) - a(G /uv)$ because this holds in each of the three rows of the table above.

Now it remains to check that if we evaluate the chromatic polynomial at $-1$, this gives $(-1)^n a(G)$ on some base cases. We could take empty graphs: these have chromatic polynomial $P(t) = t^n$, giving $P(-1) = (-1)^n = (-1)^n a(G)$, as desired. Complete graphs would also work. These have chromatic polynomial $P(t) = t(t-1)(t-2)\dotsb(t-n+1)$, so $P(-1) = (-1)^n n!$, matching $a(K_n) = n!$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .