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$.

$\endgroup$
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}).$$

$\endgroup$
  • $\begingroup$ Thank you dear Prof. McKay. I did not care about similarity of the automorphisms!!! $\endgroup$ – Shahrooz Janbaz May 21 '17 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 May 26 '17 at 13:20
  • $\begingroup$ [length order $1/n$ $\mapsto$ length order $n$] $\endgroup$ – Ben Barber Jun 3 '17 at 9:55

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.