Local-Global approach to graph theory - MathOverflow

Local-Global approach to graph theory

2009-12-31T06:57:13Z

This question is inspired from

(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$.

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

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)

Answer by Harrison Brown for Local-Global approach to graph theory

2009-12-31T07:07:18Z

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.

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.

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.

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.

Tangentially, this recent preprint 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...

Answer by Pete L. Clark for Local-Global approach to graph theory

2009-12-31T09:04:26Z

It seems like the biggest result in graph theory in recent times -- the Robertson-Seymour Theorem -- can be viewed as a local-global theorem.

Answer by Dima Fon-Der-Flaass for Local-Global approach to graph theory

2009-12-31T09:38:37Z

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:

J. I. Hall, Locally Petersen graphs, J. Graph Theory 4 (1980) 173 - 187.

Answer by Thomas Bloom for Local-Global approach to graph theory

2009-12-31T11:30:35Z

A nice result giving a negative answer towards your question is due to Erdos (1962, found in Alon and Spencer amongst other places).

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

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.

Answer by Suresh Venkat for Local-Global approach to graph theory

2009-12-31T21:49:55Z

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.

Answer by David Eppstein for Local-Global approach to graph theory

2009-12-31T22:13:11Z

See Wikipedia for some global properties determined by neighborhoods of vertices. In particular:

A graph is locally complete iff it is a disjoint union of complete graphs
A graph is locally cyclic iff it is the graph of a triangulated 2-manifold with no separating triangles

Examples where local structure implies some global structure but not as an exact characterization:

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)

Examples where global structure implies local structure:

If a graph is planar then it is locally outerplanar
If a graph is k-chromatic then it is locally (k-1)-chromatic

Answer by David Eppstein for Local-Global approach to graph theory

2009-12-31T22:20:12Z

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 "Diameter and treewidth in minor-closed graph families" and a followup by Demaine and Hajiaghayi.

Answer by Harrison Brown for Local-Global approach to graph theory

2009-12-31T23:21:26Z

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 all big enough, dense graphs can be endowed with essentially the same local structure (as long as we're only considering density.)

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 no information about the graph.

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 quasirandom graphs, which sort of encapsulates the ways we can move from local to global in random graph theory.

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

Answer by Rune for Local-Global approach to graph theory

2010-01-01T00:11:52Z

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.

A quick reference is Diestel's book which is available online for free. A better reference is Bollobas' book on the subject.

Answer by David Eppstein for Local-Global approach to graph theory

2010-01-02T00:37:40Z

Here's yet another example:

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 note on Hamiltonian circuits, Discrete Math. 1972.

The NP-completeness of Hamiltonicity means that any kind of exact characterization in terms of finite subsets of vertices is unlikely, though.

Answer by APG for Local-Global approach to graph theory

2011-05-22T17:29:45Z

There is a very nice survey Local-global phenomena in graphs by N. Linial

Answer by Felix Goldberg for Local-Global approach to graph theory

2012-04-04T23:42:47Z

There is a whole subject of Ore-type conditions for hamiltonicity, of which the Chvatal-Erdos theorem, mentioned before, is one example.

See: http://www.cs.ucdavis.edu/~gusfield/cs225w12/Chvatal-Erdos.pdf