2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
01/01/18 20:50 UTC: Перешли на HTTPS в тестовом режиме. О проблемах пишите в ЛС cepesh.





Начать новую тему Ответить на тему
 
 Вокруг гипотезы Улама-Келли. Теория графов.
Сообщение05.12.2017, 17:04 


16/12/14
415
Доброе время суток, надеюсь что данный пост послужит началом для продуктивного обсуждения и будет интересен широкому кругу читателей.
Собственно, в данном сообщении я хотел бы поделиться с миром некоторыми первыми шагами, которые удалось сделать в рамках разработанного мною подхода к этой старой проблеме в области задач об изоморфизмах графов. Мне было бы интересно услышать мнение компетентных людей на то, что будет изложено ниже, а также получить некоторые рекомендации и ответы на некоторые интересующие меня вопросы. Сразу хочу отметить тот факт, что я студент 3 курса МФТИ, так что с одной стороны никакого большого опыта реальной работы у меня нет, а с другой мне очень хочется набрать материала для первой публикации в моей жизни, так что прошу отнестись к моему положению с пониманием. Я был бы очень рад, если бы нашелся человек, также увлекающийся данной задачей , который был бы заинтересован в возможном соавторстве.

Для начала я приведу формулировку самой оригинальной задачи, дабы ввести читателей в свои обозначения и задам несколько важных, вопросов, ответ на которые мне неизвестен. Сразу отмечу, что все графы, которые рассматриваются ниже суть есть простые графы без смежных ребер и петель, также поскольку содержательной гипотеза Улама-Келли становится лишь в классе связных графов, то их то мы и будем в основном рассматривать.

Определение 1.
Колодой графа $\Gamma$ называется множество его подграфов, образованных путем удаления из исходного графа некоторого одной вершины. Обозначается оно так:
$Deck \ \Gamma = \left\lbrace \Gamma_v : \Gamma_v = \Gamma - v, v \in V(\Gamma) \right\rbrace$, где под $V(\Gamma)  $ как и обычно подразумевается множество всех вершин данного графа.
Две колоды $D_1$ и $D_2$ называются изоморфными, если между ними существует такая биекция $f: D_1 \to D_2$, что $\forall \Gamma \in D_1 \to  \Gamma \simeq f(\Gamma)$, то есть найдется такое взаимооднозначное соответствие между элементами двух колод, что оно переводит друг в друга лишь изоморфные элементы этих колод.

Множество всех изоморфизмов данной колоды $D$ на себе обозначается $Aut D$, и является группой автоморфизмов колоды, группа автоморфизмов колоды данного графа лично я назвал группой Келли данного графа, и обозначаю ее $Kel \ \Gamma$.

На данном этапе уже возникает сложный вопрос, который ставит Ф. Харрари в своей монографии на теорию графов: Как понять является ли данный набор из $n$ графов, состоящих из $n-1$ вершины колодой некоторого графа или нет? То есть как понять по данной колоде, есть ли некоторый граф, колода которого изоморфна данной? Это очень сложный вопрос, над которым я убежден бьются многие, и мне хотелось бы найти ссылки на уже известные результаты в этой области. Так мне кажется, что именно содержательных фактов о том, какими свойствами должна обладать колода, которая может быть реализована, не хватает для завершения разрешения проблема Улама-Келли.

Собственно гипотеза Улама-Келли может быть сформулирована следующим образом:

Пусть графы $\Gamma$ и $H$ таковы, что их колоды изоморфны, тогда и сами графы должны быть изоморфны, если число их вершин больше 2.

Лично мне кажется, что в общем виде данная гипотеза, конечно, неверна и ниже будет изложено, почему я придерживаюсь такого мнения. А пока я перейду к самой содержательной части данного сообщения: к некоторым пока весьма скромным, но все же достаточно интересными результатам:

Определение 2.
Пусть $f: \Gamma \to H$ - некоторый биекция между двумя графами, тогда она, конечно, порождает биекцию между колодами по правилу $f(\Gamma - v) = H - f(v)$, и обратно любая биекция между колодами порождает биекцию между графами по следующему правилу, если $f(\Gamma - v) = H - u$, то $f(v) = u$.

