I would be thankful if someone could verify the following reasoning.

Let $I$ be some graph property that is invariant (chromatic number, connectedness,etc.). Let $p(n)$ be the number of (labeled) graphs of degree $n$ that have property $I$. Suppose we know that almost all graphs have property $I$ that is to say

$$\lim_{n \to \infty} \frac{p(n)}{2^{ {n \choose 2}}} = 1. \; \; (1)$$

Does it imply that almost all non labeled graphs of $n$ have property $I$ as well?

My reasoning would say YES, since the number of all non labeled graphs is asympototic to $\frac{2^{n \choose 2}}{n!}$ and the size of the automorphism class of almost all graphs is $n!$ so if $p'(n)$ denotes the number of non labeled graphs we would have $p'(n) \sim p(n)$ and using a simmilar limit as in $(1)$ one derives at the conclusion that the given property also holds for almost all non labeled graphs.

Is the above true? If yes then this would be (in my opinion) quite nice since one can derive such results for labled graphs (which is in a way easier) and have the non labeled result "for free".

  • $\begingroup$ An interesting fact is that if the answer is YES when $I$ is the assymetry property (having no non-trivial autormorphism), then the answer is YES for all $I$. So your question is equivalent to the question : if $a_n$ ($b_n$)is the number of asymmetric unlabeled (just unlabeled) graphs on $n$ vertices, is it true that $\frac{a_n}{b_n} \to 1$ ? $\endgroup$ – Ewan Delanoy Nov 12 '12 at 8:25

In Bela Bollobas’ book “Random Graphs” (Cambridge University Press), a similar question is asked and answered in the affirmative, but only when the number of edges is fixed and not too close to $0$ or $n \choose 2$, the maximum.

Bollobas also states p.240-241 of this book that Walsh and Wright “carried out a detailed study of various spaces of unlabelled graphs (...) including the space of all unlabeled graphs of order $n$” which seems to be what the OP is asking for.

Update (12/15/2012) : As requested in a comment, here are more precise statements :

Theorem 9.4 (p.236 in Bollobas' book). Let $M(n)$ be a function of $n$ such that $$ (*) \frac{2M(n)}{n}-\log(n) \to +\infty, \ \ \ \frac{2(2^{n \choose 2}-M(n))}{n}-\log(n) \to +\infty $$ Denote by ${\cal U}_{n,M(n)}$ the set of unlabeled graphs with $M(n)$ edges on $n$ vertices. Then $$ |{\cal U}_{n,M(n)}| \sim \frac{2^{n \choose 2}}{n!} $$

Theorem 9.5 (p.239 in Bollobas' book). Let $M(n)$ satisfy (*) as above. Let $Q$ be an isomorphism-invariant property of graphs. Denote by $l(Q,n)$ ($u(Q,n)$) the probability that a random (i.e, chosen with uniform probability in the finite set) labeled (unlabeled, respectively) graph with $n$ vertices and $M(n)$ edges has property $Q$. Then $l(Q,n) \sim u(Q,n)$.

Exercise 9.3 (p.249 in Bollobas’ book) : show that ${\sf lim \ inf}(\frac{l(Q,n)}{u(Q,n)})>1$ for $M(n)=\frac{n}{2}(\log(n)+x_n)$ where $x_n$ tends to a constant, and $Q$ is the property of having at least two isolated vertices.

  • $\begingroup$ Thank you for the answer. Could you please extend it and add the precise statement in the book as I do not have a copy here to fetch? $\endgroup$ – Jernej Nov 15 '12 at 8:41
  • 1
    $\begingroup$ @Jernej : as you can see, exercise 9.3 above strongly suggests that the answer to your question is NO in general : it should fail when $Q$ is a carefully constructed variant of the property “having two isolated vertices on $n$ vertices with $\frac{n}{2}\log(n)$ edges.” $\endgroup$ – Ewan Delanoy Nov 15 '12 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.