Является ли количество узловых прядей неизменным?
Вопрос: Зависит ли количество компонентов в узле от конкретного плоского вложения?
Я исследовал, как вычислить количество компонентов («отдельных нитей») в кельтском узле на основе базовой структуры плоского графа. (См. Взаимосвязь между узлами / звеньями и планарными графиками здесь ).
По-видимому, расчет для общих графиков немного сложен; например, ссылка в этом вопросе указывает на то, что для униформы$m\times n$ сетка квадратов, количество компонентов $\mathrm{lcd}(m,n)$.
Меня удовлетворило бы найти формулу для вычисления количества компонентов («нитей») или отношения между количеством нитей и различными свойствами графа, такими как его степень, спектр и т. Д., Даже если эти свойства было трудно вычислить. .
Один из подходов, который я использовал, заключается в использовании связанных компонентов: каждая отдельная нить следует определенной траектории, и связанные компоненты этих траекторий точно соответствуют нитям. Вы можете определить траекторию как отображение функции перехода (некоторая дополнительная структура плюс) каждого ребра к его преемнику; это перестановка на (структурированных) ребрах, циклы которых являются компонентами.
Функция перехода может быть закодирована как собственный производный ориентированный граф (аналогично карте с графическим кодированием ), чьи связанные компоненты являются компонентами узлового взаимодействия. Из линейной алгебры мы знаем, что количество компонент связности можно восстановить как кратность нулевого собственного значения лапласиана матрицы смежности.
Однако я знаю, что тот же график $G$могут иметь несколько неизоморфных плоских вложений (т. е. чьи двойственные неизоморфные). По моему опыту, это изменило некоторые свойства завязывания узлов (например, количество скручиваний в каждом компоненте), но не количество компонентов:
У меня такой вопрос:
Вопрос: Зависит ли количество компонентов в узле от конкретного плоского вложения? Как мы это докажем?
Моя интуиция подсказывает, что количество компонентов является инвариантом, но я не смог привести контрпример или доказательство, используя свой подход, описанный выше.
Гипотеза: если $G$ является графом, то соответствующий узел имеет $c$ компоненты, где
$$T_G(-1,-1) = (-1)^{|E(G)|}\cdot (-2)^{c - 1}$$
и $T_G$ - многочлен Тутте, а $|E(G)|$количество ребер в графе. (?)
Ответы
Позволять $D$быть диаграммой ссылки. Например,$D$это может быть схема кельтского узла или ссылка, изображенная в вашем сообщении. Позволять$G$ быть шахматным графом $D$. График$G$ это график, описанный в вашем первом пункте.
Ответ: Количество компонентов$D$ определяется абстрактным графом $G$ и не зависит от того, как $G$ вложен в плоскость.
Насколько мне известно, это было впервые доказано Мишелем Лас Вергнасом в 1979 году. Он показал, что количество компонентов $D$ определяется полиномом Тутте $T_G(-1,-1)$. Поскольку многочлен Тутте не зависит от конкретного вложения$G$, результат следует. Ссылка на этот документ
- Лас Вергнас, Мишель. Об эйлеровых разбиениях графов . Теория графов и комбинаторика (Proc. Conf., Open Univ., Milton Keynes, 1978), стр. 62–75, Res. Notes in Math., 34, Pitman, Boston, Mass.-London, 1979.
Мне было нелегко найти копию вышеупомянутой статьи, поэтому вот еще один способ получить решение, благодаря Дэну Сильверу и Сьюзан Уильямс ( ссылка arXiv ). Они определяют матрицу$Q_2(G)$ чьи записи находятся в поле с двумя элементами $\mathbb{F}_2$следующим образом. И строки, и столбцы матрицы индексируются вершинами$v_1,\dots,v_n$ из $G$. Если$i\neq j$, то $ij$ вход $Q_2(G)$ это количество ребер между вершинами $v_i$ и $v_j$ (принято$\mod 2$). В$ii$ вход $Q_2(G)$ это сумма других записей в строке $i$ (снова взят$\mod 2$). Точно так же мы могли бы сказать$ii$ вход в $Q_2(G)$ это сумма других записей в столбце $i$.
В теореме 1.1 связанной статьи они доказывают, что количество компонент $D$ равно недействительности $Q_2(G)$. В замечании 1.2 они отмечают, что отсюда следует количество компонентов$D$ не зависит от плоского вложения $G$.
Изменить: у меня нет доступа к статье Лас Вергнаса, но я могу дать другое объяснение результата, используя полином Тутте и полином Джонса.
Позволять $L$ быть альтернативным звеном, пусть $D$ - знакопеременная диаграмма звена, и пусть $G$ быть шахматным графом $D$. Тогда многочлен Тутте$T_G(x,y)$ из $G$ и многочлен Джонса $V_L(t)$ из $L$ связаны следующим образом: $$V_L(t) = f_D(t) T_G(-t,-t^{-1})$$ для функции $f_D(T)$ определяется $$f_D(t) = (-1)^{w(D)}t^{\frac{1}{4}(|E| - 2(|V|-1)+3w(D))}$$ где $w(D)$ корчится $D$, $|E|$ количество ребер в $G$, и $|V|$ количество вершин $D$. Заметить, что$|f_D(1)|=1$, и поэтому $|V_L(1)| = |T_G(-1,-1)|$.
Многочлен Джонса удовлетворяет соотношению скейна $$(t^{\frac{1}{2}}-t^{-\frac{1}{2}})V_{L_0}(t) = t^{-1}V_{L_+}(t) - tV_{L_-}(t)$$ где $L_+,L_-,$ и $L_0$ как показано ниже.
Настройка $t=1$ в приведенном выше соотношении мотков дает $V_{L_+}(1)=V_{L_-}(1)$. Другими словами, многочлен Джонса оценивается в$t=1$ не меняется при пересечении изменений, и, следовательно, $V_L(1)=V_{\bigcirc\sqcup\dots\sqcup\bigcirc}(1)$ где $\bigcirc\sqcup\dots\sqcup\bigcirc$ - тривиальное звено с тем же количеством компонентов, что и $L$. Многочлен Джонса от$\bigcirc\sqcup\dots\sqcup\bigcirc$ является $V_{\bigcirc\sqcup\dots\sqcup\bigcirc}(t) = (-t^{\frac{1}{2}}-t^{-\frac{1}{2}})^{m-1}$ где $m$ количество компонентов $\bigcirc\sqcup\dots\sqcup\bigcirc$. Таким образом$$|T_G(-1,-1)|=|V_L(1)|=|V_{\bigcirc\sqcup\dots\sqcup\bigcirc}(1)| = 2^{m-1}.$$
Вышеупомянутый случай обрабатывается, когда $L$чередуется. Если$L$не чередуется, то действуйте следующим образом. Позволять$D$ быть любой диаграммой $L$. Определить$D_{\text{alt}}$ быть диаграммой с той же тенью, что и $D$ но чьи пересечения изменены на чередующиеся, и определяют $L_{\text{alt}}$ быть связью, диаграмма которой $D_{\text{alt}}$. Обратите внимание, что$D$ и $D_{\text{alt}}$ иметь такой же график шахматной доски $G$. Из приведенного выше аргумента следует, что$|T_G(-1,-1)|=2^{m-1}$ где $m$ количество компонентов $L_{\text{alt}}$. поскольку$L_{\text{alt}}$ и $L$ имеют одинаковое количество компонентов, результат следует для $L$ также.