Инвариант Тутте – Гротендика - Tutte–Grothendieck invariant - Wikipedia

В математика, а Инвариант Тутте – Гротендика (ТГ) это тип инвариант графа который удовлетворяет обобщенному формула удаления-сокращения. Любая оценка Полином Тутте будет примером инварианта TG.^[1][2]

Определение

Функция графика ж является TG-инвариантным, если:^[2]

${\displaystyle f(G)={\begin{cases}c^{|V(G)|}&{\text{if null}}\\xf(G/e)&{\text{if }}e{\text{ is a loop}}\\yf(G\backslash e)&{\text{if }}e{\text{ is a coloop or bridge}}\\af(G/e)+bf(G\backslash e)&{\text{else}}\end{cases}}}$

Над грамм / е обозначает сжатие края в то время как грамм \ е обозначает удаление. Цифры c, Икс, у, а, б параметры.

Обобщение на матроиды

В матроид функция ж ТГ, если:^[1]

${\displaystyle {\begin{aligned}&f(M_{1}\oplus M_{2})=f(M_{1})f(M_{2})\\&f(M)=af(M/e)+bf(M\backslash e)\ \ \ {\text{if }}e{\text{ is not coloop or bridge}}\end{aligned}}}$

Можно показать, что ж дан кем-то:

${\displaystyle f(M)=a^{|E|-r(E)}b^{r(E)}T(M;x/a,y/b)}$

куда E это набор ребер M; р - ранговая функция; и

${\displaystyle T(M;x,y)=\sum _{A\subset E(M)}(x-1)^{r(E)-r(A)}(y-1)^{|A|-r(A)}}$

является обобщением полинома Тутте на матроиды.

Группа Гротендик

Инвариант назван в честь Александр Гротендик из-за аналогичной конструкции Группа Гротендик используется в Теорема Римана – Роха. Подробнее см .:

• Тутте, В. Т. (2008). «Кольцо в теории графов». Математические труды Кембриджского философского общества. 43 (1): 26–40. Дои:10.1017 / S0305004100023173. ISSN  0305-0041. МИСТЕР  0018406.
• Брылавский, Т. (1972). "Кольцо Тутте-Гротендика". Универсальная алгебра. 2 (1): 375–388. Дои:10.1007 / BF02945050. ISSN  0002-5240. МИСТЕР  0330004.

Рекомендации

1. Валлийский. Сложность, узлы, раскраски и подсчет.
2. Гудолл, Эндрю (2008). "Графовые полиномы и инварианты Тутте-Гротендика: приложение элементарного конечного анализа Фурье". arXiv:0806.4848 [math.CO ].