5
$\begingroup$

It is well-known that the number of acyclic orientations of $K_n$ is $n!$. Does anybody know of a combinatorial argument for this fact which uses the identity: $$n!=\sum_{k=1}^ns(n,k),$$ where the $s(n,k)$ are Stirling numbers of the first kind? If such a thing exists; what do the different Stirling numbers correspond to exactly?

I would also be interested in any other information or references linking Stirling numbers with acyclic orientations. And failing all this, if anybody knows of any other nice combinatorial arguments (that is, not involving the evaluation of the chromatic polynomial at $-1$) for the numbers of acyclic orientations of complete graphs then I would be interested to hear them.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ An acyclic ordering on a complete graph is just the same think as a total order on the vertices. Edges point from small to big. There are clearly n! of these. So it seems you just want to interpret your identity in terms of linear orders. $\endgroup$
    – Benjamin Steinberg
    Commented Jun 25, 2012 at 16:49
  • 1
    $\begingroup$ More interesting is the generalization to any graph, due to Greene and Zaslavsky. See Corollary 7.4 of their paper at vulcan.math.binghamton.edu/zaslav/Tpapers/iwn.tams1983.pdf. $\endgroup$
    – Richard Stanley
    Commented Jun 25, 2012 at 23:09

3 Answers 3

Reset to default
4
$\begingroup$

hmmm...seems I was being lazy. Did that thing where you get up to do something else and the answer suddenly seems obvious. You just need to label the vertices of each acyclic orientation according to the order it dictates, and choose one to be your "identity". The others are clearly then just permutations of the labels with cycle numbers corresponding to the k in each s(n,k). Thanks for your help Benjamin.

Writing this as an answer so it can be marked as resolved (if I can accept my own answer!).

Improve this answer
$\endgroup$
2
$\begingroup$

Ok, this is 6 years late, and it might just be kicking the can down the road, but: the number of acyclic orientations of a graph $G$ with $n$ vertices is given by $(-1)^n \chi_G(-1)$, where $\chi_G$ is the chromatic polynomial of the graph [1].

For the complete graph $K_n$, it is easy to see that $\chi_{K_n}(x) = \sum_{i=1}^n (-1)^{n-i} s(n,k)\, x^i$. Replacing $x=-1$ gives you what you want.

From this point of view, the (signed) Stirling numbers of the first kind are the coefficient of the chromatic polynomial of $K_n$, which have all sorts of combinatorial interpretations.

[1] Stanley, Richard P., Acyclic orientations of graphs, Discrete Math. 5, 171-178 (1973). ZBL0258.05113..

Improve this answer
$\endgroup$
0
$\begingroup$

Ok, this is 10 years late, and it might just be kicking the can down the road, but: the number of acyclic orientations of a graph $G$ is equal to the number of Coxeter elements (elements with exactly one of each generator in any of its reduced expressions) of the group with $G$ as its Coxeter Graph.

It uses a similar idea as labelling the vertices but whenever two vertices are not adjacent in $G$ let them commute. This paper by Shi (which is a delightful read by the way) establishes a bijection to Coxeter Elements and gives a recurrence relation to compute such things. Since for a complete graph none of the labels commute it is just the number of permutations of the labels.

It would be nice to see this bijection in light of some generalization of the Stirling numbers of the first kind, but I can't think of any at the moment.

Improve this answer
$\endgroup$

You must log in to answer this question.

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