It seems that many, if not almost all, of the properties studied in graph theory are monotone. (Property means it is invariant under permutation of vertices, and monotone means that the property is either preserved under addition or deletion of edges, fixing the vertex set.) For example: connected, planar, triangle-free, bipartite, etc. Many quantitative graph invariants can also be considered monotone graph properties, e.g. chromatic number $\ge k$ or girth $\ge g$.
My question is whether there are non-monotone graph
properties which are well studied, or which arise naturally.
An obvious class of examples is the intersection of a monotone increasing and monotone decreasing property: for example graphs with chromatic number $\ge k$ and girth $\ge g$. (It is not entirely obvious if you intersect two such properties that they will have a nonempty intersection — in this case it is a well-known theorem in graph theory.
Another example is the presence of induced subgraphs isomorphic to $H$ for any graph $H$. Adding edges only increases the number of subgraphs, but it can destroy the property of being induced.
I am especially interested to hear if any non-monotone properties have been studied for random graphs. A famous theorem of Friedgut and Kalai is that every monotone graph property has a sharp threshold, and I would like to know about any examples of sharp thresholds for non-monotone properties.
Best Answer
There are a large number of natural graph properties that are not monotone.
The property of being isomorphic to a given graph is never monotone (except for the empty graph and the complete graph).
For example, the property of being the random graph is not monotone, since neither the empty graph nor the complete graph is random.
The property of satisfying a given complete nontrivial first order theory (this includes the random graph, which is first order expressible) is not monotone.
The property of being a tree (as opposed to a forest) is not monotone.
The property of being a disjoint collection of cycles is not monotone.
The property of being many disjoint copies of a single fixed graph is not monotone.
The property of having a vertex transitive automorphism group action is not monotone.
The property of being rigid is not monotone.
The property of being a Cayley graph of some group is not monotone.
The property of being transitive (for directed graphs) is not monotone.