21
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Your definition of monotone is one of many possible definitions. In the combinatorial topology literature (e.g. many papers by Bjorner) monotone means "preserved under deletion of edges." Your definition is probably more sensible, since it allows both "monotone increasing" and "monotone decreasing" properties, but it's probably worth pointing out the potential for confusion. The page en.wikipedia.org/wiki/Hereditary_property lists a variety of meanings for the term monotone (none of which is the one used in the question). $\endgroup$
    – Dan Ramras
    Commented Sep 28, 2010 at 0:58
  • $\begingroup$ Apologies for any confusion caused. I believe "preserved under edge addition" (monotone increasing) and "preserved under edge deletion" (monotone decreasing) are both fairly standard, and I mean to consider both here, even though this isn't really a richer class of properties than each on its own, since a monotone increasing parameter is just the negation of a monotone decreasing parameter. The main reason I included both is so I could mention the intersection of two monotone properties in a way that is not monotone. $\endgroup$
    – Matthew Kahle
    Commented Sep 28, 2010 at 1:18

11 Answers 11

Reset to default
19
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Can you clarify "the property of being rigid" a bit more? $\endgroup$
    – j.c.
    Commented Mar 8, 2011 at 15:47
  • $\begingroup$ A mathematical structure is rigid if it has no nontrivial automorphisms. This property is not monotone on graphs, since there are rigid graphs, but neither the empty graph nor the complete graph is rigid (when there are at least two vertices). $\endgroup$
    – Joel David Hamkins
    Commented Mar 8, 2011 at 16:28
  • $\begingroup$ Thanks! As I've been thinking recently about rigidity of graph embeddings, the overlapping terminology threw me for a loop. (Infinitesimal) rigidity in the other sense is determined by the rank of a matroid, and hence is monotone. $\endgroup$
    – j.c.
    Commented Mar 9, 2011 at 2:01
14
$\begingroup$

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

Improve this answer
$\endgroup$
12
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks -- this is exactly the kind of thing that I was hoping to find out about. $\endgroup$
    – Matthew Kahle
    Commented Sep 28, 2010 at 1:42
12
$\begingroup$

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.

Improve this answer
$\endgroup$
0
10
$\begingroup$

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?

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, this is interesting. I will look at your paper, but do you know: if you define diameter in this way is it roughly unimodal in p for random graphs, or is it more complicated than that? $\endgroup$
    – Matthew Kahle
    Commented Sep 28, 2010 at 21:09
  • 2
    $\begingroup$ Yes it is roughly unimodal. On a crude scale (p=c/n), it is logarithmic and increasing in c for c < 1, it jumps to order $n^{1/3}$ for $c=1$, and then it drops back to logarithmic and decreasing for $c>1$. If you parameterize $p$ more finely near $1/n$ you see more interesting behaviour emerge. Key papers by Luczak in the barely-below-(1/n) case, and by Riordan and Wormald (arxiv.org/abs/0808.4067) and Ding, Kim, Lubetzky and Peres (tinyurl.com/supdiam) in the barely-above-(1/n) case. $\endgroup$
    – Louigi Addario-Berry
    Commented Sep 28, 2010 at 23:59
9
$\begingroup$

Some natural non-monotone properties:

  • The property of being regular
  • The property of being a tree
  • The property of being Eulerian
Improve this answer
$\endgroup$
6
$\begingroup$

Gracefulness and harmoniousness are not monotone.

Improve this answer
$\endgroup$
5
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ But has it been studied for random graphs? Please edit if you know something about this! $\endgroup$
    – Dan Ramras
    Commented Sep 28, 2010 at 0:32
  • 2
    $\begingroup$ It isn't? News to me. $\endgroup$
    – Louigi Addario-Berry
    Commented Sep 28, 2010 at 0:34
  • 1
    $\begingroup$ A fact (not proven) from Diestel comes to mind: The random graph with probability of edge inclusion equal to $(1 + \epsilon)(\log n)n^{-1}$ is almost surely Hamiltonian. $\endgroup$
    – Austin Mohr
    Commented Sep 28, 2010 at 0:37
  • 1
    $\begingroup$ In my defense, I was thinking of a different definition of monotone, which is that the property is preserved under deletion of edges. I'll edit. According to wikipedia, this is one of many definitions of monotone used in the literature: en.wikipedia.org/wiki/Hereditary_property $\endgroup$
    – Dan Ramras
    Commented Sep 28, 2010 at 0:49
  • 1
    $\begingroup$ Yes, I am asking about properties that are either preserved under addition of edges or preserved under deletion of edges. The threshold for Hamiltonicity is $p = (\log{n} + \log\log{n}) / n $ and a proof can be found in Bollobas's book, "Random graphs." $\endgroup$
    – Matthew Kahle
    Commented Sep 28, 2010 at 1:03
0
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .