6
$\begingroup$

Let $\mathcal{C} = \bigcup_{n=0}^{\infty}\mathcal{C}_n$ be a class of finite (labeled) combinatorial objects, where $\mathcal{C}_n$ is the set of objects on $[n] = \{1,2,\dotsc,n\}$. For example, $\mathcal{C}$ could be all finite graphs, with $\mathcal{C}_n$ the graphs with vertex set $[n]$. Let us say that "almost all objects in $\mathcal{C}$ are asymmetric" if the proportion of elements in $\mathcal{C}_n$ with trivial automorphism group approaches 100% as $n\to \infty$.

I would expect that for most of the commonly studied combinatorial classes $\mathcal{C}$, almost all objects are asymmetric.

For example, for graphs I believe this was proved in [P. Erdős, A. Rényi, Asymmetric graphs, Acta Math. Acad. Sci. Hungar. 14 (1963) 295–315]. For matroids, this is conjectured in [D. Mayhew, M. Newman, D. Welsh, G. Whittle, On the asymptotic proportion of connected matroids, European J. Combin. 32 (6) (2011) 882–890], but is not known as far as I know. I would guess the same is true for posets, lattices, etc.

Question: What are some examples of natural classes $\mathcal{C}$ where not almost all objects are asymmetric?

The one example I know is trees. If almost every tree was asymmetric, then the asymptotic number of unlabeled trees would be easy to work out from Cayley's formula $n^{n-2}$. However, in fact to get the asymptotic number of unlabeled trees requires some Pólya counting, and was first worked out in [R. Otter. The number of trees. Ann. of Math. (2), 49:583–599, 1948].

EDIT: In light of some of the comments, let me say that I'm interested in examples where $\mathcal{C}$ is "sufficiently rich," which is of course a bit subjective. But graphs, matroids, posets, trees, etc. are rich, whereas things like strings (or even just bare sets) are not so rich.

EDIT 2: From this previous MO answer I learned that it is indeed known that almost all posets are asymmetric, and in fact Prömel has a very interesting paper "Counting unlabeled structures" on this subject, whose abstract begins:

In this note we prove that whenever $\mathcal{C}$ is an infinite class of finite labeled structures provided with one binary relation such that $\mathcal{C}$ is closed under isomorphisms and (induced) substructures and $\mathcal{C}$ is rich enough (in a quantitative sense) then almost all structures in are rigid, i.e., have no nontrivial automorphism.

This goes some way to answering my questions, or at least showing what examples (of classes where not almost all objects are asymmetric) must look like.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ A bit more generally it's that case for functions $[n] \to [n]$, and even $[n] \to [n^2]$ (birthday paradox), but I agree that it's not too interesting $\endgroup$
    – Daniel Weber
    Commented Jan 23 at 14:58
  • 1
    $\begingroup$ Partitions are also an example, almost all partitions have repeated parts $\endgroup$
    – Daniel Weber
    Commented Jan 23 at 15:01
  • 1
    $\begingroup$ Finite abelian groups which are not 2-groups have a nontrivial involution given by negation. That said, given $\mathcal C$, cant you define an object of $\mathcal C'_n$ to consist of two objects of $\mathcal C_{n/2}$ and an isomorphism between them? Then $\mathcal C'$ is a combinaorial class where everything has an automorphism. Finally, I really think the language of combinatorial species seems relevant here... $\endgroup$
    – Tim Campion
    Commented Jan 23 at 15:27
  • 4
    $\begingroup$ @TimCampion Your statement about trees is not correct. Start with three paths of distinct lengths and identify one of their endpoints (so it becomes of degree three). This is a tree with trivial automorphism group. (The smallest example has order 7.) $\endgroup$
    – verret
    Commented Jan 23 at 17:11
  • 2
    $\begingroup$ Interval orders and semiorders are examples. They are part of a more general setup described in EC1, second edition, Exercise 3.17. $\endgroup$
    – Richard Stanley
    Commented Jan 24 at 2:17

0

Reset to default

You must log in to answer this question.