22
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ Please give the definition of strong concentration on random graphs. $\endgroup$ – Mohammad Al-Turkistany Nov 2 '15 at 9:40
  • $\begingroup$ Likely the definition is "very high probability (1-exp) that parameter is in specific (small) range". $\endgroup$ – Suresh Venkat Nov 2 '15 at 16:01
  • $\begingroup$ @MohammadAl-Turkistany I edited the question to include a definition. $\endgroup$ – Andras Farago Nov 2 '15 at 17:20
  • $\begingroup$ 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 graphs (isnt that what you have in mind?), connectivity itself goes through a threshold phenomenon. $\endgroup$ – vzn Nov 2 '15 at 19:05
  • 2
    $\begingroup$ 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. $\endgroup$ – Aravind Nov 3 '15 at 4:28
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Andras Farago Aug 10 '16 at 3:42
  • 1
    $\begingroup$ 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). $\endgroup$ – David Eppstein Aug 12 '16 at 20:39
  • $\begingroup$ David's "counting argument" answers are always so insightful to me. :D $\endgroup$ – Daniel Apon Aug 19 '16 at 12:05

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.