Invariante del gráfico de Colin de Verdière

Propiedad gráfica

La invariante de Colin de Verdière es un parámetro gráfico para cualquier gráfico G, introducido por Yves Colin de Verdière en 1990. Fue motivado por el estudio de la multiplicidad máxima del segundo valor propio de ciertos operadores de Schrödinger . ^[1] ${\displaystyle \mu (G)}$

Definición

Sea un gráfico simple con un conjunto de vértices . Entonces es el corank más grande de cualquier matriz simétrica tal que: ${\displaystyle G=(V,E)}$ ${\displaystyle V=\{1,\dots ,n\}}$ ${\displaystyle \mu (G)}$ ${\displaystyle M=(M_{i,j})\in \mathbb {R} ^{(n)}}$

• (M1) para todos con : si , y si ; ${\displaystyle i,j}$ ${\displaystyle i\neq j}$ ${\displaystyle M_{i,j}<0}$ ${\displaystyle \{i,j\}\in E}$ ${\displaystyle M_{i,j}=0}$ ${\displaystyle \{i,j\}\notin E}$
• (M2) tiene exactamente un valor propio negativo, de multiplicidad 1; ${\displaystyle M}$
• (M3) no existe una matriz distinta de cero tal que y tal que si o se cumple. ^{[1] [2]} ${\displaystyle X=(X_{i,j})\in \mathbb {R} ^{(n)}}$ ${\displaystyle MX=0}$ ${\displaystyle X_{i,j}=0}$ ${\displaystyle i=j}$ ${\displaystyle M_{i,j}\neq 0}$

Caracterización de familias de gráficos conocidas.

Varias familias de grafos bien conocidas se pueden caracterizar en términos de sus invariantes de Colin de Verdière:

• μ ≤ 0 si y sólo si G no tiene aristas ; ^{[1] [2]}
• μ ≤ 1 si y sólo si G es un bosque lineal (una unión disjunta de caminos); ^{[1] [3]}
• μ ≤ 2 si y sólo si G es plano exterior ; ^{[1] [2]}
• μ ≤ 3 si y sólo si G es plano ; ^{[1] [2]}
• μ ≤ 4 si y sólo si G es integrable sin enlaces en R ³ . ^{[1] [4]}

Estas mismas familias de gráficos también aparecen en las conexiones entre el invariante de Colin de Verdière de un gráfico y la estructura de su complemento :

• Si el complemento de un gráfico de n -vértices es un bosque lineal, entonces μ ≥ n − 3 ; ^{[ 15]}
• Si el complemento de un gráfico de n -vértices es plano externo, entonces μ ≥ n − 4 ; ^{[ 15]}
• Si el complemento de un gráfico de n -vértices es plano, entonces μ ≥ n − 5 . ^{[ 15]}

Graficar menores

Un gráfico 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 gráfico menor solo puede disminuir o dejar sin cambios su invariante:

Si H es menor de G , entonces . ^[2] ${\displaystyle \mu (H)\leq \mu (G)}$

Según el teorema de Robertson-Seymour , para cada k existe un conjunto finito H de gráficas tal que las gráficas con k invariante como máximo 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 los siete grafos de la familia Petersen , debido a las dos caracterizaciones de los grafos incrustables sin enlaces como los grafos con μ ≤ 4 y como los grafos sin ningún menor de la familia Petersen. ^[4] Para k  = 5 el conjunto de menores prohibidos incluye 78 grafos de la familia Heawood, y se conjetura que no hay más. ^[6]

numero cromatico

Colin de Verdière (1990) conjeturó que cualquier gráfico con μ invariante de Colin de Verdière puede colorearse con como máximo μ + 1 colores. Por ejemplo, los bosques lineales tienen invariante 1 y pueden tener 2 colores ; los gráficos del plano exterior tienen dos invariantes y pueden tener 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 invariantes de Colin de Verdière 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 prueba realizada por Neil Robertson , Paul Seymour y Robin Thomas  (1993) de la conjetura de Hadwiger para K ₆ -gráficos libres menores.

Otras propiedades

Si un gráfico tiene un número de cruce , tiene como máximo el invariante de Colin de Verdière . Por ejemplo, los dos gráficos de Kuratowski y pueden dibujarse con un solo cruce y tener invariantes de Colin de Verdière como máximo cuatro. ^[2] ${\displaystyle k}$ ${\displaystyle k+3}$ ${\displaystyle K_{5}}$ ${\displaystyle K_{3,3}}$

Influencia

La 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, como el rango mínimo , el rango semidefinido mínimo y el rango sesgado mínimo.

Notas

1. van der Holst, Lovász y Schrijver (1999).
2. Colin de Verdière (1990).
3. Colin de Verdière (1990) no establece este caso explícitamente, pero se desprende de su caracterización de estos gráficos como gráficos sin triángulo ni garra menor.
4. Lovász y Schrijver (1998).
5. Kotlov, Lovász y Vempala (1997).
6. 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 J. 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 conjunta de investigación de verano AMS-IMS-SIAM sobre gráficos menores , Matemáticas contemporáneas, vol. 147, Sociedad Estadounidense de Matemáticas, 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., vol. 7, Budapest: János Bolyai Math. Soc., págs. 29–85, archivado desde el original el 3 de marzo de 2016 , consultado el 6 de agosto de 2010.
• Kotlov, Andrés; Lovász, László ; Vempala, Santosh (1997), "El número de Colin de Verdiere y las representaciones esféricas de un gráfico", Combinatorica , 17 (4): 483–521, doi :10.1007/BF01195002, archivado desde el original el 3 de marzo de 2016 , recuperado 2010-08-06
• Lovász, László ; Schrijver, Alexander (1998), "Un teorema de Borsuk para enlaces antípodas y una caracterización espectral de gráficos integrables sin enlaces", Actas de la Sociedad Matemática Estadounidense , 126 (5): 1275–1285, doi : 10.1090/S0002-9939-98- 04244-0.
• Robertson, Neil ; Seymour, Pablo ; Thomas, Robin (1993), "Conjetura de Hadwiger para gráficos libres de K6" (PDF) , Combinatorica , 13 : 279–361, doi :10.1007/BF01202354, archivado desde el original (PDF) el 10 de abril de 2009 , consultado en 2010 -08-06.