El teorema de Erdős-Gallai es un resultado de la teoría de grafos , una rama de las matemáticas combinatorias . Proporciona uno de los dos enfoques conocidos para resolver el problema de realización de gráficos , es decir, proporciona una condición necesaria y suficiente para que una secuencia finita de números naturales sea la secuencia de grados de un gráfico simple . Una secuencia que obedece estas condiciones se denomina "gráfica". El teorema fue publicado en 1960 por Paul Erdős y Tibor Gallai , de quienes recibe su nombre.
Declaración
Una secuencia de números enteros no negativos se puede representar como la secuencia de grados de un grafo simple finito en n vértices si y solo si es par y
se mantiene para cada k en .
Pruebas
No es difícil demostrar que las condiciones del teorema de Erdős-Gallai son necesarias para que una secuencia de números sea gráfica. El requisito de que la suma de los grados sea par es el lema del apretón de manos , ya utilizado por Euler en su artículo de 1736 sobre los puentes de Königsberg . La desigualdad entre la suma de losgrados más grandes y la suma de los grados restantes se puede establecer contando dos veces : el lado izquierdo da el número de adyacencias borde-vértice entre los vértices de mayor grado, cada una de estas adyacencias debe estar en un borde con uno o dos extremos de alto grado, el El término de la derecha proporciona el número máximo posible de adyacencias borde-vértice en las que ambos extremos tienen un grado alto, y el término restante de los límites superiores de la derecha el número de bordes que tienen exactamente un extremo de grado alto. Por lo tanto, la parte más difícil de la demostración es mostrar que, para cualquier secuencia de números que obedezca estas condiciones, existe una gráfica para la cual es la secuencia de grados.
La prueba original de Erdős & Gallai (1960) fue larga y complicada. Choudum (1986) cita una prueba más breve de Claude Berge , basada en ideas de flujo de red . En cambio, Choudum proporciona una prueba por inducción matemática sobre la suma de los grados: deja ser el primer índice de un número en la secuencia para la cual (o el penúltimo número si todos son iguales), utiliza un análisis de caso para mostrar que la secuencia formada al restar uno de y del último número en la secuencia (y quitar el último número si esta resta hace que se convierta en cero) es nuevamente gráfico y forma un gráfico que representa la secuencia original agregando un borde entre las dos posiciones de las que se resta una.
Tripathi, Venugopalan & West (2010) consideran una secuencia de "subrealizaciones", gráficos cuyos grados están delimitados por la secuencia de grados dada. Muestran que, si G es una subrealización, e i es el índice más pequeño de un vértice en G cuyo grado no es igual a d i , entonces G puede modificarse de manera que produzca otra subrealización, aumentando el grado del vértice i sin cambiando los grados de los vértices anteriores de la secuencia. Los pasos repetidos de este tipo deben llegar finalmente a la realización de la secuencia dada, lo que demuestra el teorema.
Relación con particiones enteras
Aigner y Triesch (1994) describen estrechas conexiones entre el teorema de Erdős-Gallai y la teoría de particiones enteras . Dejar; luego las secuencias enteras ordenadas que suman a puede interpretarse como las particiones de . Bajo la mayorización de sus sumas de prefijo , las particiones forman una celosía , en la que el cambio mínimo entre una partición individual y otra partición inferior en el orden de partición es restar uno de uno de los números. y sumarlo a un número que es menor en al menos dos (podría ser cero). Como muestran Aigner y Triesch, esta operación conserva la propiedad de ser gráfica, por lo que para probar el teorema de Erdős-Gallai basta con caracterizar las secuencias gráficas que son máximas en este orden de mayorización. Proporcionan tal caracterización, en términos de los diagramas de Ferrers de las particiones correspondientes, y muestran que es equivalente al teorema de Erdős-Gallai.
Secuencias gráficas para otros tipos de gráficos
Teoremas similares describen las secuencias de grados de gráficos dirigidos simples, gráficos dirigidos simples con bucles y gráficos bipartitos simples ( Berger 2012 ). El primer problema se caracteriza por el teorema de Fulkerson-Chen-Anstee . Los dos últimos casos, que son equivalentes, se caracterizan por el teorema de Gale-Ryser .
Versión más fuerte
Tripathi y Vijay (2003) demostraron que basta con considerar lala desigualdad tal que con y para . Barrus y col. (2012) restringen el conjunto de desigualdades para gráficos en un empuje opuesto. Si una secuencia positiva de suma par d no tiene entradas repetidas que no sean el máximo y el mínimo (y la longitud excede la entrada más grande), entonces basta con marcar solo ella desigualdad, donde .
Generalización
Una secuencia finita de enteros no negativos con es gráfico si es par y existe una secuencia que sea grafica y mayoritaria . Este resultado fue dado por Aigner & Triesch (1994) . Mahadev y Peled (1995) lo reinventaron y dieron una prueba más directa.
Ver también
Referencias
- Aigner, Martin ; Triesch, Eberhard (1994), "Realizability and uniqueness in graphs", Discrete Mathematics , 136 (1-3): 3-20, doi : 10.1016 / 0012-365X (94) 00104-Q , MR 1313278.
- Barrus, MD; Hartke, SG; Jao, Kyle F .; West, DB (2012), "Umbrales de longitud para listas gráficas dadas entradas fijas mayores y menores y espacios limitados" , Matemáticas discretas , 312 (9): 1494-1501, doi : 10.1016 / j.disc.2011.05.001
- Berger, Annabell (2012), La conexión entre el número de realizaciones para secuencias de grado y mayorización , arXiv : 1212.5443 , Bibcode : 2012arXiv1212.5443B
- Choudum, SA (1986), "Una demostración simple del teorema de Erdős-Gallai sobre secuencias de gráficos", Boletín de la Sociedad Australiana de Matemáticas , 33 (1): 67–70, doi : 10.1017 / S0004972700002872 , MR 0823853.
- Erdős, P .; Gallai, T. (1960), "Gráfok előírt fokszámú pontokkal" (PDF) , Matematikai Lapok , 11 : 264–274
- Mahadev, NVR; Peled, ONU (1995), gráficos de umbral y temas relacionados , Elsevier
- Tripathi, Amitabha; Vijay, Sujith (2003), "Una nota sobre un teorema de Erdős y Gallai", Matemáticas discretas , 265 : 417–420, doi : 10.1016 / s0012-365x (02) 00886-5 , MR 1969393
- Tripathi, Amitabha; Venugopalan, Sushmita; West, Douglas B. (2010), "Una breve prueba constructiva de la caracterización de Erdős-Gallai de listas gráficas" , Discrete Mathematics , 310 (4): 843–844, doi : 10.1016 / j.disc.2009.09.023 , MR 2574834