Система вращения

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

Каждая схема вращения определяет уникальное двухклеточное вложение связного мультиграфа на замкнутую ориентированную поверхность (с точностью до топологической эквивалентности, сохраняющей ориентацию). И наоборот, любое вложение связного мультиграфа G на ориентированную замкнутую поверхность определяет уникальную систему вращения, имеющую G в качестве основного мультиграфа. Эта фундаментальная эквивалентность между системами вращения и двухклеточными вложениями была впервые установлена в двойственной форме Лотаром Хеффтером в 1890-х годах. ^[1] и широко использовался Рингелем в 1950-х годах. ^[2] Независимо Эдмондс дал основную форму теоремы. ^[3] а детали его исследования были популяризированы Янгсом. ^[4] Обобщение на мультиграфы было представлено Гроссом и Альпертом. ^[5]

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

Формальное определение

Формально система вращения определяется как пара (σ, θ), где σ и θ — перестановки, действующие на одном и том же основном множестве B , θ — неподвижных точек без инволюция , а группа <σ, θ>, порожденная σ и θ действует транзитивно на B .

Чтобы получить систему вращения из двухклеточного вложения связного мультиграфа G на ориентированную поверхность, пусть B состоит из стрелок (или флагов , или полуребер ) G ; то есть для каждого ребра G мы формируем два элемента B , по одному для каждой конечной точки ребра. Даже если ребро имеет ту же вершину, что и обе его конечные точки, мы создаем две вытачки для этого ребра. Мы позволяем θ( b ) быть другим дротиком, образованным из того же края, что и b ; это явно инволюция без фиксированных точек. Пусть σ( b ) будет дротиком в положении по часовой стрелке от b в циклическом порядке ребер, инцидентных одной и той же вершине, где «по часовой стрелке» определяется ориентацией поверхности.

Если мультиграф вложен в ориентируемую, но не ориентированную поверхность, он обычно соответствует двум системам вращения, по одной для каждой из двух ориентаций поверхности. Эти две системы вращения имеют одинаковую инволюцию θ, но перестановка σ для одной системы вращения является обратной соответствующей перестановке для другой системы вращения.

Восстановление вставки из системы ротации

Чтобы восстановить мультиграф из системы вращения, мы формируем вершину для каждой орбиты σ и ребро для каждой орбиты θ. Вершина инцидентна ребру, если эти две орбиты имеют непустое пересечение. Таким образом, количество инцидентов на вершину равно размеру орбиты, а количество инцидентов на ребро равно двум. Если система вращения получена из 2-клеточного вложения связного мультиграфа G , граф, полученный из системы вращения изоморфен G , .

Чтобы встроить граф, полученный из системы вращения, на поверхность, сформируйте диск для каждой орбиты σθ и склейте два диска вместе вдоль ребра e всякий раз, когда два дротика, соответствующие e, принадлежат двум орбитам, соответствующим этим дискам. Результатом является двухклеточное вложение полученного мультиграфа, две ячейки которого представляют собой диски, соответствующие орбитам σθ. Поверхность этого вложения может быть ориентирована таким образом, чтобы порядок ребер вокруг каждой вершины по часовой стрелке был таким же, как порядок по часовой стрелке, заданный σ.

Характеристика поверхности заделки

По формуле Эйлера мы можем вывести род g замкнутой ориентируемой поверхности, определяемой системой вращения $(\sigma ,\theta )$ (то есть поверхность, на которую встроен двухклеточный мультиграф). ^[6] Обратите внимание, что $V=|Z(\sigma )|$ , $E=|Z(\theta )|$ и $F=|Z(\sigma \theta )|$ . Мы находим это

g=1-{\frac {1}{2}}(V-E+F)=1-{\frac {1}{2}}(|Z(\sigma )|-|Z(\theta )|+|Z(\sigma \theta )|)

где $Z(\phi )$ обозначает множество орбит перестановки $\phi$ .

См. также

Комбинаторная карта

Примечания

^ Хеффтер (1891) , Хеффтер (1898)
^ Рингель (1965)
^ Эдмондс (1960a) , Эдмондс (1960b)
^ Янгс (1963)
^ Гросс и Альперт (1974)
^ Lando & Zvonkin (2004) , formula 1.3, p. 38.

Ссылки

Кори, Р.; Мачи, А. (1992). «Карты, гиперкарты и их автоморфизмы: обзор». Математические изложения . 10 : 403–467. МР 1190182
Эдмондс, Дж. (1960a). «Комбинаторное представление многогранных поверхностей». Уведомления Американского математического общества . 7 :646.
Эдмондс, Джон Роберт (1960b). Комбинаторное представление ориентированных многогранных поверхностей (PDF) (Магистратура). Университет Мэриленда. hdl : 1903/24820 .
Гросс, Дж.Л.; Альперт, СР (1974). «Топологическая теория графов тока» . Журнал комбинаторной теории, серия B. 17 (3): 218–233. дои : 10.1016/0095-8956(74)90028-8 . МР 0363971 .
Хеффтер, Л. (1891). «О проблеме соседних территорий» . Математические летописи . 38 (4): 477–508. дои : 10.1007/BF01203357 . S2CID 121206491 .
Хеффтер, Л. (1898). «О метациклических группах и соседних конфигурациях» . Математические летописи . 50 (2–3): 261–268. дои : 10.1007/BF01448067 . S2CID 120691296 .
Ландо, Сергей К.; Звонкин, Александр К. (2004). Графы на поверхностях и их применении . Энциклопедия математических наук: низкомерная топология II. Том. 141. Шпрингер-Верлаг . ISBN 978-3-540-00203-1 . .
Мохар, Боян ; Томассен, Карстен (2001). Графы на поверхностях . Издательство Университета Джонса Хопкинса. ISBN 0-8018-6689-8 .
Рейнгольд, О.; Вадхан, С.; Вигдерсон, А. (2002). «Волны энтропии, произведение зигзагообразного графа и новые расширители постоянной степени». Анналы математики . 155 (1): 157–187. arXiv : math/0406038 . дои : 10.2307/3062153 . JSTOR 3062153 . МР 1888797 . S2CID 120739405 .
Рингель, Г. (1965). «Пол полного парного графа». Трактаты математического семинара в Гамбургском университете . 28 (3–4): 139–150. дои : 10.1007/BF02993245 . MR0189012 . S2CID 120414651 .
Янгс, JWT (1963). «Минимальные вложения и род графа» . Журнал математики и механики . 12 (2): 303–315. дои : 10.1512/iumj.1963.12.12021 . МР 0145512 .

[1] Хеффтер (1891) , Хеффтер (1898)

[2] Рингель (1965)

[3] Эдмондс (1960a) , Эдмондс (1960b)

[4] Янгс (1963)

[5] Гросс и Альперт (1974)

[6] Lando & Zvonkin (2004) , formula 1.3, p. 38.

[1]

[2]

[3]

[4]

[5]

[6]