Local-Global approach to graph theory - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T18:22:46Z http://mathoverflow.net/feeds/question/10241 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/10241/local-global-approach-to-graph-theory Local-Global approach to graph theory Gjergji Zaimi 2009-12-31T06:57:13Z 2012-04-04T23:42:47Z <p>This question is inspired from</p> <p>(i) Theorems like the "universal friend theorem": If every two vertices in a connected graph $G$ share a unique common neighbor, then there is a vertex connected to all the others in $G$.</p> <p>and (ii) Results like: If the subgraph spanned by every $k$ vertices in $G$ is $2$-colorable, then $\chi(G)=O(n^{O(1/k)})$.</p> <p>Unfortunately I don't know many results similar in flavor to the above, therefore the question. What are some important theorems/principles/methods in graph theory that help us determine global parameters of the graph from local data? (I am being intentionally vague about what I mean by "local", examples could vary from data on subgraphs spanned by few vertices, to data on subgraphs spanned by vertices at small distance from a base vertex)</p> http://mathoverflow.net/questions/10241/local-global-approach-to-graph-theory/10245#10245 Answer by Harrison Brown for Local-Global approach to graph theory Harrison Brown 2009-12-31T07:07:18Z 2009-12-31T07:35:13Z <p>Does planarity qualify as a "local condition?" I'd think it should, but I don't see how to put it into the "data on small/local subgraphs" framework.</p> <p>Anyway, if it does, you have of course the four-color theorem, and even better the five-color theorem, whose proofs essentially take advantage of the fact that we sort of understand how to move between "local" and "global" in topological spaces.</p> <p>ETA: More generally, of course, there's the whole subfield of "structural graph theory" and its methods. I don't know that the graph minor theorem is "local-to-global" -- it's really more "local-to-a-different-kind-of-local" -- but it's probably the most important structural result.</p> <p>Structural graph theory is something that I wish I knew about, but looks so horrifically technical and difficult that I'm sort of afraid to study it. There are clearly some deep patterns hidden there, though -- witness how Robertson, Seymour, and Thomas all worked on the proof of the Strong Perfect Graph Conjecture, which used a decomposition argument and had a hugely structural flavor despite being (as far as I can tell) mostly unrelated to the more topological work they'd previously done.</p> <p>Tangentially, <a href="http://www.aco.gatech.edu/~thomas/PAP/havel.pdf" rel="nofollow">this recent preprint</a> of Dvorak, Kral and Thomas caught my eye for exactly the "local properties" reason. Unfortunately the proof of the main theorem doesn't seem to be available yet...</p> http://mathoverflow.net/questions/10241/local-global-approach-to-graph-theory/10252#10252 Answer by Pete L. Clark for Local-Global approach to graph theory Pete L. Clark 2009-12-31T09:04:26Z 2009-12-31T09:04:26Z <p>It seems like the biggest result in graph theory in recent times -- the <a href="http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour%5Ftheorem" rel="nofollow">Robertson-Seymour Theorem</a> -- can be viewed as a local-global theorem.</p> http://mathoverflow.net/questions/10241/local-global-approach-to-graph-theory/10254#10254 Answer by Dima Fon-Der-Flaass for Local-Global approach to graph theory Dima Fon-Der-Flaass 2009-12-31T09:38:37Z 2009-12-31T09:38:37Z <p>There are many results on locally such-and-such graphs in algebraic combinatorics. One of the first, and nicest, of them is the classification of locally Petersen graphs:</p> <p>J. I. Hall, Locally Petersen graphs, J. Graph Theory 4 (1980) 173 - 187.</p> http://mathoverflow.net/questions/10241/local-global-approach-to-graph-theory/10260#10260 Answer by Thomas Bloom for Local-Global approach to graph theory Thomas Bloom 2009-12-31T11:30:35Z 2009-12-31T11:30:35Z <p>A nice result giving a negative answer towards your question is due to Erdos (1962, found in Alon and Spencer amongst other places).</p> <p>It says that for all k there exists $\epsilon>0$ so that for all sufficiently large n there exist graphs on n vertices with chromatic number greater than k, $\chi(G)>k$, but for every subgraph S induced by at most $\epsilon n$ vertices, $\chi(S)\leq 3$.</p> <p>In other words, not much information can be deduced about the chromatic number of graphs from the chromatic number of their subgraphs (in general) - except for results such as the one you mentioned. So local behaviour can be very different to global behaviour, at least as chromatic numbers go.</p> http://mathoverflow.net/questions/10241/local-global-approach-to-graph-theory/10325#10325 Answer by Suresh Venkat for Local-Global approach to graph theory Suresh Venkat 2009-12-31T21:49:55Z 2009-12-31T21:49:55Z <p>Along the lines of what Thomas Bloom points out, it's unlikely that any NP-Complete property of a graph will have a local-global structure, because such a structure would imply an algorithm that might run efficiently (parametrized by the "size" of the local structure). Chromatic number is one such example. </p> http://mathoverflow.net/questions/10241/local-global-approach-to-graph-theory/10326#10326 Answer by David Eppstein for Local-Global approach to graph theory David Eppstein 2009-12-31T22:13:11Z 2009-12-31T22:13:11Z <p>See <a href="http://en.wikipedia.org/wiki/Neighbourhood%5F%28graph%5Ftheory%29" rel="nofollow">Wikipedia</a> for some global properties determined by neighborhoods of vertices. In particular:</p> <ul> <li>A graph is locally complete iff it is a disjoint union of complete graphs</li> <li>A graph is locally cyclic iff it is the graph of a triangulated 2-manifold with no separating triangles</li> </ul> <p>Examples where local structure implies some global structure but not as an exact characterization:</p> <ul> <li>If a graph is locally k-chromatic then it is globally O(sqrt(kn))-chromatic (maybe there is a version of this for local neighborhoods of larger radius similar to the one for k=2 that you cite in the question)</li> </ul> <p>Examples where global structure implies local structure:</p> <ul> <li>If a graph is planar then it is locally outerplanar</li> <li>If a graph is k-chromatic then it is locally (k-1)-chromatic</li> </ul> http://mathoverflow.net/questions/10241/local-global-approach-to-graph-theory/10328#10328 Answer by David Eppstein for Local-Global approach to graph theory David Eppstein 2009-12-31T22:20:12Z 2009-12-31T22:20:12Z <p>Here's another one, if one looks at minor-closed graph families instead of individual graphs: a minor-closed graph family has bounded local treewidth (that is, there is a function f such that the treewidth of radius-k neighborhoods of any vertex in any graph in the family is at most f(k)) if and only if the family excludes some apex graph. In this case (unlike Pete Clark's answer) I'm viewing the excluded minor as a global property since it depends on the whole graph and not just on bounded-radius neighborhoods. See my paper <a href="http://arxiv.org/abs/math.CO/9907126" rel="nofollow">"Diameter and treewidth in minor-closed graph families"</a> and <a href="http://dx.doi.org/10.1007/s00453-004-1106-1" rel="nofollow">a followup by Demaine and Hajiaghayi</a>.</p> http://mathoverflow.net/questions/10241/local-global-approach-to-graph-theory/10332#10332 Answer by Harrison Brown for Local-Global approach to graph theory Harrison Brown 2009-12-31T23:21:26Z 2009-12-31T23:21:26Z <p>I think that other "negative results" come from the philosophy of extremal graph theory. For instance, one way of thinking of Szemeredi's regularity lemma is as a statement that <em>all</em> big enough, dense graphs can be endowed with essentially the same local structure (as long as we're only considering density.)</p> <p>Ramsey theory can be thought of as examining the regime in which the existence of a member from a list of small subgraphs gives you <em>no</em> information about the graph.</p> <p>And of course, random graphs all look the same at small scales, but especially if you're asking about a property that can't be characterized in first-order logic, they can be quite unpredictable globally. That said, there is the concept of <a href="http://authors.library.caltech.edu/10730/1/CHUpnas88.pdf" rel="nofollow">quasirandom graphs</a>, which sort of encapsulates the ways we can move from local to global in random graph theory.</p> <p>Along those lines, there's been some fantastic work on graph homomorphisms -- Lovasz is the name that stands out the most, although there are a number of people working on this -- which (loosely speaking) creates a metric space where graphs that are hard to separate by local data are close to each other... </p> http://mathoverflow.net/questions/10241/local-global-approach-to-graph-theory/10333#10333 Answer by Rune for Local-Global approach to graph theory Rune 2010-01-01T00:11:52Z 2010-01-01T00:11:52Z <p>It seems like what you want is the field of Extremal Graph Theory. Most results in the field are about how global properties imply local structures or the reverse. An example of the first type is Turan's theorem, which for instance says that any graph with more than $n^2/4$ edges must contain a clique of size 3. On the other hand, we have Dirac's result, that if the minimum degree of a graph is n/2 then it must contain a Hamiltonian cycle.</p> <p>A quick reference is Diestel's book which is available online for free. A better reference is Bollobas' book on the subject.</p> http://mathoverflow.net/questions/10241/local-global-approach-to-graph-theory/10429#10429 Answer by David Eppstein for Local-Global approach to graph theory David Eppstein 2010-01-02T00:37:40Z 2010-01-02T00:37:40Z <p>Here's yet another example:</p> <p>If a graph is s-connected (that is, no set of s-1 vertices can be removed in such a way as to disconnect the remaining graph) and has no independent set of s+1 vertices, then it has a Hamiltonian cycle: see Chvátal and ErdÅ‘s, <a href="http://www.renyi.hu/~p%5Ferdos/1972-02.pdf" rel="nofollow">A note on Hamiltonian circuits</a>, Discrete Math. 1972.</p> <p>The NP-completeness of Hamiltonicity means that any kind of exact characterization in terms of finite subsets of vertices is unlikely, though.</p> http://mathoverflow.net/questions/10241/local-global-approach-to-graph-theory/65720#65720 Answer by APG for Local-Global approach to graph theory APG 2011-05-22T17:29:45Z 2011-05-22T23:32:45Z <p>There is a very nice survey <a href="http://www.cs.huji.ac.il/~nati/PAPERS/local_global.pdf" rel="nofollow">Local-global phenomena in graphs</a> by N. Linial</p> http://mathoverflow.net/questions/10241/local-global-approach-to-graph-theory/93175#93175 Answer by Felix Goldberg for Local-Global approach to graph theory Felix Goldberg 2012-04-04T23:42:47Z 2012-04-04T23:42:47Z <p>There is a whole subject of Ore-type conditions for hamiltonicity, of which the Chvatal-Erdos theorem, mentioned before, is one example.</p> <p>See: <a href="http://www.cs.ucdavis.edu/~gusfield/cs225w12/Chvatal-Erdos.pdf" rel="nofollow">http://www.cs.ucdavis.edu/~gusfield/cs225w12/Chvatal-Erdos.pdf</a></p>