И данное определение позволяет задаться интересным вопросом, а правда да ли что любой изоморфизм между колодами порождается некоторым изоморфизмом между графами? Ясно, что изоморфизмов между колодами точно не меньше чем между графами, но как будет показано ниже бывают случаи, когда их больше! Что и вызывает у меня сомнения в гипотезе Улама-Келли для всех графов.

Чтобы ответить на поставленный только что вопрос необходимо для начала исследовать вопросы связанные с автоморфизмами колоды и графа, то есть изучить отношение между двумя группами: $Aut \ \Gamma$ и $Kel \ \Gamma$, ясно что каждый автоморфизм графа порождает некоторый автоморфизм колоды, поэтому можно говорить о естественном вложении группы автоморфизмов данного графа в его группу Келли: $Aut \ \Gamma \hookrightarrow Kel \ \Gamma$, однако не факт, что данное вложение есть изоморфизм между двумя группами, что позволяет ввести следующее содержательное определение:

Определение 3.
Граф $\Gamma$ называется однозначным (простите не смог придумать нечто более красивое), если его группа Келли изоморфна группе его автоморфизмов. В таком случае разумеется вложение описанное выше доставляет один из изоморфизмов между двумя данными группами.

Забегая вперед скажу, что по моей интуиции именно требование однозначности для графов $\Gamma$ и $H$ является существенным для гипотезы Улама-Келли. Поскольку оно гарантирует, что любой изоморфизм между двумя однозначными графами порождает изоморфизм их колод, и обратно любой изоморфизм их колод порожден некоторым графическим изоморфизмом.

Лемма 1.
Если графы $\Gamma$ и $H$ однозначные и изоморфные, то любой изоморфизм между их колодами порожден изоморфизмом между самими графами. Причем данное высказывание справедливо и в обратную сторону.

Док-во:

1) Поскольку любой изоморфизм между графами сразу же задает изоморфизм между их колодами, то нам достаточно доказать, что число изоморфизмов между колодами совпадает с числом изоморфизмом между самими графами. Сделать это легко, если вспомнить, что число изоморфизмов между колодами совпадает с мощностью их групп автоморфизмов, то же самое справедливо и для графов, а так как группы Келли и группы автоморфизмов для графов изоморфны по условию леммы, то мы уже все доказали.

2) В обратную стороны доказать тоже нетрудно: если число изоморфизмом совпадает, то мощности групп автоморфизмов и групп Келли для наших графов совпадают, что вкупе с существованием естественного вложение и дает нам факт изоморфности этих групп.

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

Важный момент: понятие однозначного графа является содержательным, ибо есть как однозначные так и неоднозначные графы, что показывает следующая лемма:

Лемма 2.
Любой граф, группа автоморфизмом которого есть циклическая группа простого порядка $p \geqslant 3$, является неоднозначным.

Я приведу простой набросок доказательства для случая $p=3$, оно легко переносится на общий случай:

1) Будем называть действие группы $G$ на множестве $X$ неполным заданное отображением $f: G \to Sym(x)$, если существует такая подгруппа группы всех перестановок множества $X$: $H \leqslant Sym(X)$, что выполнены 2 условия:

i) $f(G) < H \leqslant Sym(X)$
ii) Орбиты любой точки $x \in X$ у этих двух групп одинаковы: $\forall x \in X \to x^{G} = x^{H}$

Если любое действие группы $G$ задаваемое инъективным вложением неполное, то такую группу будем называть неполной. Теперь так как действие группы автоморфизмов графа на его колоде всегда инъективно по самому построению естественного вложения, то нам нужно лишь доказать неполноту циклической группы 3 порядка, что сразу повлечет за собой возникновение лишних перестановок колоды, которые не изменят орбит, а значит и дадут верные автоморфизмы колоды, которые уже не будут порождены автоморфизмами графа.

2) Чтобы достичь поставленной цели, мы поступим так:
Рассмотрим любое инъективное действие группы $A_3$ на множестве $x$, так как оно инъективное, то найдется перестановка $g \in A_3$, которая будет двигать $X$ не тождественно, то есть будет точка $x_1 \in X$, такая что $x_{1}^{g} \ne {x_1}$, так как справедлива формула
$|A_3| = 3 = |x^{A_3}||Stab_{A_3} x|, \forall x \in X$, то есть мощность нашей группы, которая есть простое число, есть произведение длины орбиты любой точки на мощность ее стабилизатора, то либо стабилизатор у нас состоит из одной перестановки (единицы), либо длина ее орбиты равна 3. То есть мы только что доказали, что есть точка длина орбиты которой равна 3 для любого инъективного действия. Большего нам особенно и не потребуется, запишем орбиту точки x_1 помощью таблицы:
$$\begin{pmatrix}
 x_1&x_2  &x_3 \\
 x_2& x_3 &x_1 \\
 x_3& x_1 &x_2 
