Подходы к GI, вдохновленные проблемой узлов

14

GI и проблема узлов являются проблемой определения структурной эквивалентности математических объектов. Есть ли какие-либо результаты установления связей между ними? Хорошие связи проблемы узлов со статистической физикой были изучены с помощью полиномов узлов , есть ли похожие результаты для ?граммя

Было бы особенно полезно узнать, есть ли какие-либо стандартные результаты / предупреждения / предложения / комментарии, прежде чем начать изучать мотивирован проблемой узла. На самом деле, мне было интересно, если это рекомендуется для изучения в этом направлении для моей магистерской диссертации. Я интересуюсь квантовыми / классическими подходами к G I и алгебраическими задачами. Любые другие предложения приветствуются.граммяграммя

DurgaDatta
источник
из математических изоморфных графов : «В некотором смысле изоморфизм графов прост на практике, за исключением набора патологически сложных графов, которые, кажется, вызывают все проблемы. Таким образом, в отличие от теории узлов, никогда не было каких-либо значимых пар графов, для которых изоморфизм была не решена ... К сожалению, почти наверняка не существует простого для вычисления универсального графа-инварианта, основанного на спектре графа или любых других параметрах графа (Royle 2004). "
ВЗН
2
Видимо, эквивалентность узлов также проста на практике.
Джефф
У меня есть постер, аналогичный вопрос здесь Physics.stackexchange.com/questions/39328/… также
DurgaDatta
Насколько мне известно, нет "патологически сложных" узлов, которые вызывают все проблемы. Было бы очень интересно найти семейство unknots, которые имели плохое время выполнения в различных программах распознавания unknot, либо доказуемо, либо просто экспериментально.
Сэм Нид

Ответы:

17

Одна связь состоит в том, что изоморфизм графов и изоморфизм узлов являются частными случаями 3-многообразного гомеоморфизма. В случае узла два узла изоморфны, если их дополнения (многообразия, образованные удалением точек узла из 3-пространства) гомеоморфны.

А в случае графов графы можно преобразовывать в многообразия таким образом, чтобы графы были изоморфными тогда и только тогда, когда многообразия гомеоморфны. Я написал комментарий об этом в пост в Google+ в декабре прошлого года, но, к сожалению, не в пост, которым я могу поделиться. Конструкция должна начинаться с многообразия для каждой вершины v в форме дополнения в 3-сфере букета петель степени (v) (соединенных вместе в общей вершине). Для каждого края uv соедините коллекторы для u и v вместе с помощью операциии свяжите одну петлю от вас и одну петлю от v поперек операционного шара. Тогда каждый изоморфизм графов поднимается до гомеоморфизма получающегося многообразия (это было бы верно, даже если бы мы только использовали операцию на 3-сферах без букетов), и букеты препятствовали тому, чтобы у многообразия были дополнительные гомеоморфизмы, которые не происходят из графа. ,

Дэвид Эппштейн
источник
7

более общий вопрос - это связь между теорией узлов и теорией графов. В качестве одного из возможных мест для начала есть связь между полиномом Джонса (используется для классификации узлов) и полиномом Тутте плоских графов. то есть в теории узлов, многочлен Тутте появляется как многочлен Джонса чередующегося узла. (так что, возможно, есть некоторая связь теории узлов с GI на плоских графах.)

см. 7,8 в:

Вычисление полинома Тутте для графа и полинома Джонса для переменного звена умеренного размера Sekine, Imai, Tani

ПОЛИНОМ И ДЖОНСЫ НА ПОВЕРХНОСТИ ОЛИВЕР Т. ДАСБАХ, ДЭВИД ФУТЕР, ЭФСТРАТИЯ КАЛЬФАГИАННИ, СЯО-СОНГ ЛИН, И НИЛ У. СТОЛЬЦФУС

ВЗН
источник