In search of a counterexample to the Lovász conjecture

It is a celebrated result of John Dixon, (The probability of generating the symmetric group, (subscription) Math. Z. 110 (1969), 199–205.) that if one choose two random permutations in the symmetric group S_n, uniformly (i.e. each with probability 1 / n!), and independently, the probability that the two permutations generate the whole group tends to 3/4 as n \to \infty. It is clear that this probability will never be greater than 3/4, since there is a 1/4 probability that the two permutations will both be even, in which case you could only generate, at most, the alternating group. Interestingly enough, Dixon’s paper covers this possibility, and he actually shows that the probability that two permutations generate the alternating group tends to 1/4 as n \to \infty.

Equivalently, if two random elements x, y of the alternating group A_n are chosen uniformly and randomly, the probability that they generate the group tends to 1 as n \to \infty. This leads me to my question — what is the probability that the 4-regular Cayley graph with generators x, y , x^{-1}, y^{-1} is not Hamiltonian, as n \to \infty?

Showing that this probability is bounded away from 0 would provide a counterexample for a notorious problem about vertex-transitive graphs. So we might expect that this is hard. But is it even possible that it is true, or is there some obvious reason that such graphs will tend to be Hamiltonian?

Another approach in the same spirit would be computational rather than asymptotic. Suppose we look at thousands of random Cayley graphs on the alternating groups A_5 and A_6, for example. It is straightforward to check that they are connected. Is it within reach for a cleverly designed algorithm on modern computers to conclusively rule out Hamiltonicity for a 4-regular graph on 60 or 360 vertices? I would also be happy with a computer-aided proof that the conjecture is false.

Historical note: It is called the Lovász conjecture, even though he just asked the question (and perhaps conjectured the other way). I am under the impression that some prominent people in this field have felt that the answer should be no. In particular Babai does not believe it.

Packing tetrahedra

Last spring I saw a great colloquium talk on packing regular tetrahedra in space by Jeffrey Lagarias. He pointed out that in some sense the problem goes back to Aristotle, who apparently claimed that they tile space. Since Aristotle was thought to be infallible, this was repeated throughout the ages until someone (maybe Minkowski?) noticed that they actually don’t.

John Conway and Sal Torquato considered various quantitative questions about packing, tiling, and covering, and in particular asked about the densest packing of tetrahedra in space. They optimized over a very special kind of periodic packing, and in the densest packing they found, the tetrahedra take up about 72% of space.

Compare this to the densest packing of spheres in space, which take up about 74%. If Conway and Torquato’s example was actually the densest packing of tetrahedra, it would be a counterexample to Ulam’s conjecture that the sphere is the worst case scenario for packing.

But a series of papers improving the bound followed, and as of early 2010 the record is held by Chen, Engel, and Glotzer with a packing fraction of 85.63%.

I want to advertise two attractive open problems related to this.

(1) Good upper bounds on tetrahedron packing.

At the time of the colloquium talk I saw several months ago, it seemed that despite a whole host of papers improving the lower bound on tetrahedron packing, there was no upper bound in the literature. Since then Gravel, Elser, and Kallus posted a paper on the arXiv which gives an upper bound. This is very cool, but the upper bound on density they give is something like 1- 2.6 \times 10^{-25}, so there is still a lot of room for improvement.

(2) Packing tetrahedra in a sphere.

As far as I know, even the following problem is open. Let’s make our lives easier by discretizing the problem and we simply ask how many tetrahedra we can pack in a sphere. Okay, let’s make it even easier: the edge length of each of the tetrahedra is the same as the radius of the sphere. Even easier: every one of the tetrahedra has to have one corner at the center of the sphere. Now how many tetrahedra can you pack in the sphere?

It is fairly clear that you can get 20 tetrahedra in the sphere, since the edge length of the icosahedron is just slightly longer than the radius of its circumscribed sphere. By comparing the volume of the regular tetrahedron to the volume of the sphere, we get a trivial upper bound of 35 tetrahedra. But by comparing surface area instead, we get an upper bound of 22 tetrahedra.