\end{pmatrix}$$
Думаю, ясно что я имею ввиду: у нас сразу автоматом, есть 3 точки:$x_1, x_2, x_3$, такие что перестановка $g$ их переводит одна в другую по кругу, собственно из них мы соткем лишнюю перестановку по диагональной схеме:
пусть перестановка $g^{*}$, такова что на всех точках кроме $x_1, x_2, x_3$ оно совпадает с $g$, а в точках $x_1, x_2, x_3$ определена следующим способом:
$$\begin{pmatrix}
x_1 &x_2  &x_3  \\
 x_3&x_3  &x_2
\end{pmatrix}$$
Ясно, что она отличается от $g$ по первой строке, от $g^2$ по второй, а от $g^3$ по третьем строке, что и означает что она не содержится в образе группы $A_3$, с другой стороны видно что новая перестановка не изменяет орбиты, а значит групповая оболочка этой перестановки и образа $A_3$ дадут ту группу, которую мы ищем.

Ясно, что таким же методом, только с большей длиной диагонального метода можно построить нужную перестановку в случае больших простых $p$.

Теперь начну излагать, то что получилось достичь в области самой гипотезы Келли-Улама при требовании однозначности графов:

Пусть графы $\Gamma$ и $H$ однозначны, причем их колоды изоморфны, а число их вершин больше 2, тогда они изоморфны.

1) Рассмотрим все изоморфизмы между колодами этих графов, обозначим это множество за $I_D = {f:  Deck \ \Gamma \to Deck \ H}$, и заодно взглянем на те отображения, которые были порождены данными изоморфизмами, обозначим их совокупность за $I = {f: \Gamma \to H}$

2) Докажем, что I обладает интересным свойством:
i) $\forall f \in I \to f \circ I^{-1} = Aut \ H$
ii)$\forall f \in I \to f^{-1} \circ I = Aut \ \Gamma$

Довольно ясно, что это так, ибо композиции по типу "туда-обратно" между графами порождены такими же композициями "туда-обратно" между колодами, а в случае колод композиции образованы изоморфизмами, что и означает что в случае колод эти композиции обладают указанным выше свойством, а в силу однозначности графов справедлива лемма, описанная выше, что и дает данное утверждение. Данный объект $I$ - я назвал изооблаком и начал его изучать поглубже, однако мне уже намекнули в этой теме: http://dxdy.ru/topic123069.html, что это некоторая комбинация уже известных в алгебре понятий, так что я в скорости постараюсь переформулировать свои мысли в общепринятых терминах и конструкциях.

Благодарю публику за внимание, буду рад любым комментариям.

 Профиль  
                  
 
 Re: Вокруг гипотезы Улама-Келли. Теория графов.
Сообщение05.12.2017, 19:27 


18/01/15
221
Ну, прямо сейчас могу сказать, что Вы --- не первый из участников dxdy, который пытается эту проблему решить. Погуглите.

 Профиль  
                  
 
 Re: Вокруг гипотезы Улама-Келли. Теория графов.
Сообщение11.12.2017, 07:17 


08/12/13
199
Если говорить о моей сырой попытке, наличие других не гуглил, то там будет продолжение. Сейчас нет возможности, а на январь-февраль можно запланировать изложение идеи. Собственно её разработал дальше ещё тем летом, но обсуждение отложил, так как для меня эта задача лишь одна из граней метаматиматической проблемы, куда входят ряд задач из теории чисел и ряд проблем, которые то ли P, то ли NP.
Общая идея состоит в том, что для решения некоторых задач может потребоваться слишком большая для человеческого осознания математическая конструкция. Поэтому искать ответ нужно исключительно обходным путём через инварианты или законы сохранения. Иначе имеется то, что называю дурной бесконечностью, то есть в при данном уровне детализации в самом сложном случае всегда нехватает чуть-чуть, одного маленького шажка, который при этом существует на любом уровне детализации(или разбиения проблемы на отдельные варианты).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group