Комбинаторная теория групп - Линдон Р.
Скачать (прямая ссылка):
Пусть р и q—натуральные числа, такие, что \/p+l/q = 1/2. Хорошо известно, что единственные натуральные решения суть (3, 6), (4, 4) и (6, 3). В наших рассмотрениях возникает два типа карт. Если M — непустая карта, все внутренние вершины которой имеют степень не менее р, а все области имеют степень не менее q, то она будет называться [р, а\-картой. Если M — непустая карта, все внутренние вершины которой имеют степень не менее р, а все внутренние области имеют степень не менее q, то она будет называться (р, q)-картой.
Знаки суммирования 2 будут означать суммирование по вершинам или областям карты М. Таким образом, 2^(°) есть сумма степеней всех вершин карты М, a ^d (D)— сумма степеней всех областей карты М. Обозначение 2' будет употребляться для суммирования по граничным вершинам или областям, а 2° — суммирование по внутренним областям или вершинам. Таким образом, 2'd(v) — сумма степеней всех граничных вершин карты М, а 2? (D)— сумма степеней всех внутренних областей. В случае необходимости будет добавляться индекс, именующий карту, о которой идет речь.
Пусть M — произвольная карта. Тогда V будет означать число вершин карты М. (Мы будем избегать использования индексов для обозначения карты, если только речь не будет идти о более чем одной карте.) Число неориентированных ребер карты M будет обозначаться буквой Е, а число областей этой карты — буквой F. Символ V обозначает число граничных вершин карты М, F' — число граничных областей и E' — число граничных ребер с учетом кратности. Если M связна и односвязна, то E' — число ребер в граничном цикле для М. Чтобы получить E' в общем случае, нужно сложить числа ребер в циклах, необходимых для описания границы карты М. Заметим, что, возможно, имеет место Е>Е. Пусть Q — число компонент карты M и h — число дырок (т. е. число ограни-ченных компонент дополнения к M) этой карты. Допустим, что и q — натуральные числа, такие, что \lp-\-\lq=\l2.
Следующие формулы лягут в основу наших рассмотрений.
Теорема 3.1. Пусть M — произвольная карта. Тогда (3.1)
P(Q-h)^[p-d(v)] + ^[p-d(v)] + ^[q-d(D)]-J f
3. основные формулы 32?
(3.2) P(Q-A) = ?- [f+ 2-d(«)]+?°[/>-d(i;)] +
+ f I>-<*(0>]+f (V-E-).
р Используем формулу Эйлера \ = V—E+F для связного графа Г (неограниченные области при делении плоскости графом Г в учет не принимаются). Пусть Г есть 1-скелет карты М. Суммируя по связным компонентам, возможно, несвязного графа, получим Q= ^V-E+F.
Верны следующие равенства:
(1) (Q-h) = V-E + F.
(2) 2Е = ^d(v). (Сумма степеней вершин учитывает каждое ребро дважды.)
(3) 2E = ^d (D)+ E'.
Пусть « — положительное действительное число. Исключим E из приведенных выше равенств.
(I') 2(n+l)(Q-h) = 2(n + l)V-2(n+l)E + 2(n+l)F, (2') 2E = %d(v),
(У) 2nE = nJ\d(D) + nE\
Используя (2') и (3'), получаем из (Г)
(4) 2(n + l)(Q-h) = 2(n+l)V-%d(v) +
+ 2(п+ї) F-n^d(D)-пЕ\
Поскольку V — число вершин, a F- число областей, имеем
(5) 2(n+\)(Q-h) = ^[2(n+\)~d(v)] +
+ nZ[^-d(D)]-nE-.
Суммируя отдельно по граничным и внутренним вершинам, получаем
(6) 2(n+l)(Q-h) = yi-[2(n+\)-d(v)] +
+ ^[2(n+\)-d(v)] + n^[^±^-d(D)]-nE\
Пусть /7=2 (я-f 1) и 9=2 (п + 1)/м. Тогда /г=/?А/, 1//7+1/7=1/2 и (/7 + 2)/2 = /7/^ + 2.
В этом случае (6) можно переписать в виде
(7) /7 (Q - h) = 2- [/> - d (и)] + 2° [P - d (V)] +
+ f E^~d(D)]-?.?-.
Это и есть формула (3.1). Нам нужно расщепить первую сумму в (6). Если мы суммируем п по граничным вершинам, то 2' п =
¦
328
Pл. V. Теория малых сокращений
= nV- = (p/q) V'. Поэтому
(8) р (Q -h) = 2- [п + 2 - d (V)] + 2"п + S° [Р -d (V)] +
(9) p(Q-h) = ? [?- + 2-d{v)]+?\p-d{v)] +
Получили формулу (3.2). ?
Перед выводом некоторых следствий теоремы 3.1 рассмотрим дуальные карты.
Дуальная карта М* для данной карты M строится следующим образом. Выберем точку vi в каждой области D1 карты М. Набор точек и} есть множество вершин карты М*. Если D1 и D2 — области из М, такие, что D1=T=D2, но у D1 и D2 есть общее ребро е, проведем ребро е* из V* в vi, пересекая е, но не пересекая другие ребра карты M или уже построенные ранее ребра карты М*. Поскольку ^dD1 П DoD2, ребро е внутреннее для М. Кроме того, если в области D карты M имеется ребро е, такое, что D лежит по обе стороны этого ребра, то рисуем петлю с вершиной в v\, пересекающую е, но не пересекающую другие ребра. Вершины и ребра множества М* образуют граф Г*. Области карты М* определяются как области, ограниченные графом Г* и содержащие внутренние вершины карты М.
Эта конструкция совпадает с обычной конструкцией дуального графа для некоторого плоского графа, если не считать того, что граничные ребра для M не принимаются во внимание. То же построение может быть проделано иначе. Рассмотрим 1-скелет Г карты М, делящий плоскость на различные области (в том числе и неограниченные). Построим дуальный граф Г*. Вычеркнем вершины и любые содержащие их ребра, которые соответствуют областям, не являющимся областями карты М. Получится М*.
Мы видим, что М* обладает следующими свойствами:
(1) Вершины V* карты М* находятся во взаимно однозначном соответствии с областями D карты М, причем v* ?D. Если v* соответствует области D, то, поскольку одно ребро проводится из V* через каждое внутреннее ребро границы d(D), имеем d(v*)=i(D).
