Инвариант Колен де Вердьера

03.02.2021

Инвариант Колен де Вердьера — характеристика графа μ ( G ) {displaystyle mu (G)} , определённая для любого графа G, введённая Ивом Колен де Вердьером в 1990 году в процессе исследования кратности второго собственного значения некоторых операторов Шрёдингера.

Определение

Пусть G = ( V , E ) {displaystyle G=(V,E)} — простой (не содержащий петель и кратных рёбер) ациклический граф. Без потери общности поименуем множество вершин следующим образом: V = { 1 , … , n } {displaystyle V={1,dots ,n}} . Тогда μ ( G ) {displaystyle mu (G)} — наибольший коранг любой такой матрицы M = ( M i , j ) ∈ R ( n ) {displaystyle M=(M_{i,j})in mathbb {R} ^{(n)}} , что:

  • (M1) для любых i , j {displaystyle i,j} , где i ≠ j {displaystyle i eq j} : M i , j < 0 {displaystyle M_{i,j}<0} , если i и j смежны, и M i , j = 0 {displaystyle M_{i,j}=0} , в противном случае
  • (M2) M имеет ровно одно собственное значение мультиплетности 1;
  • (M3) не существует такой ненулевой матрицы X = ( X i , j ) ∈ R ( n ) {displaystyle X=(X_{i,j})in mathbb {R} ^{(n)}} , что M X = 0 {displaystyle MX=0} , и что X i , j = 0 {displaystyle X_{i,j}=0} всякий раз, когда i = j {displaystyle i=j} или M i , j ≠ 0 {displaystyle M_{i,j} eq 0} .

Классификация известных групп графов

С точки зрения инварианта Колен де Вердьера, некоторые хорошо известные семейства графов обладают характерными особенностями:

  • μ ( K 1 ) = 0 {displaystyle mu (K_{1})=0} , μ ( K n ) = n − 1 {displaystyle mu (K_{n})=n-1} , μ ( K n ¯ ) = 1 {displaystyle mu ({overline {K_{n}}})=1} при n > 1 {displaystyle n>1} ;
  • μ ≤ 1 тогда и только тогда, когда G является линейным лесом (лесом, в котором каждый компонент является путём, то есть инцидентность любой вершины не больше 2);
  • μ ≤ 2 тогда и только тогда, когда G является внешнепланарным графом (все вершины лежат на одной грани);
  • μ ≤ 3 тогда и только тогда, когда G является планарным графом;
  • μ ≤ 4 тогда и только тогда, когда G является бессвязно встраиваемым, то есть не существует двух циклов в G, для которых при отображении на евклидово пространство (коэффициент зацепления) равен нулю.

Эти же группы графов проявляют свои отличительные черты и при анализе связи между инвариантом графа и дополнением этого графа:

  • Если дополнение графа с n вершинами является линейным лесом, то μ ≥ n − 3;
  • Если дополнение графа с n вершинами является внешнепланарным графом, тоμ ≥ n − 4;
  • Если дополнение графа с n вершинами является планарным графом, то μ ≥ n − 5.

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

Минором графа G называют граф H, полученный из G последовательным удалением вершин, удалением рёбер и сжатием рёбер. Инвариант Колена де Вердьера монотонен относительно операции взятия минора в том смысле, что минорирование графа не может увеличить его инвариант:

Если H является минором G, то μ ( H ) ≤ μ ( G ) {displaystyle mu (H)leq mu (G)} .

По теореме Робертсона — Сеймура, для любого k существует H, конечное множество графов такое, что для любого графа с инвариантом не более k графы из H не могут быть минорами. В работе Colin de Verdière 1990 перечисляются множества таких недопустимых миноров для k ≤ 3; для k = 4 множество недопустимых миноров состоит из семи графов Petersen family по определению бессвязно встраиваемого графа как графа с μ ≤ 4 и без графов Петерсена в качестве миноров.

Связь с хроматическим числом

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

Для графов с инвариантом де Вердьера не более четырёх предположение истинно; они все являются бессвязно встраиваемыми, и тот факт, что они раскрашиваются пятью цветами, является следствием доказательства гипотезы Хадвигера для графов без миноров типа K6 в работе Robertson, Seymour & Thomas 1993.

Другие свойства

Если число пересечений графа равно k, то инвариант де Вердьера для него будет не более k + 3. Например, графы Куратовского K5 и K3,3 могут быть изображены с одним пересечением, и инвариант для них будет не более четырёх.