3
$\begingroup$

Maybe this question is off topic or duplicate, but maybe there is some information which I am not aware of.

Let $G_n$ denote the set of non-isomorphic simple graphs and $|G_n|=g_n$. Also, let $U_{n,m}$ denote the set of non-isomorphic simple graphs with $n$ vertices and $m$ edges, and $|U_{n,m}|=u_{n,m}$. I am interested in the below limit:

$$\lim_{n\rightarrow \infty}{T_n=\frac{\sum\limits_{m=1}^{\binom{n}{2}}{\binom{u_{n,m}}{2}}}{\binom{g_n}{2}}}.$$

The sequence $T_n$ shows the probability that two graphs among graphs with $n$ vertices have the same number of edges. Is it possible that the above limit exists and is not equal to zero?

Maybe this observation helps to see something. We have $$u_{n,1}+\cdots+u_{n,\binom{n}{2}}=g_n,$$

so, $$\binom{u_{n,1}}{2}+\cdots+\binom{u_{n,\binom{n}{2}}}{2}=\binom{g_n}{2}-\sum\limits_{1\leq i<j\leq \binom{n}{2}}{u_{n,i}u_{n,j}}.$$

Therefore, we can write $T_n$ as follows

$$T_n=1-\frac{\sum\limits_{1\leq i<j\leq \binom{n}{2}}{u_{n,i}u_{n,j}}}{\binom{g_n}{2}}.$$

Some numerical results: $T_4=0.09090909091, T_5=0.1051693405, T_6=0.1055417701, T_7= 0.09997318375,$ $T_8=0.09345209613, T_9=0.08721068637, T_{10}=0.08077014830$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

Since the vast majority graphs has trivial groups, and this is even more true (to exponential precision) for graphs with likely numbers of edges, the answer will be the same if you consider labelled graphs. This makes it a simple exercise if you know the identity $$2^{-2N} \sum_{i=0}^N \binom Ni^2 = \frac{\Gamma(N+\frac12)}{\sqrt{\pi}\,N!}.$$

I get $$\frac{\sqrt{2}}{\sqrt{\pi}\,n} + O(n^{-2}).$$

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you dear Prof. McKay. I did not care about similarity of the automorphisms!!! $\endgroup$
    – Shahrooz
    Commented May 21, 2017 at 18:29
  • 1
    $\begingroup$ @ShahroozJanbaz, to predict the $1/n$ decay (and hence limit $0$) without doing any computation you can use the fact that a random graph has binomial $B(\binom n 2, 1/2)$ edges, which is (i) concentrated in an interval of length order $1/n$ about its mean and (ii) does take values at either end of the range fairly often. So very roughly you are looking for the probability that two random choices from a set of size $n$ agree, which is of order $1/n$. $\endgroup$
    – Ben Barber
    Commented May 26, 2017 at 13:20
  • $\begingroup$ [length order $1/n$ $\mapsto$ length order $n$] $\endgroup$
    – Ben Barber
    Commented Jun 3, 2017 at 9:55

You must log in to answer this question.

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