Enfoque local-global de la teoría de grafos

Question

Esta pregunta se inspira en

(i) Teoremas como el "teorema del amigo universal": Si cada dos vértices de un grafo conexo $G$ comparten un único vecino común, entonces hay un vértice conectado a todos los demás en $G$ .

y (ii) Resultados como: Si el subgrafo abarcado por cada $k$ vértices en $G$ es $2$ -colorable, entonces $\chi(G)=O(n^{O(1/k)})$ .

Desgraciadamente no conozco muchos resultados similares en sabor a los anteriores, por eso la pregunta. ¿Cuáles son algunos teoremas/principios/métodos importantes en teoría de grafos que nos ayudan a determinar parámetros globales del grafo a partir de datos locales? (Estoy siendo intencionadamente vago sobre lo que quiero decir con "local", los ejemplos podrían variar desde datos sobre subgrafos abarcados por pocos vértices, a datos sobre subgrafos abarcados por vértices a poca distancia de un vértice base)

Answer 1

Hay una encuesta muy bonita Fenómenos locales-globales en grafos por N. Linial

Answer 2

Un buen resultado que da una respuesta negativa a su pregunta se debe a Erdos (1962, encontrado en Alon y Spencer entre otros lugares).

Dice que para todo k existe $\epsilon>0$ de modo que para todo n suficientemente grande existen grafos sobre n vértices con número cromático mayor que k, $\chi(G)>k$ pero para cada subgrafo S inducido como máximo por $\epsilon n$ vértices, $\chi(S)\leq 3$ .

En otras palabras, no se puede deducir mucha información sobre el número cromático de los grafos a partir del número cromático de sus subgrafos (en general), salvo resultados como el que has mencionado. Así que el comportamiento local puede ser muy diferente del comportamiento global, al menos en lo que respecta a los números cromáticos.

Answer 3

Véase Wikipedia para algunas propiedades globales determinadas por vecindades de vértices. En particular:

• Un grafo es localmente completo si es una unión disjunta de grafos completos
• Un grafo es localmente cíclico si es el grafo de un 2manifold triangulado sin triángulos de separación

Ejemplos en los que la estructura local implica cierta estructura global, pero no como caracterización exacta:

• Si un grafo es localmente k-cromático entonces es globalmente O(sqrt(kn))-cromático (quizás exista una versión de esto para vecindades locales de radio mayor similar a la de k=2 que citas en la pregunta)

Ejemplos en los que la estructura global implica una estructura local:

• Si un grafo es plano, entonces es localmente exteriormente plano.
• Si un grafo es k-cromático entonces es localmente (k-1)-cromático

Answer 4

Parece que el mayor resultado en la teoría de grafos en los últimos tiempos -- el Teorema Robertson-Seymour -- puede verse como un teorema local-global.

Answer 5

¿Califica la planaridad como "condición local"? Pensaría que sí, pero no veo cómo incluirla en el marco de "datos sobre subgrafos pequeños/locales".

De todos modos, si es así, tenemos por supuesto el teorema de los cuatro colores, e incluso mejor el teorema de los cinco colores, cuyas demostraciones se aprovechan esencialmente del hecho de que más o menos entendemos cómo movernos entre "local" y "global" en los espacios topológicos.

ETA: En términos más generales, por supuesto, existe todo el subcampo de la "teoría estructural de grafos" y sus métodos. No sé si el teorema menor de los grafos es "de lo local a lo global" (en realidad es más bien "de lo local a un tipo diferente de lo local"), pero probablemente sea el resultado estructural más importante.

La teoría estructural de grafos es algo que me gustaría conocer, pero parece tan terriblemente técnica y difícil que me da miedo estudiarla. Robertson, Seymour y Thomas trabajaron en la demostración de la conjetura del grafo perfecto fuerte, que utilizaba un argumento de descomposición y tenía un sabor enormemente estructural a pesar de no estar relacionado (hasta donde yo sé) con el trabajo más topológico que habían realizado anteriormente.

Tangencialmente, este reciente preprint de Dvorak, Kral y Thomas me llamó la atención exactamente por la razón de las "propiedades locales". Por desgracia, la demostración del teorema principal no parece estar disponible todavía...