Інваріант Колен де Вердьєра

Інваріа́нт Колен де Вердьєра — характеристика графа ${\displaystyle \mu (G)}$, визначена для будь-якого графа ${\displaystyle G}$, яку 1990 року ввів Ів Колен де Вердьє^[fr] в процесі дослідження кратності другого власного значення деяких операторів Шредінгера^[1].

Визначення

Нехай ${\displaystyle G=(V,E)}$ — простий (без петель і кратних ребер) ациклічний граф. Без втрати загальності поіменуємо множину вершин у такий спосіб: ${\displaystyle V=\{1,\dots ,n\}}$. Тоді ${\displaystyle \mu (G)}$ — найбільший коранг^[en] будь-якої такої симетричної матриці ${\displaystyle M=(M_{i,j})\in \mathbb {R} ^{(n)}}$, що:

• (M1) для будь-яких ${\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) ${\displaystyle M}$ має рівно одне від'ємне власне значення кратності ${\displaystyle 1}$;
• (M3) не існує такої ненульової матриці ${\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}$^[2][1].

Класифікація відомих груп графів

З точки зору інваріанта Колен де Вердьєра, деякі добре відомі сімейства графів мають характерні особливості:

• ${\displaystyle \mu (K_{1})=0}$, ${\displaystyle \mu (K_{n})=n-1}$, ${\displaystyle \mu ({\overline {K_{n}}})=1}$ при ${\displaystyle n>1}$;^[1][2]
• μ ≤ 1 тоді й лише тоді, коли G є лінійним лісом (лісом, у якому кожен компонент є шляхом, тобто інцидентність будь-якої вершини не більша від 2);^[1][3]
• μ ≤ 2 тоді й лише тоді, коли G є зовніпланарним графом (усі вершини лежать на одній грані);^[1][2]
• μ ≤ 3 тоді й лише тоді, коли G є планарним графом;^[1][2]
• μ ≤ 4 тоді й лише тоді, коли G є незачеплено вклада́ним, тобто не існує двох циклів у G, для яких при відображенні на евклідів простір коефіцієнт зачеплення дорівнює нулю.^[1][4]

Ці ж групи графів проявляють свої відмінні риси і під час аналізу зв'язку між інваріантом графа і доповненням цього графа:

• Якщо доповнення графа з n вершинами є лінійним лісом, то μ ≥ n − 3;^[1][5]
• Якщо доповнення графа з n вершинами є зовніпланарним графом, то μ ≥ n − 4;^[1][5]
• Якщо доповнення графа з n вершинами є планарним графом, то μ ≥ n − 5.^[1][5]

Мінори графів

Мінором графа G називають граф H, отриманий з G послідовним видаленням вершин, видаленням ребер і стисненням ребер. Інваріант Колена де Вердьєра монотонний відносно операції взяття мінора в тому сенсі, що мінорування графа не може збільшити його інваріанта:

Якщо H є мінором G, то ${\displaystyle \mu (H)\leq \mu (G)}$.^[2]

В теоремі Робертсона — Сеймура, для будь-якого k існує H, скінченна множина графів така, що для будь-якого графа з інваріантом не більшим від k графи з H не можуть бути мінорами. В роботі (Colin de Verdière, 1990) перелічено множини таких недопустимих мінорів для k ≤ 3; для k = 4 множина недопустимих мінорів складається з семи графів сімейства Петерсена за визначенням незачеплено вкладеного графа як графа з μ ≤ 4 і без графів Петерсена як мінорів^[4].

Зв'язок із хроматичним числом

Колен де Вердьєр (Colin de Verdière, 1990) припустив, що будь-який граф з інваріантом де Вердьера μ можна розфарбувати з використанням не больше ніж μ + 1 кольорів. Наприклад, у лінійних лісів (компоненти яких є двочастковими графами) інваріант дорівнює 1; у зовніпланарних графів інваріант дорівнює 2 і їх можна розфарбувати трьома кольорами; у планарних графів інваріант — 3 і їх можна розфарбувати чотирма кольорами.

Для графів з інваріантом де Вердьєра не більше чотирьох припущення істинне; вони всі є незачеплено вкладаними, і той факт, що вони розфарбовуються п'ятьма кольорами, є наслідком доведення гіпотези Хадвігера для графів без мінорів типу K₆ у роботі Робертсона, Сеймура та Томаса (Robertson, Seymour та Thomas, 1993).

Інші властивості

Якщо число перетинів графа дорівнює k, то інваріант де Вердьєра для нього буде не більшим ніж k + 3. Наприклад, графи Куратовського K₅ і K_3,3 можна зобразити з одним перетином, і інваріант для них буде не більшим від чотирьох^[2].

Примітки

1. (van der Holst, Lovász та Schrijver, 1999).
2. (Colin de Verdière, 1990).
3. У праці (Colin de Verdière, 1990) цей випадок явно не розглянуто, але він явно випливає з результатів аналізу графів, які не мають мінорів виду «трикутник» і «клешня».
4. (Lovász та Schrijver, 1998).
5. (Kotlov, Lovász та Vempala, 1997).

Посилання

• Colin de Verdière, Y. (1990), Sur un nouvel invariant des graphes et un critère de planarité, Journal of Combinatorial Theory, Series B, 50 (1): 11—21, doi:10.1016/0095-8956(90)90093-F
• van der Holst, Hein; Lovász, László; Schrijver, Alexander (1999), The Colin de Verdière graph parameter, Graph Theory and Combinatorial Biology (Balatonlelle, 1996), Bolyai Soc. Math. Stud., т. 7, Budapest: János Bolyai Math. Soc., с. 29—85, архів оригіналу за 3 березня 2016, процитовано 20 січня 2022.
• Kotlov, Andrew; Lovász, László; Vempala, Santosh (1997), The Colin de Verdiere number and sphere representations of a graph, Combinatorica, 17 (4): 483—521, doi:10.1007/BF01195002, архів оригіналу за 3 березня 2016, процитовано 20 січня 2022
• Lovász, László; Schrijver, Alexander (1998), A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs, 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), Hadwiger's conjecture for K₆-free graphs (PDF), Combinatorica, 13: 279—361, doi:10.1007/BF01202354, архів оригіналу (PDF) за 10 квітня 2009, процитовано 20 січня 2022.