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

Creo que otros "resultados negativos" proceden de la filosofía de la teoría de grafos extremos. Por ejemplo, una forma de pensar en el lema de regularidad de Szemeredi es como una afirmación de que todos suficientemente grandes, los grafos densos pueden estar dotados esencialmente de la misma estructura local (siempre que sólo consideremos la densidad.)

Se puede considerar que la teoría de Ramsey examina el régimen en el que la existencia de un miembro de una lista de pequeños subgrafos le da no información sobre el gráfico.

Y, por supuesto, los grafos aleatorios tienen todos el mismo aspecto a escalas pequeñas, pero especialmente si preguntas por una propiedad que no se puede caracterizar en lógica de primer orden, pueden ser bastante impredecibles globalmente. Dicho esto, existe el concepto de grafos cuasirandomáticos que resume las formas en que podemos pasar de lo local a lo global en la teoría de grafos aleatorios.

En este sentido, se ha realizado un trabajo fantástico sobre los homomorfismos de grafos (Lovasz es el nombre que más destaca, aunque hay varias personas trabajando en ello), que (en términos generales) crea un espacio métrico en el que los grafos que son difíciles de separar mediante datos locales están cerca unos de otros...

Answer 2

Existe todo un tema de condiciones de tipo Ore para la hamiltonicidad, del que el teorema de Chvatal-Erdos, mencionado antes, es un ejemplo.

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

Answer 3

He aquí un ejemplo de invariante de un grafo que relaciona las estimaciones locales de algún parámetro con el valor global (o verdadero) del parámetro. El coeficiente de imperfección de un gráfico $G$ denotado $imp(G)$ se define como $\sup_{x \ne 0} \frac{\chi_f(G,x)}{\omega(G,x)}$ donde el supremum se toma sobre todos los vectores racionales no nulos $x$ y $\chi_f(G,x)$ y $\omega(G,x)$ denotan el número cromático fraccionario y el número de camarilla, respectivamente, del grafo ponderado por vértices $(G,x)$ .

Consideremos una red de comunicación inalámbrica en la que cada nodo $v \in V(G)$ tiene una demanda para transmitir datos durante una fracción $x_v$ de cada unidad de tiempo. Los nodos que son adyacentes en $G$ no pueden transmitir simultáneamente debido a interferencias inalámbricas (así es como el conjunto de bordes de $G$ ). La pregunta es: ¿puede un vector de demanda $x = (x_v: v \in V(G))$ ¿quedará satisfecho? El vector de demanda $x$ es factible si y sólo si $\chi_f(G,x) \le 1$ . Informática $\chi_f(G,x)$ es NP-difícil en general.

Un mecanismo eficiente y distribuido para determinar la viabilidad consiste en comprobar si la suma de las demandas de cada camarilla en $G$ es como máximo $1$ . Para una demanda concreta $x$ un algoritmo centralizado óptimo calcularía el numerador $\chi_f(G,x)$ de la definición de ratio de imperfección. El algoritmo distribuido calcula el denominador $\omega(G,x)$ . Su ratio es el factor por el que el algoritmo distribuido se aleja del óptimo. El valor máximo posible de este coeficiente, sobre todos los patrones de demanda, es el peor caso de rendimiento de este algoritmo distribuido, y es igual al coeficiente de imperfección de $G$ .

El índice de imperfección se investigó mediante Gerke y McDiarmid y se han estudiado las aplicaciones de la relación de imperfección a las redes inalámbricas aquí , aquí y aquí .