5
$\begingroup$

Cayley's formula states that the number of labeled trees on $n$ vertices is $n^{n-2}$. There are many nice proofs of this compact formula.

To contrast, counting unlabeled trees is considerably harder. The best we seem to have are asymptotic or generating function representations.

I am hoping to solicit examples of other counting problems of this type, particularly ones where the labeled count is known exactly but little is known about the unlabeled count.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ I would say that a lot is known about the count of unlabeled trees; it's just more complicated than for labeled trees, and this is very typical of graphical enumeration. You can find lots of examples in Harary and Palmer's book "Graphical Enumeration." There is even an explicit though complicated formula (as a sum over partitions) for the number of unlabeled trees. It might be noted that there are some problems, such as counting self-complementary graphs, in which the unlabeled version has been solved, but not the labeled version. $\endgroup$
    – Ira Gessel
    Commented Oct 7, 2014 at 19:45
  • 3
    $\begingroup$ In principle the number of unlabelled objects can be computed by Burnside's Lemma (aka Cauchy-Frobenius theorem) if the automorphisms of the labelled objects are sufficiently understood. Thus we want situations with complicated automorphism groups. For instance, it seems unlikely that there is a polynomial-time algorithm for computing unlabelled graphs on $n$ vertices, though the number of labelled graphs is just $2^{{n\choose 2}}$. There are many similar examples. $\endgroup$
    – Richard Stanley
    Commented Oct 7, 2014 at 23:18
  • $\begingroup$ Although in general I guess you are right in that labeled objects are more amenable than unlabeled ones, I think there are some counterexamples to this general behavior: for instance, it is 'easier' to count unlabeled semiorders as opposed to labeled ones (see en.wikipedia.org/wiki/Semiorder#Other_results). $\endgroup$
    – Sam Hopkins
    Commented May 24, 2015 at 1:34
  • $\begingroup$ Here's another example: It's not too difficult to count labeled graphs in which no two vertices have complementary neighborhoods—there's a nice exponential generating function that can be found by inclusion-exclusion. But I don't know how to count the corresponding unlabeled graphs. $\endgroup$
    – Ira Gessel
    Commented Mar 14, 2020 at 18:41

1 Answer 1

Reset to default
1
$\begingroup$

Since the question

I am hoping to solicit examples of other counting problems of this type, particularly ones where the labeled count is known exactly but little is known about the unlabeled count.

does not make "exactly" a sine qua non, the following is a relevant example: counting planar graphs. It is still essentially an

open problem to find a formula, even an asymptotic one, for the total number of all unlabelled planar graphs on $n$ vertices.

(By the way, I think that counting unlabelled planar graphs is arguably the most intuitive combinatorial problem of all; after all, we are here speaking of drawing unlabelled maps, what could be more intuitive than that?)

In contrast, the corresponding problem for labeled planar graphs is not easy but much better understood, especially thanks to:

Omer Giménez, Marc Noy, Asymptotic enumeration and limit laws of planar graphs.

Journal of the American Mathematical Society 22, No. 2, 309-329 (2009).

it was (inter alia) proved for the first time that if $g_n$ denotes the number of labelled planar undirected graphs on vertex set $n$, then there exist two constants $\gamma,g>0$ and $g$, which are explicitly known (though not as elementary functions: there are inverses of elementary functions involved; but they can routinely be computed to arbitrary numerical precision), such that

${\Large\lim_{n\to\infty}\frac{g_n}{ {}\quad g\cdot n^{-\frac72}\cdot\gamma^n\cdot n!\ \quad}}\quad =\quad 1$. ${}\hspace{100pt}$ (known)

As far as I know, this is the best formula for the number of labelled planar graphs. (There seems to be no hope to ever find an explicit formula in elementary functions, or even a polynomial algorithm to arrive at the number $g_n$.)

In contrast, and this makes it relevant to the question, if $u_n$ denotes the number of unlabeled planar graphs on $n$, then all that is known is that

$\lim_{n\to\infty} (u_n)^{1/n}$

exists (and there is an explicit lower bound for this limit); this gives far less information than the result of Giménez and Noy. In particular, it is not known (and this is relevant to the OP's question) whether there exists a rational number $q>0$ and constants $u,\xi>0$ such that

${\Large\lim_{n\to\infty}\frac{u_n}{ {}\quad u\cdot n^{-q}\cdot\xi^n\cdot n!\ \quad}}\quad \overset{?}{=}\quad 1$. ${}\hspace{100pt}$ (unknown)

Improve this answer
$\endgroup$

You must log in to answer this question.

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