20
$\begingroup$

I was encouraged to post this question by Jim Propp during a meeting of the Cambridge Combinatorics and Coffee Club. It is a counterpoint to the MathOverflow question "Counting Problems where Labeled is Known but Unlabeled is Not" which asks for examples where it is known how to count labeled objects but not known how to count unlabeled objects.

I think the general expectation in enumerative combinatorics is that it should be easier to count labeled objects as opposed to unlabeled objects. For instance, we have much nicer formulas for the number of labeled trees, labeled graphs, labeled connected graphs on $n$ vertices than for the corresponding unlabeled objects. (Here labeled means the vertices are labeled.)

Nevertheless I am asking for counterexamples to this general trend. That is, I am looking for examples of counting problems where the unlabeled objects have a nicer formula than the labeled objects. I know of two such examples.

  1. Semiorders. A semiorder, also known as a unit interval order, is a poset that avoids $2+2$ and $3+1$ as induced subposets. The number of semiorders on $n$ unlabeled elements is the $n$th Catalan number $C_n := \frac{1}{n+1}\binom{2n}{n}$. The number of labeled semiorders is sequence A006531 in the OEIS. Labeled semiorders on $n$ elements have an exponential generating function of $C(1-e^{-x})$ where $C(x) = \frac{1-\sqrt{1-4x}}{2x}$ is the ordinary generating function for the Catalan numbers.

  2. Threshold graphs. A threshold graph is a graph $G=(V,E)$ for which there is some threshold function $\omega\colon V\to\mathbb{R}$ on the vertices such that $\{i,j\}\in E$ iff $\omega(i)+\omega(j) > 0$. The number of threshold graphs on $n$ unlabeled vertices is $2^{n-1}$ (because there is a simple recursive construction of these graphs). The number of labeled threshold graphs is sequence A005840 in the OEIS. Labeled threshold graphs on $n$ vertices have an exponential generating function $\frac{e^x(1-x)}{(2-e^x)}$.

Does anyone know other examples like these? Interestingly, for both semiorders and threshold graphs we have an associated hyperplane arrangement; see Stanley's notes.

Improve this question
$\endgroup$
2
  • 9
    $\begingroup$ Counting number of ways to put $n$ unlabeled stones in a row is very easy compared to the $n!$ ways to put down the labeled ones... $\endgroup$
    – Per Alexandersson
    Commented Mar 7, 2016 at 2:39
  • 3
    $\begingroup$ @PerAlexandersson: Perhaps this somewhat trivial example was meant in jest but it actually does fit nicely into the hyperplane arrangement story. You can count unlabeled semiorders by counting regions of $\{x_i-x_j=1\colon 1\leq i,j \leq n\}$ that intersect $x_1 < x_2 < \cdots < x_n$ and you can count unlabeled threshold graphs by counting regions of $\{x_i+x_j = 0\colon 1 \leq i < j \leq n\}$ that intersect $|x_1| < |x_2| < \cdots < |x_n|$. Similarly you can count unlabeled stone arrangements by counting regions of $\{x_i-x_j = 0\}$ that intersect $x_1 < \cdots < x_n$. $\endgroup$
    – Sam Hopkins
    Commented Mar 7, 2016 at 3:53

2 Answers 2

Reset to default
5
$\begingroup$

A good example is self-complementary graphs. It's not hard to count unlabeled self-complementary graphs using Burnside's lemma, but there seems to be no reasonable formula for counting labeled self-complementary graphs.

Unlabeled self-complementary graphs are counted by sequence A000171 in the OEIS. A paper on counting labeled self-complementary graphs is Shinsei Tazawa, A new counting methods, including the issue of counting labelled self-complementary graphs, arXiv:0909.2314 [math.CO]. This paper computes the number of labeled self-complementary graphs on $n$ vertices for $n$ up to 9.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ What is labelled analogue of self-complementary graph? For me, 'self-complementary graph with labelled vertices' looks less natural than 'self-complementray graph with labelled vertices and given isomorphism between the graph and its complement'. $\endgroup$
    – Fedor Petrov
    Commented Mar 8, 2016 at 14:59
  • $\begingroup$ A labeled self-complementary graph is a graph that is isomorphic to its complement. $\endgroup$
    – Ira Gessel
    Commented Mar 8, 2016 at 15:29
4
$\begingroup$

A generalization of Per Alexandersson's comment is to take the isomorphism class of any graph (or digraph) $G$. There is exactly one such unlabelled graph, so it is obviously harder to count the labelled objects.

For Per Alexandersson's comment, $G$ is a directed path with $n$ vertices, in which case there are $n!$ labelled versions of $G$. If $G$ is a cycle with $n$ vertices, there are $\frac{(n-1)!}{2}$ labelled versions of $G$. If $G$ is $K_{n,n}$, there are $\frac{1}{2}\binom{2n}{n}$ labelled versions of $G$. These examples are quite structured, making it fairly easy to count the labelled versions, but for a random graph $G$ on $n$ vertices, it will likely be difficult to count the number of labeled versions of $G$.

Improve this answer
$\endgroup$

You must log in to answer this question.

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