There is apparently a folklore conjecture that 20 tetrahedra is the right answer, so proving this comes down to ruling out 21 or 22. To rule out 21 seems like a nonlinear optimization problem in some 63-dimensional space.

I’d guess that this is within the realm of computation if someone made some clever reductions. Oleg Musin settled the question of the kissing number in 4-dimensional space in 2003. To rule out kissing number of 25 is essentially optimizing some function over a 75-dimensional space. This sounds a little bit daunting, but it is apparently much easier than Thomas Hales’s proof of the Kepler conjecture. (For a nice survey of this work, see this article by Pfender and Ziegler.)

The fundamental group of random 2-complexes

Eric Babson, Chris Hoffman, and I recently posted major revisions of our preprint, “The fundamental group of random 2-complexes” to the arXiv. This article will appear in Journal of the American Mathematical Society. This note is intended to be a high level summary of the main result, with a few words about the techniques.

The Erdős–Rényi random graph G(n,p) is the probability space on all graphs with vertex set [n] = \{ 1, 2, \dots, n \}, with edges included with probability p, independently. Frequently p = p(n) and n \to \infty, and we say that G(n,p) asymptotically almost surely (a.a.s) has property \mathcal{P} if \mbox{Pr} [ G(n,p) \in \mathcal{P} ] \to 1 as n \to \infty.

A seminal result of Erdős and Rényi is that p(n) = \log{n} / n is a sharp threshold for connectivity. In particular if p > (1+ \epsilon) \log{n} / n, then G(n,p) is a.a.s. connected, and if p < (1- \epsilon) \log{n} / n, then G(n,p) is a.a.s. disconnected.

Nathan Linial and Roy Meshulam introduced a two-dimensional analogue of G(n,p), and proved an analogue of the Erdős-Rényi theorem. Their two-dimensional analogue is as follows: let Y(n,p) denote the probability space of all 2-dimensional (abstract) simplicial complexes with vertex set [n] and edge set {[n] \choose 2} (i.e. a complete graph for the 1-skeleton), with each of the { n \choose 3} triangles included independently with probability p.

Linial and Meshulam showed that p(n) = 2 \log{n} / n is a sharp threshold for vanishing of first homology H_1(Y(n,p)). (Here the coefficients are over \mathbb{Z} / 2. This was generalized to \mathbb{Z} /p for all p by Meshulam and Wallach.) In other words, once p is much larger than 2 \log{n} / n, every (one-dimensional) cycle is the boundary of some two-dimensional subcomplex.

Babson, Hoffman, and I showed that the threshold for vanishing of \pi_1 (Y(n,p)) is much larger: up to some log terms, the threshold is p = n^{-1/2}. In other words, you must add a lot more random two-dimensional faces before every cycle is the boundary of not any just any subcomplex, but the boundary of the continuous image of a topological disk. A precise statement is as follows.

Main result Let \epsilon >0 be arbitrary but constant. If p \le n^{-1/2 - \epsilon} then \pi_1 (Y(n,p)) \neq 0, and if p \ge n^{-1/2 + \epsilon} then \pi_1 (Y(n,p)) = 0, asymptotically almost surely.

It is relatively straightforward to show that when p is much larger than n^{-1/2}, a.a.s. \pi_1 =0. Almost all of the work in the paper is showing that when p is much smaller than n^{-1/2} a.a.s. \pi_1 \neq 0. Our methods depend heavily on geometric group theory, and on the way to showing that \pi_1 is non-vanishing, we must show first that it is hyperbolic in the sense of Gromov.

Proving this involves some intermediate results which do not involve randomness at all, and which may be of independent interest in topological combinatorics. In particular, we must characterize the topology of sufficiently sparse two-dimensional simplicial complexes. The precise statement is as follows:

