Threshold behavior for non-monotone graph properties

One of my research interests is what you might call non-monotone graph properties.

A seminal result of Erdős and Rényi is that if p \ll \log{n} / n, then the random graph G(n,p) is a.a.s. disconnected, while if p \gg \log{n} /n then G(n,p) is a.a.s. connected. This can be made more precise; for example, if p = \frac{\log{n} + c}{n}, with c \in \mathbb{R}, then \mbox{Pr}[G(n,p) \mbox{ is connected }] \to e^{-e^{-c}} as n \to \infty. Connectivity is an example of a monotone graph property, meaning a set of graphs either closed under edge deletion or edge contraction. Other examples would be triangle-free, k-colorable, and less than five components. The fact that every monotone graph property has a sharp threshold is a celebrated theorem of Friedgut and Kalai.

More generally, a graph property is a way of assigning numbers to finite graphs that is invariant under graph isomorphism, and increases or decreases with edge deletion or addition. Examples would be the number of triangle subgraphs, chromatic number, and number of connected components.

Much of random graph theory is concerned with monotone properties of random graphs. But it is not hard to think of examples of non-monotone properties. For example, let i = the number of induced four-cycle subgraphs. Another example would be j = the number of complete K_3-subgraphs that are not contained in any K_4-subgraph. When p is very large,  p \gg n^{-1/3}, then a.a.s. every three vertices share some common neighbor, so every K_3-subgraph is contained in a K_4-subgraph and j=0. Similarly, when p is very small, p \ll n^{-1}, then a.a.s. there are no K_3 subgraphs, and j=0. For intermediate values of p, n^{-1/3} \ll p \ll n^{-1}, the expected value of j is E[j] = \theta (n^3 p^3).

So the expected value of the graph property is unimodal in edge density, and we still have threshold behavior. Can Friedgut and Kalai’s result be extended to a more general setting that includes these cases?

This is a simple and perhaps natural combinatorial example, but my original motivation was topological. I wrote a paper about topological properties of random clique complexes, available on the arXiv, which turn out to be non-monotone generalizations of the original Erdős-Rényi theorem. I will continue to write more about this and other related examples sometime soon, and as I have time, but in the meantime if anyone knows any nice examples of non-monotone graph properties, please leave a comment.

One more thought for now. It seems in many of the most natural examples we have of non-monotone properties F, the expected value of F over the probability space G(n,p) is basically a unimodal function in the underlying parameter p. Can you give any natural examples of bimodal or multimodal graph properties? (Pathological examples?)

About these ads

One thought on “Threshold behavior for non-monotone graph properties

  1. Gil Kalai says:

    Dear Matthew

    This is a very good question and a good answer may find applications in graph theory and also in percolation and other related models.

Leave a Reply


You are commenting using your account. Log Out / Change )

Twitter picture


Facebook photo


Google+ photo


Connecting to %s