2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Несколько вопросов вокруг колоды некоторого графа.
Сообщение08.12.2017, 21:53 


16/12/14
474
Доброе время суток!
Данное сообщение призвано развить проблематику, ранее затронутую в моем предыдущем сообщении:http://dxdy.ru/topic123116.html, однако в целом не будет связано с гипотезой Улама-Келли напрямую, поэтому я предпочел выделить его в отдельную ветвь дискуссии. Впрочем, я все равно буду использовать терминологию введенную в предыдущем сообщении, поэтому рекомендую хотя бы бегло пробежать его глазами. Все графы, как и обычно, простые (без кратных ребер и петель).

Модератору: Если Вы все таки сочтете нужным, то эти 2 темы можно слить в одну.

Итак в данном сообщении я изложу 2 гипотезы, связанные с колодами произвольных графов и докажу их эквивалентность.
Предположение 1.

Пусть $\Gamma$ - некоторый граф, а $Aut \ \Gamma$ - его группа автоморфизмов, в то время как $Kel \ \Gamma$ - есть группа автоморфизмов его колоды, тогда справедливо следующее утверждение:
Если $u, v$ - 2 такие вершины, что их орбиты относительно группы $Aut \ \Gamma$ - не пересекаются, то орбиты максимальных подграфов, образованных удалением этих вершин из исходного графа, относительно $Kel \ \Gamma$ - тоже непересекаются:
$\forall u, v \in V(\Gamma): u \notin v^{Aut \ \Gamma} \to \Gamma - u \notin (\Gamma - v)^{Kel \ \Gamma}$

Предположение 2.
Группа $Kel \ \Gamma$ представима в следующем виде:
$Kel \ \Gamma = Sym(O_1)\times \dots \times Sym(O_m)$, где $O_i$ - разные орбиты элементов колоды относительно действия группы автоморфизмов графа $\Gamma$

Лемма
Предположения 1 и 2 эквивалентны.
Док-во:

1) Заметим, что $Kel \ \Gamma$ всегда представляется следующем виде:
$Kel \ \Gamma = Sym(A_1) \times \dots \times Sym(A_p)$, где $A_p$ - множества образованные путем объединения некоторого количества орбит из предположения 2.
Это ясно в силу определения группы $Kel \ \Gamma$, которая переставляет между собой изоморфные элементы колоды. Так как все члены орбиты группы автоморфизмов графа ясно дело изоморфны, то $Kel \ \Gamma$ действует на каждой такой орбите, как полная группа перестановок, если же так вышло что элементы двух разных орбит все равно изоморфны, то эти 2 разные орбиты как бы перемешиваются группой $Kel \ \Gamma$.

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

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

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

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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