Theorem. If \Delta is a finite simplicial complex such that f_2 (\sigma) / f_0(\sigma) \le 1/2 for every subcomplex \sigma, then \Delta is homotopy equivalent to a wedge of circle, spheres, and projective planes.

(Here f_i denotes the number of i-dimensional faces.)

Corollary. With hypothesis as above, the fundamental group \pi_1( \Delta) is isomorphic to a free product \mathbb{Z} * \mathbb{Z} * \dots * \mathbb{Z} / 2 * \mathbb{Z}/2, for some number of \mathbb{Z}‘s and \mathbb{Z} /2‘s.

It is relatively easy to check that if p = O(n^{-1/2 - \epsilon}) then with high probability subcomplexes of Y(n,p) on a bounded number of vertices satisfy the hypothesis of this theorem. (Of course Y(n,p) itself does not, since it has f_0 = n and roughly f_2 \approx n^{5/2} as p approaches n^{-1/2}.)

But the corollary gives us that the fundamental group of small subcomplexes is hyperbolic, and then Gromov’s local-to-global principle allows us to patch these together to get that \pi_1 ( Y(n,p) ) is hyperbolic as well.
This gives a linear isoperimetric inequality on pi_1 which we can “lift” to a linear isoperimetric inequality on Y(n,p).

But if Y(n,p) is simply connected and satisfies a linear isoperimetric inequality, then that would imply that every 3-cycle is contractible using a bounded number of triangles, but this is easy to rule out with a first-moment argument.

There are a number of technical details that I am omitting here, but hopefully this at least gives the flavor of the argument.

An attractive open problem in this area is to identify the threshold t(n) for vanishing of H_1( Y(n,p), \mathbb{Z}). It is tempting to think that t(n) \approx 2 \log{n} / n, since this is the threshold for vanishing of H_1(Y(n,p), \mathbb{Z} / m) for every integer m. This argument would work for any fixed simplicial complex but the argument doesn’t apply in the limit; Meshulam and Wallach’s result holds for fixed m as n \to \infty, so in particular it does not rule out torsion in integer homology that grows with n.

As far as we know at the moment, no one has written down any improvements to the trivial bounds on t(n), that 2 \log{n} / n \le t(n) \le n^{-1/2}. Any progress on this problem will require new tools to handle torsion in random homology, and will no doubt be of interest in both geometric group theory and stochastic topology.

A conjecture concerning random cubical complexes

Nati Linial and Roy Meshulam defined a certain kind of random two-dimensional simplicial complex, and found the threshold for vanishing of homology. Their theorem is in some sense a perfect homological analogue of the classical Erdős–Rényi characterization of the threshold for connectivity of the random graph.

Linial and Meshulam’s definition was as follows. Y(n,p) is a complete graph on n vertices, with each of the {n \choose 3} triangular faces inserted independently with probability p, which may depend on n. We say that Y(n,p) almost always surely (a.a.s) has property \mathcal{P} if the probability that Y(n,p) \in \mathcal{P} tends to one as n \to \infty.

Nati Linial and Roy Meshulam showed that if \omega is any function that tends to infinity with n and if p = (\log{n} + \omega) / n then a.a.s H_1( Y(n,p) , \mathbb{Z} / 2) =0 , and if p = (\log{n} - \omega) / n then a.a.s H_1( Y(n,p) , \mathbb{Z} / 2)  \neq 0 .

(This result was later extended to arbitrary finite field coefficients and arbitrary dimension by Meshulam and Wallach. It may also be worth noting for the topologically inclined reader that their argument is actually a cohomological one, but in this setting universal coefficients gives us that homology and cohomology are isomorphic vector spaces.)

Eric Babson, Chris Hoffman, and I found the threshold for vanishing of the fundamental group \pi_1(Y(n,p)) to be quite different. In particular, we showed that if \epsilon > 0 is any constant and p \le n^{-1/2 -\epsilon} then a.a.s. \pi_1 ( Y(n,p) ) \neq 0 and if p \ge n^{ -1/2 + \epsilon} then a.a.s. \pi_1 ( Y(n,p) )  = 0 . The harder direction is to show that on the left side of the threshold that the fundamental group is nontrivial, and this uses Gromov’s ideas of negative curvature. In particular to show that the \pi_1 is nontrivial we have to show first that it is a hyperbolic group.

