Which graph parameters are NOT concentrated on random graphs?

Question

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.

Answer 1

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 Yuval Peres. "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 2

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.