2
$\begingroup$

Let $\alpha>1$ be a constant and define $B_n$ as the number of (labeled) balanced graphs with $n$ vertices and $\left\lceil \alpha n\right\rceil $ edges. The paper Strongly Balanced Graphs and Random Graphs by A. Ruciński and A. Vince implies that $B_n\geq1$. What better lower bounds are known? In particular, is it known to be bounded from below by $n^{(1+o(1))\alpha n}$?

Edit: adding a definition of balanced graphs. The density of a graph $G$ with $v$ vertices and $e$ edges is $$\mathrm{den}(G)=\frac{e}{v}$$ A graph $G$ is balanced if $\mathrm{den}(G)\geq \mathrm{den}(H)$ for every subgraph $H$ of $G$. Balanced graphs appear naturally when counting copies of a given graph in the random graph, as explained in the paper I referred to.

Improve this question
$\endgroup$
2
  • $\begingroup$ Adding a definition would enhance your chance of getting a good response. $\endgroup$
    – Brendan McKay
    Commented Aug 10, 2022 at 15:52
  • $\begingroup$ @BrendanMcKay Thanks, I edited $\endgroup$
    – 35T41
    Commented Aug 10, 2022 at 17:24

1 Answer 1

Reset to default
2
$\begingroup$

The bound of Ruciński and Vince is for strongly balanced, which is a more strict condition. If only balanced is required, the example of connected regular graphs provides a bound much greater than $n^{\Omega(n)}$.

The total number of regular graphs with $n$ vertices is $$\alpha(n) \frac{2^{n^2/2}\sqrt{2e}}{\pi^{n/2} n^{n/2}},$$ where $\alpha(n)$ is a constant depending on $n\pmod{4}$.

B. D. McKay and N. C. Wormald, Asymptotic enumeration by degree sequence of graphs of high degree, European J. Combin., 11 (1990) 565-580.

Note that the formula is stated for all regular graphs, not necessarily connected, but the vast majority of regular graphs are connected. (All degrees apart from 0,1,2 guarantee almost sure connectivity.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Great, only balanced is required and this exactly what I was looking for. Thank you! $\endgroup$
    – 35T41
    Commented Aug 11, 2022 at 5:57
  • $\begingroup$ Dear Brendan, I'm taking a closer look and now I see that there's one condition missing, and it is the average degree. I need to count only graphs with density close to $1/\alpha$, which means average degree $2/\alpha$. Regular graphs do not generally cover this case, as the average degree can be fractional. Maybe something in the same nature can be said about almost regular graphs (in which $\Delta=\delta+1$)? $\endgroup$
    – 35T41
    Commented Aug 14, 2022 at 8:05
  • $\begingroup$ Right. Such near-regular graphs are not always balanced but I suspect most of them are. With a rough calculation I think the requirement is that for any subset $U$ of vertices, the number of edges between $U$ and $V$ is at least $|U|(n-|U|)/n$. Needs checking! $\endgroup$
    – Brendan McKay
    Commented Aug 14, 2022 at 10:13

You must log in to answer this question.

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