El invariante de Colin de Verdière es un parámetro de gráficopara cualquier gráfico G, introducido por Yves Colin de Verdière en 1990. Fue motivado por el estudio de la máxima multiplicidad del segundo valor propio de ciertos operadores de Schrödinger . [1]
Definición
Dejar ser un gráfico simple sin bucles con conjunto de vértices. Luegoes la corank más grande de cualquier matriz simétrica tal que:
Caracterización de familias de grafos conocidas
Varias familias conocidas de gráficos se pueden caracterizar en términos de sus invariantes de Colin de Verdière:
- μ ≤ 0 si y solo si G no tiene aristas ; [1] [2]
- μ ≤ 1 si y solo si G es un bosque lineal (una unión disjunta de caminos); [1] [3]
- μ ≤ 2 si y solo si G es plano exterior ; [1] [2]
- μ ≤ 3 si y solo si G es plano ; [1] [2]
- μ ≤ 4 si y solo si G es insertable sin enlaces en R 3 . [1] [4]
Estas mismas familias de gráficos también aparecen en conexiones entre el invariante de Colin de Verdière de un gráfico y la estructura de su complemento :
Graficar menores
Un menor de un gráfico es otro gráfico formado a partir de él contrayendo aristas y eliminando aristas y vértices. El invariante de Colin de Verdière es monótono menor, lo que significa que tomar un menor de un gráfico solo puede disminuir o dejar sin cambios su invariante:
- Si H es menor de G entonces . [2]
Según el teorema de Robertson-Seymour , para cada k existe un conjunto finito H de gráficas tal que las gráficas con invariante como máximo k son las mismas que las gráficas que no tienen ningún miembro de H como menor. Colin de Verdière (1990) enumera estos conjuntos de menores prohibidos para k ≤ 3; para k = 4 el conjunto de menores prohibidos consta de las siete gráficas de la familia Petersen , debido a las dos caracterizaciones de las gráficas insertables sin enlaces como las gráficas con μ ≤ 4 y las gráficas sin menor de la familia Petersen. [4] Para k = 5 el conjunto de menores prohibidos incluye 78 gráficos de la familia Heawood, y se conjetura que no hay más. [6]
Número cromático
Colin de Verdière (1990) conjeturó que cualquier gráfico con μ invariante de Colin de Verdière puede ser coloreado con colores μ + 1 como máximo. Por ejemplo, los bosques lineales tienen invariante 1 y pueden ser de 2 colores ; los gráficos planos exteriores tienen dos invariantes y pueden ser de 3 colores; las gráficas planas tienen invariante 3 y (según el teorema de los cuatro colores ) pueden tener 4 colores.
Para gráficos con Colin de Verdière invariante como máximo cuatro, la conjetura sigue siendo cierta; Estos son los gráficos incrustables sin enlaces , y el hecho de que tengan un número cromático como máximo cinco es una consecuencia de una demostración de Neil Robertson , Paul Seymour y Robin Thomas ( 1993 ) de la conjetura de Hadwiger para gráficos libres de K 6 -menores.
Otras propiedades
Si un gráfico tiene un número de cruce , tiene Colin de Verdière invariante a lo sumo . Por ejemplo, los dos gráficos de Kuratowski y ambos pueden dibujarse con un solo cruce y tener Colin de Verdière invariante como máximo cuatro. [2]
Influencia
El invariante de Colin de Verdière se define a través de una clase de matrices correspondientes al gráfico en lugar de una sola matriz. En la misma línea, se pueden definir y estudiar otros parámetros del gráfico en la misma línea, como el rango mínimo , el rango mínimo semidefinido y el rango de sesgo mínimo .
Notas
- ↑ a b c d e f g h i j van der Holst, Lovász y Schrijver (1999) .
- ↑ a b c d e f Colin de Verdière (1990) .
- ↑ Colin de Verdière (1990) no establece este caso explícitamente, pero se sigue de su caracterización de estos gráficos como los gráficos sin triángulo ni garra menor.
- ↑ a b Lovász y Schrijver (1998) .
- ↑ a b c Kotlov, Lovász y Vempala (1997) .
- ^ Hein van der Holst (2006). "Gráficos y obstrucciones en cuatro dimensiones" (PDF) . Revista de Teoría Combinatoria , Serie B . 96 (3): 388–404. doi : 10.1016 / j.jctb.2005.09.004 .
Referencias
- Colin de Verdière, Yves (1990), "Sur un nouvel invariant des graphes et un critère de planarité", Journal of Combinatorial Theory, Serie B , 50 (1): 11-21, doi : 10.1016 / 0095-8956 (90) 90093-F. Traducido por Neil Calkin como Colin de Verdière, Yves (1993), "Sobre una nueva gráfica invariante y un criterio de planaridad", en Robertson, Neil ; Seymour, Paul (eds.), Teoría de la estructura de grafos: Proc. Conferencia de investigación conjunta de verano AMS-IMS-SIAM sobre menores gráficos , matemáticas contemporáneas, 147 , American Mathematical Society, págs. 137–147.
- van der Holst, Hein; Lovász, László ; Schrijver, Alexander (1999), "El parámetro gráfico de Colin de Verdière", Teoría de grafos y biología combinatoria (Balatonlelle, 1996) , Bolyai Soc. Matemáticas. Stud., 7 , Budapest: János Bolyai Math. Soc., Págs. 29–85.
- Kotlov, Andrew; Lovász, László ; Vempala, Santosh (1997), "Las representaciones numéricas y esféricas de un gráfico de Colin de Verdiere" , Combinatorica , 17 (4): 483–521, doi : 10.1007 / BF01195002
- Lovász, László ; Schrijver, Alexander (1998), "Un teorema de Borsuk para enlaces antípodas y una caracterización espectral de gráficos incrustables sin enlaces", Proceedings of the American Mathematical Society , 126 (5): 1275-1285, doi : 10.1090 / S0002-9939-98- 04244-0.
- Robertson, Neil ; Seymour, Paul ; Thomas, Robin (1993), "Conjetura de Hadwiger para gráficos libres de K 6 " (PDF) , Combinatorica , 13 : 279–361, doi : 10.1007 / BF01202354.