What’s a “locally determined graph property?”

This has nothing to do with the rest of the post, but I’ll put it here so you read it before you get bored. I’d like to thank my readers (all seven of you) for supporting this blog in the first six months or so of its existence, and hope that you’ll stick around (and be joined by hundreds of new readers…) to hear my sporadic ramblings and wild ravings in the next year. Here’s to a happy and successful 2010!

Over at MathOverflow, Gjergji Zaimi asks (in a criminally under-voted-for question): How can we obtain global information from local data in graph theory?  This is something that perhaps everyone working in or around graph theory has asked themselves, in some form, at some point — I know I have. So it’s not surprising that Gjergji’s question has received many different answers with many different interesting things to say.

I originally wanted to write a post trying to “answer” Gjergji’s question as best I could, but quickly realized the futility of that goal — it’s such a broad and deep question that I doubt if anyone could answer it concisely, and I know I couldn’t! So instead I’ll just talk about an \epsilon of the question — what does it even mean, “local data?”

Gjergji left the meaning of “local graph property” vague in his question — and to his great credit, he stated (in the question!) that he did so knowingly and intentionally. To see why, let’s go over some theorems (and some conjectures) that can reasonably be said to “go from local to global” (for conciseness, we’ll set |V(G)| = n and |E(G)| = m in what follows):

  1. If every two vertices in a connected graph G have a unique common neighbor, then there’s a vertex adjacent to all the others.
  2. (Ore) If every pair of non-adjacent vertices in G has total degree at least n, then G is Hamiltonian.
  3. If the subgraph spanned by every k vertices is bipartite, then G has chromatic number at most O(n^{c/k}) for some absolute constant c.
  4. (Grotzsch) If G is planar and has no triangles, then G is 3-colorable.
  5. (Dvorak-Kral-Thomas) If G is planar and every path between distinct triangles is longer than some absolute constant, then G is 3-colorable.
  6. If no two vertices of G, both of degree greater than 2, are adjacent, then G is 3-colorable.
  7. If G has roughly n^2/4 edges and about the same number of subgraphs isomorphic to C_4 as the Erdos-Renyi graph G(n, 1/2), then all labeled graphs on k vertices occur about equally often as induced subgraphs of G, for k << n.
  8. (Turan) If G is triangle-free, then m \leq n^2/4.
  9. (Robertson-Seymour) The graph minors theorem.
  10. If G contains no K_k subgraph and n >> k, then the complement of G must contain a $K_k$ subgraph.
  11. (Alon-Krivelevich) If a random induced subgraph of G of order O(k~ln~k / \epsilon^2) is k-colorable, then with high probability you can delete \epsilon n^2 edges of G and obtain a k-colorable graph. (In particular, if every such subgraph is k-colorable, then the conclusion holds deterministically.)
  12. (Conjecture, Erdos-Gyarfas) If G has minimum degree 3, then G contains a cycle with length a power of two.
  13. (Conjecture, Hadwiger) If G contains no K_k minor, then G is (k-1)-colorable.
  14. (Reconstruction conjecture) As long as n > 2, G is determined by the multiset of induced subgraphs on (n-1) vertices.

Clearly these statements are all over the place — some, like 6, are almost trivial to prove, while others take hundreds of pages or are still open! Furthermore, they run the gamut from extremal graph theory to topological problems to pure combinatorics.

And implicitly they use widely varying notions of “locality.” Let’s try to deconstruct what they mean, in roughly increasing order of generality. But first, let’s clear up what we mean by “local-to-global,” at least a little.

The starting idea — although we may well move beyond this later — is to consider two graph properties P, P'. A local-to-global theorem, then, is a theorem which says that if G satisfies property P “locally,” then it satisfies P’ globally. (We may also require that G is sufficiently large, or dense.) Often P’ will be weaker than P, although sometimes they’re logically incomparable. The question is what we mean by “locally!” So let’s consider some possibilities:

  • The “local data” are the induced subgraphs on a constant (or << n) number of vertices. This is arguably the strictest possible notion of “locality” we’ll encounter, and is almost certainly the strictest one about which we can say much of interest. Amazingly, though, there are a lot of interesting things to consider! Ramsey theory falls squarely into this category, as does a good deal of extremal graph theory. Statements 3, 8, 10, and the deterministic version of 11 are of this form. 7 and the probabilistic version of 11 are closely related.
  • The “local data” are (unions of) the neighborhood of each vertex, the set of vertices at most a fixed distance away from each vertex, or the induced subgraphs on these. This isn’t actually comparable to the first notion of “locality,” but in practice it tends to be less strict. What’s interesting is that there seems to be a “phase transition” at work here: Theorems that just use the neighborhood of sets of vertices tend to be straightforwardly combinatorial; examples include 1, 2, 6, and 12. But theorems that consider higher distances often have a geometric flavor; look at (for instance) 5, or at the spectral theory of expanders.
  • The “local data” are “low-complexity (induced) subgraphs.” Occasionally one wants to consider a family of graphs that isn’t closed under taking subgraphs, but are still in some sense “small.” One example, for instance, is the set of subdivisions of K_5; another is the set of odd cycles. It might be useful to think of this as an “information-theoretic relaxation” of small induced subgraphs; we can view the family of constant-sized subgraphs as the set of subgraphs describable with O(1) bits; this relaxes it to some family of subgraphs with smal information complexity. Probably the best example is graph minor theory, although the strong perfect graph theorem falls into this category as well.

Now let’s step back from the original definition of “local-to-global” and generalize. Note that if we can check a global property by checking it on each constant-sized subgraph, we can check it using a constant number of pointers and constant extra space. This suggests that we might want to investigate “complexity-theoretic” notions of localness.

  • A property is “locally determined” if it’s decidable by a Turing machine with a constant number of pointers to the input and constant additional space. I believe this is equivalent to the property being regular, although I’m a little unclear.
  • A property is “locally determined” if it’s in L = SL. Think of this as a generalization of “counting on local data.” This is a remarkably rich complexity class, containing things like planarity and connectedness that we might not think of as “local.”
  • A property is “locally determined” if it’s in RL. Similar to the above.
  • A property is “locally determined” if it’s in P (=BPP? =NP?). The rationale for this is that no such polynomial time algorithm can examine more than a negligible fraction of “large subgraphs.” That said, I don’t know of any graph property that I would consider “local” which is known to be in BPP but believed to be outside of L. Anyone have an example?
  • ??? What are some other notions of “local” in graph theory? How does this affect how we move from local to global?

Tags: , , , , , ,

2 Responses to “What’s a “locally determined graph property?””

  1. Gjergji Says:

    I really like your post, and thank you for taking the time and writing your opinions. Btw, what do you think I should do about the MO question? Is there any point in starting a bounty (or is the thread pretty much dead? I’m new to MO so am not familiar with the trends there). If not then I will accept one of your answers, even though they are all equally good and with different perspectives. 🙂

  2. PADIR Says:


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: