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 , then the random graph is a.a.s. disconnected, while if then is a.a.s. connected. This can be made more precise; for example, if with , then as . 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 the number of induced four-cycle subgraphs. Another example would be the number of complete -subgraphs that are not contained in any -subgraph. When is very large, , then a.a.s. every three vertices share some common neighbor, so every -subgraph is contained in a -subgraph and . Similarly, when is very small, , then a.a.s. there are no subgraphs, and . For intermediate values of , , the expected value of is .
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 , the expected value of over the probability space is basically a unimodal function in the underlying parameter . Can you give any natural examples of bimodal or multimodal graph properties? (Pathological examples?)