[I want to advertise one of my favorite open problems in this area: as far as I know, nothing is known about the threshold for H_1( Y(n,p) , \mathbb{Z}) , other than what is implied by the above results.]

I was thinking recently about a cubical analogue of the Linial-Meshulam set up. Define Z(n,p) to be the one-skeleton of the n-dimensional cube with each square two-dimensional face inserted independently with probability p. This should be the cubical analogue of the Linial-Mesulam model? So what are the thresholds for the vanishing of H_1 ( Z(n,p) , \mathbb{Z} / 2) and \pi_1 ( Z(n,p) ) ?

I just did some “back of the envelope” calculations which surprised me. It looks like p must be much larger (in particular bounded away from zero) before either homology or homotopy is killed. Here is what I think probably happens. For the sake of simplicity assume here that p is constant, although in realty there are o(1) terms that I am suppressing.

(1) If p  < \log{2} then a.a.s H_1 ( Z(n,p) , \mathbb{Z} /2 ) \neq 0, and if p  > \log{2} then a.a.s H_1 ( Z(n,p) , \mathbb{Z} /2 ) = 0.

(2) If p  < (\log{2})^{1/4} then a.a.s. \pi_1 ( Z(n,p) ) \neq 0, and if p > (\log{2})^{1/4} then a.a.s. \pi_1 ( Z(n,p) ) = 0.

Perhaps in a future post I can explain where the numbers \log{2} \approx 0.69315 and (\log{2})^{1/4} \approx 0.91244 come from. Or in the meantime, I would be grateful for any corroborating computations or counterexamples.

Topological Turán theory

I just came across the following interesting question of Nati Linial.

If a two-dimensional simplicial complex has n vertices and \Omega(n^{5/2}) faces, does it necessarily contain an embedded torus?

I want to advertise this question to a wider audience, so I’ll explain first why I think it is interesting.

First of all this question makes sense in the context of Turán theory, a branch of extremal combinatorics. The classical Turán theorem gives that if a graph on n vertices has more than \displaystyle{ \left( 1-\frac{1}{r} \right) \frac{n^2}{2} } edges then it necessarily contains a complete subgraph K_r on r vertices. This is tight for every r and n.

One could ask instead how many edges one must have before there is forced to be a cycle subgraph, where it doesn’t matter what the length of the cycle is. This is actually an easier question, and it is easy to see out that if one has n edges there must be a cycle.
It also seems more natural, in that it can be phrased topologically: how many edges must be added to n vertices before we are forced to contain an embedded image of the circle?

What is the right two-dimensional analogue of this statement? In particular, is there a constant C such that a two-dimensional simplicial complex with n vertices and at least C n^2 two-dimensional faces must contain an embedded sphere S^2? If so, then this is essentially best possible. By taking a cone over a complete graph on n-1 vertices, one constructs a two-complex on n vertices with {n -1 \choose 2} faces and no embedded spheres. Without having thought about it at all, I am not sure how to do better.

In any case, the corresponding question for torus seems more interesting, but for different reasons. In a paper with Eric Babson and Chris Hoffman we looked at the fundamental group of random two-complexes, as defined by Linial and Meshulam, and found the rough threshold for vanishing of the fundamental group. To show that the fundamental group was nontrivial when the number of faces was small required a lot of work — in particular, in order to apply Gromov’s local-to-global method for hyperbolicity, we needed to prove that the space was locally negatively curved, and this meant classifying the homotopy type of subcomplexes up to a large but constant size.

