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

En la línea de lo que señala Thomas Bloom, es poco probable que cualquier propiedad NP-Completa de un grafo tenga una estructura local-global, porque tal estructura implicaría un algoritmo que podría ejecutarse eficientemente (parametrizado por el "tamaño" de la estructura local). El número cromático es un ejemplo de ello.

Answer 2

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 3

Aquí hay otra, si nos fijamos en las familias de grafos de menor cierre en lugar de en los grafos individuales: una familia de grafos de menor cierre tiene un treewidth local acotado (es decir, existe una función f tal que el treewidth de los vecindarios de radio-k de cualquier vértice en cualquier grafo de la familia es como máximo f(k)) si y sólo si la familia excluye algún grafo vértice. En este caso (a diferencia de la respuesta de Pete Clark) estoy viendo el menor excluido como una propiedad global, ya que depende de todo el gráfico y no sólo de los vecindarios de radio limitado. Véase mi artículo "Diámetro y treewidth en familias de grafos minor-closed" y un seguimiento de Demaine y Hajiaghayi .

Answer 4

He aquí otro ejemplo:

Si un grafo está s-conectado (es decir, no se puede eliminar ningún conjunto de s-1 vértices de forma que se desconecte el grafo restante) y no tiene ningún conjunto independiente de s+1 vértices, entonces tiene un ciclo hamiltoniano: véase Chvátal y Erdős, Nota sobre los circuitos hamiltonianos Discrete Math. 1972.

La complejidad NP de la Hamiltonicidad significa que cualquier tipo de caracterización exacta en términos de subconjuntos finitos de vértices es poco probable.

Answer 5

Parece que lo que buscas es el campo de la Teoría de Grafos Extremos. La mayoría de los resultados en este campo tratan de cómo las propiedades globales implican estructuras locales o lo contrario. Un ejemplo del primer tipo es el teorema de Turan, que dice, por ejemplo, que cualquier grafo con más de $n^2/4$ Las aristas deben contener una camarilla de tamaño 3. Por otra parte, tenemos el resultado de Dirac, que si el grado mínimo de un grafo es n/2 entonces debe contener un ciclo hamiltoniano.

Una referencia rápida es el libro de Diestel, disponible gratuitamente en Internet. Una referencia mejor es el libro de Bollobas sobre el tema.