20 votos

Enfoque local-Global de teoría de grafos

Esta pregunta está inspirado en el

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

y (ii) los Resultados como: Si el subgrafo generado por cada $k$ vértices en $G$ $2$- engañosa, a continuación,$\chi(G)=O(n^{O(1/k)})$.

Lamentablemente, no conozco muchos resultados similares en sabor a la anterior, por lo tanto la pregunta. ¿Cuáles son algunos de los más importantes teoremas, principios y métodos de la teoría de grafos que nos ayudan a determinar los parámetros globales de la gráfica de datos locales? (Estoy siendo intencionalmente vaga acerca de lo que quiero decir por "locales", los ejemplos podrían variar a partir de datos de subdiagramas se extendió por un par de vértices, a los datos de los subdiagramas se extendieron por los vértices a pequeña distancia de una base de vértice)

8voto

Elmar Weber Puntos 242

Hay una encuesta muy bonito Local-global fenómenos en gráficos por N. Linial

5voto

K. Brian Kelley Puntos 7714

Un buen resultado dando una respuesta negativa hacia su pregunta es debido a Erdos (1962, se encuentra en Alon y Spencer, entre otros lugares).

Se dice que para todo k existe $\epsilon>0$, de modo que para todos lo suficientemente grande n existen gráficas de n vértices con cromática número mayor que k, $\chi(G)>k$, pero para cada subgrafo S inducido a la mayoría de los $\epsilon n$ vértices, $\chi(S)\leq 3$.

En otras palabras, no es mucha la información que se puede deducir acerca de la cromática número de gráficos a partir de la cromática número de sus subdiagramas (en general) - excepto por los resultados como el que usted ha mencionado. De manera local, el comportamiento puede ser muy diferente al comportamiento global de, al menos como cromática números de ir.

4voto

skfd Puntos 463

¿Planaridad calificar como una "condición local?" Yo pensaría que debería, pero no veo cómo ponerlo en los "datos de los pequeños/local subdiagramas" marco.

De todos modos, si lo hace, usted tiene de curso de los cuatro-color teorema, y mejor aún la de cinco colores teorema, cuya pruebas esencialmente tomar ventaja del hecho de que tenemos suerte de entender cómo se mueven entre "local" y "global" en espacios topológicos.

ETA: Más generalmente, por supuesto, no todo el subcampo de "estructural de la teoría de grafos" y sus métodos. No sé que la gráfica de menor importancia es el teorema "de lo local a lo global", es realmente más "local-a-un-diferentes-tipo-de-locales" -- pero es probablemente el más importante estructurales resultado.

Estructural de la teoría de grafos es algo que me gustaría que me conocía, pero se ve tan espantoso técnico y difícil que yo soy una especie de miedo de estudio. Es claro que hay algunos en el fondo de patrones ocultos, aunque -- testigo de cómo Robertson, Seymour, y Tomás, trabajó en la prueba de la Fuerte Perfecto Gráfico Conjetura, que utiliza una descomposición argumento y había un enorme estructurales sabor a pesar de ser (como lo que puedo decir) en su mayoría ajenos a la más topológico trabajo que había hecho.

Tangencialmente, esta reciente preprint de Dvorak, Kral y Thomas me llamó la atención precisamente por el "local" propiedades de la razón. Por desgracia, la prueba de las principales teorema no parece estar disponible, sin embargo...

4voto

kevtrout Puntos 2774

Parece que el mayor resultado en teoría de gráfico en los últimos tiempos, el Teorema de Robertson-Seymour --puede considerarse un teorema local-global.

4voto

Alan Puntos 221

Hay muchos resultados en gráficos localmente y tal de combinatoria algebraica. Una de las primeras y más bellas, de ellos es la clasificación de local Petersen gráficos:

J. I. Hall, local Petersen gráficos, 4 de teoría de gráfico J. (1980) 173-187.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X