It turned out that the small subcomplexes were all homotopy equivalent to wedges of circles, spheres, and projective planes. In particular, we show that there are not any torus subcomplexes, at least not of bounded size. (Linial may have recently shown that there are not embedded tori, even of size tending to infinity with n.) On the other hand, just on the other side of the threshold embedded tori abound in great quantity. It is interesting that something similar happens in the density random groups of Gromov — that the threshold for vanishing of the density random group corresponds to the presence of tori subcomplex in the naturally associated two-complex. It is not clear to me if this is a general phenomenon, coming geometrically from the fact that a torus admits a flat metric.

Some of the great successes of the probabilistic method in combinatorics have been in existence proofs when constructions are hard or impossible to come by. It would be nice to have interesting or extremal topological examples produced this way. Nati’s question suggests an interesting family of extremal problems in topological combinatorics, and it might make sense that in certain cases, random simplicial complexes have nearly maximally many faces for avoiding a particular embedded subspace.

Update: Nati pointed me to the paper Sós, V. T.; Erdos, P.; Brown, W. G., On the existence of triangulated spheres in $3$-graphs, and related problems. Period. Math. Hungar. 3 (1973), no. 3-4, 221–228.
Here it is shown that n^{5/2} is the right answer for the sphere. Their lower bound is constructive, based on projective planes over finite fields. Nati said that being initially unaware of this paper, he found a probabilistic proof that works just as well as a lower bound for every fixed 2-manifold. So it seems that the main problem here is to find a matching upper bound for the torus.

The Rado complex

A simplicial complex is said to be flag if it is the clique complex of its underlying graph. In other words, one starts with the graph and add all simplices of all dimensions that are compatible with this 1-skeleton. A subcomplex F' of a flag complex F is said to be induced if it is flag, and if whenever vertices x, y \in  F' and \{ x,y \} is an edge of F, we also have that \{ x,y \} is an edge of F'.

Does there exist a flag simplicial complex \Delta with countably many vertices, such that the following extension property holds?

[Extension property] For every finite or countably infinite flag simplicial complex X and vertex v \in X, and for every embedding of X-v as an induced subcomplex i: X -v \hookrightarrow \Delta , i can be extended to an embedding \widetilde{i}: X \hookrightarrow \Delta of X as an induced subcomplex.

It turns out that such a \Delta does exist, and it is unique up to isomorphism (both combinatorially and topologically). Other interesting properties of \Delta immediately follow.

- \Delta contains homoemorphic copies of every finite and countably infinite simplicial complex as induced subcomplexes.

- The link of every face \sigma \in \Delta is homeomorphic to \Delta itself.

- The automorphism group of \Delta acts transitively on d-dimensional faces for every d.

- Deleting any finite number of vertices or edges of \Delta and the accompanying faces does not change its homeomorphism type.

Here is an easy way to describe \Delta. Take countably many vertices, say labeled by the positive integers. Choose a probability p such that 0 < p < 1, and for each pair of integers \{ m,n \}, connect m to n by an edge with probability p. Do this independently for every edge.

This is sometimes called the Rado graph, and because it is unique up to isomorphism (and in particular because it does not depend on p) it is sometimes also called the random graph. It is also possible to construct the Rado graph purely combinatorially, without resorting to probability. The \Delta I have in mind is of course just the clique complex of the Rado graph.

We can filter the complex \Delta by setting \Delta(n) to be the induced subcomplex on all vertices with labels \le n, and this allows us to ask more refined questions. (Now the choice of p affects the asymptotics, so we assume p = 1/2.) From the perspective of homotopy theory, \Delta is not a particularly interesting complex; it is contractible. (This is an exercise, one should check this if it is not obvious!) However, \Delta(n) has interesting topology.

As n \to \infty, the probability that \Delta(n) is contractible is going to 0. It was recently shown that \Delta(n) has asymptotically almost surely (a.a.s.) at least \Omega( \log{ \log{ n}} ) nontrivial homology groups, concentrated around dimension \log_2{n}. For comparison, the dimension of \Delta(n) is d \approx 2 \log_2{n}.

