La teoría de grafos extremos es una rama de las matemáticas que estudia cómo las propiedades globales de un grafo influyen en la subestructura local. [1] Abarca una gran cantidad de resultados que describen cómo ciertas propiedades del gráfico - número de vértices (tamaño), número de aristas , densidad de aristas , número cromático y circunferencia , por ejemplo - garantizan la existencia de ciertas subestructuras locales.
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/1/1b/Turan_13-4.svg/220px-Turan_13-4.svg.png)
Uno de los principales objetos de estudio en esta área de la teoría de grafos son los grafos extremos , que son máximos o mínimos con respecto a algún parámetro global, y que contienen (o no contienen) una subestructura local, como una camarilla, o una coloración del borde.
Ejemplos de
La teoría de grafos extremos puede estar motivada por preguntas como las siguientes:
Pregunta 1. ¿Cuál es el número máximo posible de aristas en un gráfico en vértices de manera que no contenga un ciclo?
Si un gráfico en vértices contiene al menos bordes, entonces también debe contener un ciclo. Además, cualquier árbol con vértices contiene bordes y no contiene ciclos; Los árboles son los únicos gráficos conbordes y sin ciclos. Por tanto, la respuesta a esta pregunta es, y los árboles son los gráficos extremos. [2]
Pregunta 2. Si un gráfico en vértices no contiene ningún subgrafo triangular, ¿cuál es el número máximo de aristas que puede tener?
El teorema de Mantel responde a esta pregunta: el número máximo de aristas es. El gráfico extremo correspondiente es un gráfico bipartito completo en vértices, es decir, las dos partes difieren en tamaño como máximo en 1.
A continuación, se presenta una generalización de la pregunta 2:
Pregunta 3. Vamosser un número entero positivo. ¿Cuántas aristas debe haber en un gráfico? en vértices para garantizar que, sin importar cómo estén dispuestos los bordes, la camarilla se puede encontrar como un subgrafo?
La respuesta a esta pregunta es y es respondido por el Teorema de Turán . Por lo tanto, si un gráfico en vértices es -gratis, puede tener como máximo
muchos bordes; la gráfica extrema correspondiente con esa cantidad de aristas es la gráfica de Turán , que se muestra en la figura de arriba. Es la unión completa deconjuntos independientes (con tamaños lo más iguales posible; tal partición se llama equitativa ).
La siguiente pregunta es una generalización de la Pregunta 3, donde el gráfico completo es reemplazado por cualquier gráfico :
Pregunta 4. Vamos ser un número entero positivo, y cualquier gráfico en vértices. ¿Cuántas aristas debe haber en un gráfico? en vértices para garantizar que, independientemente de cómo estén dispuestos los bordes, es un subgrafo de ?
Esta pregunta es respondida principalmente por el teorema de Erdős-Stone . La principal advertencia es que para bipartito, el teorema no determina satisfactoriamente el comportamiento asintótico del recuento de aristas extremas. Para muchas (clases de) grafos bipartitos particulares, determinar el comportamiento asintótico sigue siendo un problema abierto.
Varios resultados fundamentales en la teoría de grafos extremos responden preguntas que siguen esta formulación general:
Pregunta 5. Dada una propiedad gráfica , un parámetro describir un gráfico y un conjunto de gráficos , deseamos encontrar el valor mínimo posible tal que cada grafo con tiene propiedad . Además, es posible que queramos describir gráficos que son extremas en el sentido de tener cerca de pero que no satisfacen la propiedad .
En la Pregunta 1, por ejemplo, es el conjunto de -Gráficos de vértice, es la propiedad de contener un ciclo, es el número de aristas y el corte es . Los ejemplos extremos son los árboles.
Historia
El Teorema de Mantel (1907) y el Teorema de Turán (1941) fueron algunos de los primeros hitos en el estudio de la teoría de grafos extremos. [3] En particular, el teorema de Turán se convertiría más tarde en una motivación para encontrar resultados como el Teorema de Erdős-Stone-Simonovits (1946). [1] Este resultado es sorprendente porque conecta el número cromático con el número máximo de aristas en una-Gráfico gratuito. Una prueba alternativa de Erdős-Stone-Simonovits se dio en 1975, y utilizó el lema de regularidad de Szemerédi , una técnica esencial en la resolución de problemas extremos de teoría de grafos. [3]
Resultados de densidad y desigualdades
Un parámetro global que tiene un papel importante en la teoría de grafos extremos es la densidad de subgrafos; para un gráfico y una gráfica , su densidad de subgrafo se define como
.
En particular, la densidad del borde es la densidad del subgrafo para :
Los teoremas mencionados anteriormente se pueden reformular en términos de densidad de bordes. Por ejemplo, el teorema de Mantel implica que la densidad de aristas de un subgrafo sin triángulos es como máximo. El teorema de Turán implica que la densidad de aristas de-El gráfico libre es como máximo .
Además, el teorema de Erdős-Stone-Simonovits establece que
dónde es el número máximo de aristas que un -Gráfico gratuito en vértices pueden tener, y es el número cromático de. Una interpretación de este resultado es que la densidad de los bordes de un-el gráfico libre es asintóticamente .
Otro resultado de Erdős, Rényi y Sós (1966) muestra que el gráfico de vértices que no contienen como subgrafo tiene como máximo el siguiente número de aristas.
Condiciones mínimas de titulación
Los teoremas establecidos anteriormente dan las condiciones para que un objeto pequeño aparezca dentro de un gráfico (quizás) muy grande. Otra dirección en la teoría de grafos extremos es buscar condiciones que garanticen la existencia de una estructura que cubra todos los vértices. Tenga en cuenta que incluso es posible para un gráfico con vértices y aristas para tener un vértice aislado, aunque casi todas las aristas posibles están presentes en el gráfico. Las condiciones de recuento de bordes no dan ninguna indicación de cómo se distribuyen los bordes en el gráfico, lo que lleva a resultados que solo encuentran estructuras limitadas en gráficos muy grandes. Esto proporciona motivación para considerar el parámetro de grado mínimo, que se define como
Un grado mínimo grande elimina la posibilidad de tener algunos vértices 'patológicos'; si el grado mínimo de un gráfico G es 1, por ejemplo, entonces no puede haber vértices aislados (aunque G puede tener muy pocas aristas).
Un resultado de la teoría de grafos extremos relacionado con el parámetro de grado mínimo es el teorema de Dirac , que establece que cada grafo con vértices y grado mínimo al menos contiene un ciclo de Hamilton .
Otro teorema [3] dice que si el grado mínimo de una gráfica es , y la circunferencia es , entonces el número de vértices en el gráfico es al menos
.
Algunas preguntas abiertas
A pesar de que se han realizado muchas observaciones importantes en el campo de la teoría de grafos extremos, todavía quedan varias preguntas sin respuesta. Por ejemplo, el problema de Zarankiewicz pregunta cuál es el número máximo posible de aristas en un gráfico bipartito envértices que no tienen subgrafos bipartitos completos de tamaño.
Otra conjetura importante en la teoría de grafos extremos fue formulada por Sidorenko en 1993 . Se conjetura que sies un gráfico bipartito, luego su densidad de grafón (una noción generalizada de densidad de gráfico) Por lo menos .
Ver también
- Teoría de Ramsey
- Desigualdades de densidad de gráficos
- Problema de subgrafo prohibido
- Elección aleatoria dependiente
Notas
- ^ a b Diestel 2010
- ^ Bollobás 2004 , p. 9
- ↑ a b c Bollobás 1998 , p. 104
Referencias
- Bollobás, Béla (2004), Extremal Graph Theory , Nueva York: Dover Publications , ISBN 978-0-486-43596-1.
- Bollobás, Béla (1998), Modern Graph Theory , Berlín, Nueva York: Springer-Verlag , págs. 103-144, ISBN 978-0-387-98491-9.
- Diestel, Reinhard (2010), Graph Theory (4ª ed.), Berlín, Nueva York: Springer-Verlag, págs. 169–198, ISBN 978-3-642-14278-9, archivado desde el original el 28 de mayo de 2017 , consultado el 18 de noviembre de 2013.
- M. Simonovits, Diapositivas de las conferencias de la escuela de verano de Chorin, 2006. [1]