What are some good examples of non-monotone graph properties? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T07:43:35Z http://mathoverflow.net/feeds/question/40230 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/40230/what-are-some-good-examples-of-non-monotone-graph-properties What are some good examples of non-monotone graph properties? Matthew Kahle 2010-09-28T00:12:04Z 2011-02-09T01:08:31Z <p>It seems that many, if not almost all, of the properties studied in graph theory are monotone. (<em>Property</em> means it is invariant under permutation of vertices, and <em>monotone</em> 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$.</p> <blockquote> <p>My question is whether there are non-monotone graph properties which are well studied, or which arise naturally.</p> </blockquote> <p>An obvious class of examples is the intersection of a monotone increasing and monotone decreasing property: for example graphs with chromatic number $\ge k$ <em>and</em> 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.</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/40230/what-are-some-good-examples-of-non-monotone-graph-properties/40232#40232 Answer by Thierry Zell for What are some good examples of non-monotone graph properties? Thierry Zell 2010-09-28T00:27:32Z 2010-09-28T00:27:32Z <p>The <em>boxicity</em> of a graph <em>G</em> is the smallest dimension <em>d</em> such that <em>G</em> is the intersection graph of sets made up of products of <em>d</em> intervals. If you delete all edges or add all edges, the boxicity becomes 1 (resp. 0).</p> http://mathoverflow.net/questions/40230/what-are-some-good-examples-of-non-monotone-graph-properties/40234#40234 Answer by Dan Ramras for What are some good examples of non-monotone graph properties? Dan Ramras 2010-09-28T00:30:44Z 2010-09-28T00:50:53Z <p>The property of having a Hamiltonian cycle (Hamiltonicity?) is not monotone. </p> <p>Edit: this is only true if "monotone" is taken to mean that the property is preserved under deletion of edges. </p> http://mathoverflow.net/questions/40230/what-are-some-good-examples-of-non-monotone-graph-properties/40235#40235 Answer by Joel David Hamkins for What are some good examples of non-monotone graph properties? Joel David Hamkins 2010-09-28T00:31:22Z 2010-09-28T00:48:48Z <p>There are a large number of natural graph properties that are not monotone. </p> <ul> <li><p>The property of being isomorphic to a given graph is never monotone (except for the empty graph and the complete graph). </p></li> <li><p>For example, the property of being <a href="http://en.wikipedia.org/wiki/Rado_graph" rel="nofollow">the random graph</a> is not monotone, since neither the empty graph nor the complete graph is random.</p></li> <li><p>The property of satisfying a given complete nontrivial first order theory (this includes the random graph, which is first order expressible) is not monotone. </p></li> <li><p>The property of being a tree (as opposed to a forest) is not monotone.</p></li> <li><p>The property of being a disjoint collection of cycles is not monotone.</p></li> <li><p>The property of being many disjoint copies of a single fixed graph is not monotone.</p></li> <li><p>The property of having a vertex transitive automorphism group action is not monotone.</p></li> <li><p>The property of being rigid is not monotone. </p></li> <li><p>The property of being a Cayley graph of some group is not monotone.</p></li> <li><p>The property of being transitive (for directed graphs) is not monotone.</p></li> </ul> http://mathoverflow.net/questions/40230/what-are-some-good-examples-of-non-monotone-graph-properties/40236#40236 Answer by Louigi Addario-Berry for What are some good examples of non-monotone graph properties? Louigi Addario-Berry 2010-09-28T00:44:26Z 2010-09-28T00:44:26Z <p>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, <em>once the graph is already connected</em>. But starting from a graph with no vertices, say, this diameter will at least at first increase as edges are added.</p> <p>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 <a href="http://arxiv.org/abs/0903.4730" rel="nofollow">this paper</a> but due to a host of people, the diameter of $G_{n,p}$ is more or less completely understood for all $p$. </p> <p>Here is a non-monotone property related to the diameter: graph spread, introduced by <a href="http://www.tau.ac.il/~nogaa/PDFS/iso7.pdf" rel="nofollow">Alon, Boppana, and Spencer</a>. 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$). </p> <p>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}$ <a href="http://arxiv.org/abs/0902.1156" rel="nofollow">has been studied</a>.</p> <p>Perhaps the result of Friedgut and Kalai can be extended to cover these kinds of "monotone on-connected-graphs" properties? </p> http://mathoverflow.net/questions/40230/what-are-some-good-examples-of-non-monotone-graph-properties/40237#40237 Answer by Tony Huynh for What are some good examples of non-monotone graph properties? Tony Huynh 2010-09-28T00:46:30Z 2010-09-28T00:46:30Z <p>What about the property of being <a href="http://en.wikipedia.org/wiki/Perfect_graph" rel="nofollow">perfect</a>? Certainly this is an important graph property and it clearly is not monotone. </p> http://mathoverflow.net/questions/40230/what-are-some-good-examples-of-non-monotone-graph-properties/40238#40238 Answer by Robin Kothari for What are some good examples of non-monotone graph properties? Robin Kothari 2010-09-28T00:48:44Z 2010-09-28T00:48:44Z <p>Some natural non-monotone properties:</p> <ul> <li>The property of being regular</li> <li>The property of being a tree</li> <li>The property of being Eulerian</li> </ul> http://mathoverflow.net/questions/40230/what-are-some-good-examples-of-non-monotone-graph-properties/40247#40247 Answer by Kevin P. Costello for What are some good examples of non-monotone graph properties? Kevin P. Costello 2010-09-28T01:37:22Z 2010-09-28T01:37:22Z <p>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. </p> <p>This does turn out to have a sharp threshold though, as I showed with <a href="http://arxiv.org/abs/math/0606414" rel="nofollow">Van Vu.</a> 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}$. </p> <p>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. </p> http://mathoverflow.net/questions/40230/what-are-some-good-examples-of-non-monotone-graph-properties/40310#40310 Answer by Jonah Ostroff for What are some good examples of non-monotone graph properties? Jonah Ostroff 2010-09-28T12:52:11Z 2010-09-28T12:52:11Z <p><a href="http://mathworld.wolfram.com/GracefulGraph.html" rel="nofollow">Gracefulness</a> and <a href="http://mathworld.wolfram.com/HarmoniousGraph.html" rel="nofollow">harmoniousness</a> are not monotone.</p> http://mathoverflow.net/questions/40230/what-are-some-good-examples-of-non-monotone-graph-properties/40317#40317 Answer by gowers for What are some good examples of non-monotone graph properties? gowers 2010-09-28T13:49:12Z 2010-09-28T13:49:12Z <p>Bollob&aacute;s gave an invited lecture at the ICM in 1998, in which he discussed <em>hereditary</em> 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.</p> http://mathoverflow.net/questions/40230/what-are-some-good-examples-of-non-monotone-graph-properties/40637#40637 Answer by Hugh J for What are some good examples of non-monotone graph properties? Hugh J 2010-09-30T16:07:48Z 2010-09-30T16:07:48Z <p>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 ?) ? </p> <p>This kind of event is related to Russo-Margulis formula (and therefore appears quite often, for example in the work of Friedgut and Kalai).</p> http://mathoverflow.net/questions/40230/what-are-some-good-examples-of-non-monotone-graph-properties/54837#54837 Answer by Jon Noel for What are some good examples of non-monotone graph properties? Jon Noel 2011-02-09T01:08:31Z 2011-02-09T01:08:31Z <p>Some variations of colouring problems are not monotone. For example, consider the following problem from <a href="http://dx.doi.org/10.1016/j.disc.2007.07.028" rel="nofollow">ScienceDirect</a>. </p> <p>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.</p> <p>For $n\geq3$ the complete bipartite graph $K_{n,n}$ is $k$-mixing whenever $k\geq3$, but the <a href="http://mathworld.wolfram.com/CocktailPartyGraph.html" rel="nofollow">cocktail party graph</a> with $n$ couples (obtained by deleting edges from $K_{n,n}$) is not $n$-mixing. See the examples in the <a href="http://dx.doi.org/10.1016/j.disc.2007.07.028" rel="nofollow">paper</a> above.</p>