I think one can probably show using the techniques from this paper that there is a.a.s. no nontrivial homology above dimension d/2 or below dimension d/4. It is still not clear (at least to me) what happens between dimensions d/4 and d/2. It seems that a naive Morse theory argument can give that the expected dimension of homology is small in this range, but to show that it is zero would take a more refined Morse function. Perhaps a good topic for another post would be “Morse theory in probability.”

Another question: given a non-contractible induced subcomplex (say an embedded d-dimensional sphere) \Delta' \subset \Delta on a set S of k vertices, how many vertices f(k) should one expect to add to S before \Delta' becomes contractible in the larger induced subcomplex? For example, it seems that once you have added about 2^k vertices, it is reasonably likely that one of these vertices induces a cone over \Delta', but is it possible that the subcomplex becomes contractible with far fewer vertices added?

An application of disc packing to statistical mechanics

I recently posted an article to the arXiv, on a problem suggested by Persi Diaconis. “Hard discs in a box” is a classical setting in statistical physics. One very simple model of matter is as n non-overlapping (or hard) discs of radius r, bouncing around inside a unit square. This is a very well studied model in computational statistical physics, although not much seems to be known so far mathematically. In particular, the statistical physicists observe experimentally that there is a phase transition of some kind when \pi r^2 n  \approx 0.70.

The details of what exactly it means that there is a phase transition will have to be left for another post. But what is relevant for us here is how they sample a uniformly random configuration of hard discs, via the Metropolis algorithm. (Please see the recent survey article by Persi Diaconis in the Bulletin of the AMS.) Basically, one starts with the discs in a reasonable starting configuration, say evenly spaced along some lattice, and then one applies Metropolis, which means the following. Choose one of the n discs uniformly randomly, and make a small perturbation of its position. If this results in overlapping discs, or going out of the square, reject the move, otherwise accept it.

Under certain hypotheses on your space, one can show that this Markov chain converges to the uniform distribution on the space of all possible configurations. But to know this, one must know that the Markov chain is irreducible, and in particular that the configuration space is path connected.

Diaconis, Lebeau, and Michel observed that there is some constant c_1 such that if r \le  c_1 / n, the discs can always be freely rearranged, and in particular that the Metropolis Markov chain is irreducible. The real point of their article was to put useful upper bounds on the mixing time of Metropolis in general, and then they applied it to the hard discs setting as a motivating example. It would be nice if the same holds even in the range of the phase transition; in other words we would like to replace n in the above statement with \sqrt{n}.

However, their result is essentially best possible. In my recent preprint, I gave examples of stable configurations (meaning that no single disc can move) with r > c_2 / n. Here is a picture that should give some feeling for the main idea behind the construction.

A stable configuration of discs

There is still quite a lot to do here. As Persi points out in his survey article, these configuration spaces of hard discs are naturally endowed with a topological structure, as well as probability measure. In his survey article, he says, “very, very little is known about the topology of these spaces.”

At a workshop on, “Topological complexity of random sets,” this past week at the American Institute of Mathematics, Yuliy Baryshnikov, Peter Bubenik, and I were able to establish a connection to classical algebraic topology. In particular, if r < \frac{1}{2 n}, then the configuration space C(n; r) is not only path connected, but it is homotopy equivalent to the classical configuration space of n labeled points in the plane. It is fairly clear that this happens for some sufficiently small radius, but as far as we know, no one had put any quantitative bounds on it yet.

In another article, in preparation, I discuss the combinatorial aspects of these configuration spaces, and give an example of what I call a “transitionary” configuration, as a first attempt to give a heuristic explanation of the phase transition near \pi r^2 n =0.70. The disc packing example illustrated above might be more interesting to discrete geometers than to probabilists, since one would like to believe that examples like this are rather rare, in a measure theoretic sense. Nevertheless, we believe that deeply understanding the various geometric and topological features of these spaces, and how they change as r varies, might be a first step in explaining the phase transition mathematically.

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?)