<p>Failure to concentrate happens for some counting ($\#\mathsf{P}$) properties, and maybe for many of them.</p>

<p>A simple example is the number of spanning subgraphs ($2^m$). The number of edges of a random graph fluctuates by $\pm \Theta(n)$ so the number of spanning subgraphs fluctuates by a factor of $2^{\Theta(n)}$, well away from the $(1+\epsilon)$ factor you are using in your definition of concentration.</p>

<p>To show that this is not an isolated example, here's an argument (not entirely rigorous but possibly able to be made rigorous) for why failure to concentrate should also be true of the number of Hamiltonian cycles. The expected value of this number is clearly $(n-1)!/2^{n+1}$: each of the $(n-1)!/2$ cyclic sequences of vertices has a $1/2^n$ chance of actually being a Hamiltonian cycle. By a similar argument, the expected amount of change to this number caused by introducing a new edge would be $(n-2)!/2^{n-1}$, smaller by a linear factor. If the number of Hamiltonian cycles were strongly concentrated, most edge flips would cause an amount of change to this number that is close to its expected value. But then the $\Theta(n)$ fluctuation in the number of edges would cause a fluctuation in the number of Hamiltonian cycles that is proportional to its expected value, contradicting the assumption of strong concentration.</p>

<p>Other plausible candidates for failure to concentrate include the number of colorings (partitions of the vertices into independent sets), number of matchings or perfect matchings, or number of spanning trees.</p>

CC BY-SA 3.0
2016-08-10T03:42:48.973Z
These are indeed interesting examples. Apparently, they all require parameters that can be exponentially large in $n$. I wonder if there is any meaningful non-concentrating parameter among those that are bounded by a polynomial of the graph size?
Andras Farago
CC BY-SA 3.0
2016-08-12T20:39:27.663Z
It would also be of interest to find natural properties that are non-concentrated even in the G(n,m) model of random graphs; the ones in this answer work only for G(n,p).
David Eppstein
CC BY-SA 3.0
2016-08-19T12:05:14.367Z
David's "counting argument" answers are always so insightful to me. :D
Daniel Apon
CC BY-SA 3.0
2016-08-09T21:02:49.040Z
2016-08-09T21:02:49.040Z
David Eppstein
<p>Many parameters  of the largest connected component are not concentrated for <span class="math-container">$G(n,p)$</span> if <span class="math-container">$p=1/n$</span> and more generally if <span class="math-container">$p$</span> is in the critical window. Examples are the diameter and the size of the largest component, the size of the second largest component, the number of leaves the component has, etc.</p>

<p>See e.g.  </p>

<p>Aldous, David. "Brownian excursions, critical random graphs and the multiplicative coalescent." The Annals of Probability (1997): 812-854.</p>

<p>Nachmias, Asaf, and Yuval Peres. "Critical random graphs: diameter and mixing time." The Annals of Probability 36, no. 4 (2008): 1267-1286.</p>

<p>Addario-Berry, Louigi, Nicolas Broutin, and Christina Goldschmidt. "The continuum limit of critical random graphs." Probability Theory and Related Fields 152, no. 3-4 (2012): 367-406.</p>

CC BY-SA 4.0
2019-06-03T08:02:10.677Z
2019-06-03T08:02:10.677Z
Yuval Peres
<p>It is well known that many important graph parameters show (strong) concentration on random graphs, at least in some range of the edge probability. Some typical examples are the chromatic number, maximum clique,  maximum independent set, maximum matching, domination number, number of copies of a fixed subgraph, diameter, maximum degree, choice number (list coloring number), Lovasz $\theta$-number, tree width, etc. </p>

<p><strong>Question:</strong> Which are the exceptions, that is, meaningful graph parameters that are <strong>not</strong> concentrated on random graphs?</p>

<p><strong>Edit.</strong>
A possible definition of concentration is this:</p>

<p>Let $X_n$ be a graph parameter on $n$-vertex random graphs. We call it <em>concentrated</em>, if for every $\epsilon&gt;0$, it holds that 
$$\lim_{n\rightarrow\infty}\Pr\big((1-\epsilon)E(X_n)\leq X_n \leq (1+\epsilon)E(X_n)\big)=1.$$
The concentration is <em>strong</em>, if the probability approaches 1 at an exponential rate. But sometimes strong is used in a different sense, referring to the fact that the convergence remains true with a shrinking interval, yielding a possibly very narrow range. 
 For example, if $X_n$ is the minimum degree, then, for some range of the edge probability $p$,  one can prove 
$$\lim_{n\rightarrow\infty}\Pr\big(\lfloor E(X_n)\rfloor\leq X_n \leq \lceil E(X_n)\rceil\big)=1$$
which is the shortest possible interval (as the degree is integer, but the expected value may not be). </p>

<p><strong>Note:</strong> One can construct <em>artificial</em> exemptions from  the concentration rule. For example, let $X_n=n$, if the graph has an odd number of edges, and 0 otherwise. This is clearly not concentrated, but I would not consider it a <em>meaningful</em> parameter.</p>

CC BY-SA 3.0
2015-11-02T09:40:33.087Z
Please give the definition of  _strong concentration_ on random graphs.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-11-02T16:01:22.687Z
Likely the definition is "very high probability (1-exp) that parameter is in specific (small) range".
Suresh Venkat
CC BY-SA 3.0
2015-11-02T17:20:36.637Z
@MohammadAl-Turkistany I edited the question to include a definition.
Andras Farago
CC BY-SA 3.0
2015-11-02T19:05:08.477Z
possibly simple binary property(s) like connectivity? or maybe the idea is to exclude binary properties? think this maybe needs a better analysis of the random graph model. for [erdos-renyi](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model) graphs (isnt that what you have in mind?), connectivity itself goes through a threshold phenomenon.
vzn
CC BY-SA 3.0
2015-11-03T04:28:00.180Z
Must the concentration happen only at the expectation? I think the number of copies of a fixed subgraph $H$ is concentrated, but not around the expectation unless $H$ is balanced.
Aravind
CC BY-SA 3.0
2016-08-10T12:03:31.230Z
It's not a "standard parameter", but if you look to automorphisms then a random graph tends to have only trivial or small size automorphisms.
Marzio De Biasi
<graph-theory><pr.probability><random-graphs>
Which graph parameters are NOT concentrated on random graphs?
Andras Farago
# Which graph parameters are NOT concentrated on random graphs?

(Asked by: username_0 on 2015-11-02)

It is well known that many important graph parameters show (strong) concentration on random graphs, at least in some range of the edge probability. Some typical examples are the chromatic number, maximum clique, maximum independent set, maximum matching, domination number, number of copies of a fixed subgraph, diameter, maximum degree, choice number (list coloring number), Lovasz $\theta$-number, tree width, etc.

**Question:** Which are the exceptions, that is, meaningful graph parameters that are **not** concentrated on random graphs?

**Edit.**
A possible definition of concentration is this:

Let $X\_n$ be a graph parameter on $n$-vertex random graphs. We call it *concentrated*, if for every $\epsilon>0$, it holds that
$$\lim\_{n\rightarrow\infty}\Pr\big((1-\epsilon)E(X\_n)\leq X\_n \leq (1+\epsilon)E(X\_n)\big)=1.$$
The concentration is *strong*, if the probability approaches 1 at an exponential rate. But sometimes strong is used in a different sense, referring to the fact that the convergence remains true with a shrinking interval, yielding a possibly very narrow range.
For example, if $X\_n$ is the minimum degree, then, for some range of the edge probability $p$, one can prove
$$\lim\_{n\rightarrow\infty}\Pr\big(\lfloor E(X\_n)\rfloor\leq X\_n \leq \lceil E(X\_n)\rceil\big)=1$$
which is the shortest possible interval (as the degree is integer, but the expected value may not be).

**Note:** One can construct *artificial* exemptions from the concentration rule. For example, let $X\_n=n$, if the graph has an odd number of edges, and 0 otherwise. This is clearly not concentrated, but I would not consider it a *meaningful* parameter.

**Tags:** graph-theory, pr.probability, random-graphs

> **Comments:**
> **username_1**: Please give the definition of  _strong concentration_ on random graphs.  
> **username_2**: Likely the definition is "very high probability (1-exp) that parameter is in specific (small) range".  
> **username_0**: @MohammadAl-Turkistany I edited the question to include a definition.  
> **username_3**: possibly simple binary property(s) like connectivity? or maybe the idea is to exclude binary properties? think this maybe needs a better analysis of the random graph model. for [erdos-renyi](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model) graphs (isnt that what you have in mind?), connectivity itself goes through a threshold phenomenon.  
> **username_4**: Must the concentration happen only at the expectation? I think the number of copies of a fixed subgraph $H$ is concentrated, but not around the expectation unless $H$ is balanced.  
> **username_5**: It's not a "standard parameter", but if you look to automorphisms then a random graph tends to have only trivial or small size automorphisms.  

---

## 2 answers

### Answer by username_8 on 2019-06-03. Score: 7 | Accepted answer

Many parameters of the largest connected component are not concentrated for $G(n,p)$ if $p=1/n$ and more generally if $p$ is in the critical window. Examples are the diameter and the size of the largest component, the size of the second largest component, the number of leaves the component has, etc.

See e.g.

Aldous, David. "Brownian excursions, critical random graphs and the multiplicative coalescent." The Annals of Probability (1997): 812-854.

Nachmias, Asaf, and username_8. "Critical random graphs: diameter and mixing time." The Annals of Probability 36, no. 4 (2008): 1267-1286.

Addario-Berry, Louigi, Nicolas Broutin, and Christina Goldschmidt. "The continuum limit of critical random graphs." Probability Theory and Related Fields 152, no. 3-4 (2012): 367-406.


---

### Answer by username_6 on 2016-08-09. Score: 6

Failure to concentrate happens for some counting ($\#\mathsf{P}$) properties, and maybe for many of them.

A simple example is the number of spanning subgraphs ($2^m$). The number of edges of a random graph fluctuates by $\pm \Theta(n)$ so the number of spanning subgraphs fluctuates by a factor of $2^{\Theta(n)}$, well away from the $(1+\epsilon)$ factor you are using in your definition of concentration.

To show that this is not an isolated example, here's an argument (not entirely rigorous but possibly able to be made rigorous) for why failure to concentrate should also be true of the number of Hamiltonian cycles. The expected value of this number is clearly $(n-1)!/2^{n+1}$: each of the $(n-1)!/2$ cyclic sequences of vertices has a $1/2^n$ chance of actually being a Hamiltonian cycle. By a similar argument, the expected amount of change to this number caused by introducing a new edge would be $(n-2)!/2^{n-1}$, smaller by a linear factor. If the number of Hamiltonian cycles were strongly concentrated, most edge flips would cause an amount of change to this number that is close to its expected value. But then the $\Theta(n)$ fluctuation in the number of edges would cause a fluctuation in the number of Hamiltonian cycles that is proportional to its expected value, contradicting the assumption of strong concentration.

Other plausible candidates for failure to concentrate include the number of colorings (partitions of the vertices into independent sets), number of matchings or perfect matchings, or number of spanning trees.

> **Comments:**
> **username_0**: These are indeed interesting examples. Apparently, they all require parameters that can be exponentially large in $n$. I wonder if there is any meaningful non-concentrating parameter among those that are bounded by a polynomial of the graph size?  
> **username_6**: It would also be of interest to find natural properties that are non-concentrated even in the G(n,m) model of random graphs; the ones in this answer work only for G(n,p).  
> **username_7**: David's "counting argument" answers are always so insightful to me. :D  

---

