2014 dxdy logo

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

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




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


16/12/14
472
Доброе время суток!
Данное сообщение призвано развить проблематику, ранее затронутую в моем предыдущем сообщении: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 сообщение ] 

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



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

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


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

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