What are some good examples of non-monotone graph properties? - MathOverflow

What are some good examples of non-monotone graph properties?

2010-09-28T00:12:04Z

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.

Answer by Thierry Zell for What are some good examples of non-monotone graph properties?

2010-09-28T00:27:32Z

The boxicity of a graph G is the smallest dimension d such that G is the intersection graph of sets made up of products of d intervals. If you delete all edges or add all edges, the boxicity becomes 1 (resp. 0).

Answer by Dan Ramras for What are some good examples of non-monotone graph properties?

2010-09-28T00:30:44Z

The property of having a Hamiltonian cycle (Hamiltonicity?) is not monotone.

Edit: this is only true if "monotone" is taken to mean that the property is preserved under deletion of edges.

Answer by Joel David Hamkins for What are some good examples of non-monotone graph properties?

2010-09-28T00:31:22Z

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.

Answer by Louigi Addario-Berry for What are some good examples of non-monotone graph properties?

2010-09-28T00:44:26Z

One whole family comes from considering properties that are monotone for connected graphs but can change when the connectivity changes. For example: the diameter of a graph -- defined to be the maximum of the diameters of its connected components, which is more informative than saying a disconnected graph has diameter infinity -- is monotone decreasing as edges are added, once the graph is already connected. But starting from a graph with no vertices, say, this diameter will at least at first increase as edges are added.

This property has by now been quite well-studied for random graphs and I think it's fair to say it's well-understood. We give an overview of known results near the critical point for the random graph $G_{n,p}$ in the introduction of this paper but due to a host of people, the diameter of $G_{n,p}$ is more or less completely understood for all $p$.

Here is a non-monotone property related to the diameter: graph spread, introduced by Alon, Boppana, and Spencer. Spread is defined as follows: Let $G=(V,E)$ be a connected graph and let $U$ be a uniformly random vertex of $G$. Then for a function $f:V\to \mathbb{R}$ define $\mathbf{V}(f)$ to be the variance of $f(U)$. The spread of $G$ is then defined to be the supremum of $\mathbf{V}(f)$ over all Lipschitz functions $f$ on $G$ (by Lipschitz I mean that $|f(u)-f(v)|\leq 1$ whenever $uv \in E$).

Again, for a disconnected graph define the spread to be the maximum over all connected components. Then again this is non-monotone and again the phase transition for $G_{n,p}$ has been studied.

Perhaps the result of Friedgut and Kalai can be extended to cover these kinds of "monotone on-connected-graphs" properties?

Answer by Tony Huynh for What are some good examples of non-monotone graph properties?

2010-09-28T00:46:30Z

What about the property of being perfect? Certainly this is an important graph property and it clearly is not monotone.

Answer by Robin Kothari for What are some good examples of non-monotone graph properties?

2010-09-28T00:48:44Z

Some natural non-monotone properties:

The property of being regular
The property of being a tree
The property of being Eulerian

Answer by Kevin P. Costello for What are some good examples of non-monotone graph properties?

2010-09-28T01:37:22Z

The property of having a non-singular adjacency matrix is non-monotone. For example, the path on four vertices has a full-rank adjacency matrix, but closing the path into a cycle reduces the rank by $2$ (the two pairs of opposite vertices correspond to equal rows in the adjacency matrix). Conversely, closing the path on three vertices into a triangle converts a singular adjacency matrix into a non-singular one.

This does turn out to have a sharp threshold though, as I showed with Van Vu. The situation is similar to that for the graph becoming connected: The property fails automatically when the graph has isolated vertices, and this turns out to be the main obstruction. The graph becomes connected/the matrix becomes non-singular at $\frac{\log n}{n}$.

A curious consequence of the non-monotonicity here is that there's also (likely) a sharp threshold at the other end of the spectrum. For $p$ exceptionally close to $1$, pairs of equal rows start cropping up again in the adjacency matrix (e.g. when the complement of $G$ contains an isolated edge). However, we don't know whether that's the main source of dependency in this range or if the threshold occurs sooner.

Answer by Jonah Ostroff for What are some good examples of non-monotone graph properties?

2010-09-28T12:52:11Z

Gracefulness and harmoniousness are not monotone.

Answer by gowers for What are some good examples of non-monotone graph properties?

2010-09-28T13:49:12Z

Bollobás gave an invited lecture at the ICM in 1998, in which he discussed hereditary properties of graphs -- that is, properties that are inherited by induced subgraphs (as opposed to arbitrary subgraphs). Many results that are known for monotone properties have counterparts for hereditary properties, but actually formulating and proving them is often quite a bit harder. So it might be worth looking at his article in the ICM proceedings (available online now that all ICM proceedings are available online), partly for the article itself and partly for the references it contains.

Answer by Hugh J for What are some good examples of non-monotone graph properties?

2010-09-30T16:07:48Z

Consider a property $A$ and an edge $e$. You can consider the following property: does the occurence of property $A$ depends on the state of the edge $e$ (i.e., is $e$ pivotal ?) ?

This kind of event is related to Russo-Margulis formula (and therefore appears quite often, for example in the work of Friedgut and Kalai).

Answer by Jon Noel for What are some good examples of non-monotone graph properties?

2011-02-09T01:08:31Z

Some variations of colouring problems are not monotone. For example, consider the following problem from ScienceDirect.

For a fixed graph $G$ and integer $k\geq\chi(G)$ consider the $k$-colour graph $\mathscr{C}_k(G)$ on the set of all $k$-colourings of $G$ where colourings $f$ and $g$ are adjacent if $f(v)\neq g(v)$ for exactly one vertex $v$ of $G$. Say that $G$ is $k$-mixing if the $k$-colour graph is connected.

For $n\geq3$ the complete bipartite graph $K_{n,n}$ is $k$-mixing whenever $k\geq3$, but the cocktail party graph with $n$ couples (obtained by deleting edges from $K_{n,n}$) is not $n$-mixing. See the examples in the paper above.