Local-global approach to graph theory

Question

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 1

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

Answer 2

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 3

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 4

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 5

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 6

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 7

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 8

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 9

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 10

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 11

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 12

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

Answer 13

Here's an example of a graph invariant which relates local estimates of some parameter with the global (or true) value of the parameter. The imperfection ratio of a graph $G$, denoted $imp(G)$, is defined to be $\sup_{x \ne 0} \frac{\chi_f(G,x)}{\omega(G,x)}$, where the supremum is taken over all nonzero rational vectors $x$, and $\chi_f(G,x)$ and $\omega(G,x)$ denote the fractional chromatic number and clique number, respectively, of the vertex-weighted graph $(G,x)$.

Consider a wireless communication network, where each node $v \in V(G)$ has a demand to transmit data for a fraction $x_v$ of each unit of time. Nodes which are adjacent in $G$ cannot transmit simultaneously due to wireless interference (this is how the edge set of $G$ is defined). The question is: can a demand vector $x = (x_v: v \in V(G))$ be satisfied? The demand vector $x$ is feasible if and only if $\chi_f(G,x) \le 1$. Computing $\chi_f(G,x)$ is NP-hard in general.

Am efficient, distributed mechanism for determining feasibility is to check whether the sum of the demands of each clique in $G$ is at most $1$. For a particular demand $x$, an optimal centralized algorithm would compute the numerator $\chi_f(G,x)$ of the definition of imperfection ratio. The distributed algorithm computes the denominator $\omega(G,x)$. Their ratio is the factor by which the distributed algorithm is away from optimal. The maximum possible value of this ratio, over all demand patterns, is the worst-case performance of this distributed algorithm, and is equal to the imperfection ratio of $G$.

The imperfection ratio was investigated by Gerke and McDiarmid, and applications of imperfection ratio to wireless networks has been studied here, here, and here.