Локально линейный граф

Локально линейный граф — неориентированный граф в окрестности каждой вершины порождённым паросочетанием^[en]. То есть для любой вершины ${\displaystyle v}$ любая окрестность ${\displaystyle v}$ должна быть смежной в точности ещё одной вершине, соседней вершине ${\displaystyle v}$. Эквивалентно, любое ребро ${\displaystyle uv}$ такого графа принадлежит единственному треугольнику ${\displaystyle uvw}$^[1]. Локально линейные графы называются также локально паросочетаемыми графами^[2].

Примеры локально линейных графов включают треугольные кактусы, рёберные графы 3-регулярных графов без треугольников и прямое произведение более мелких локально линейных графов. Определённые кнезеровские графы, и некоторые сильно регулярные графы также локально линейны.

Некоторые локально линейные графы имеют почти квадратичное число рёбер. Вопрос, как плотны эти графы, может быть одной из формулировок Проблема Ружи – Семереди. Известны также наиболее плотные планарные графы, которые могут быть локально линейными.

Построения и примеры

Известны некоторые построения для локально линейных графов.

Приклеивания и произведения

Графы дружеских отношений, образованные склеиванием вместе набора треугольников в одной общей вершине, локально линейны. Это единственные конечные графы, имеющие более сильное свойство, что любая пара вершин (смежных или нет) имеют в точности одну общую соседнюю вершину^[3]. Более обще, любой треугольный кактус, граф, в котором все простые циклы треугольны и все пары простых циклов имеют максимум одну общую вершину, локально линейны.

Пусть ${\displaystyle G}$ и ${\displaystyle H}$ будут любыми двумя локально линейными графами, выберем треугольник из каждого из графов и склеим два графа вместе путём отождествления пар в этих треугольниках (это вид операции суммы по клике на графах). Тогда результирующий граф остаётся локально линейным^[4].

Прямое произведение графов любых двух локально линейных графов остаётся линейно локальным, поскольку любые треугольники в произведении приходят из одного или другого множителя. Например, Граф Пэли с девятью вершинами (граф 3-3 дуопризмы) является прямым произведением двух треугольников^[1]. Графы Хэмминга ${\displaystyle H(d,3)}$ являются произведениями ${\displaystyle d}$ треугольников, а потому снова локально линейны^[5].

Размножение

Если граф ${\displaystyle G}$ является 3-регулярным графом без треугольников, то рёберный граф ${\displaystyle L(G)}$ является графом, образованным путём преобразования каждого ребра графа ${\displaystyle G}$ в новую вершину и связыванием двух вершин ребром в ${\displaystyle L(G)}$, если соответствующие рёбра графа ${\displaystyle G}$ имеют общую конечную вершину. Эти графы являются 4-регулярными и локально линейными. Любой 4-регулярный локально линейный граф может быть построен таким образом^[6]. Например, граф кубооктаэдра может быть образован этим способом как рёберный граф куба, а граф Пэли с девятью вершинами является рёберным графом коммунального графа ${\displaystyle K_{3,3}}$. Рёберный граф графа Петерсена, другой граф этого типа, имеет свойство, аналогичное свойству клеток, что это наименьший возможный граф, в котором наибольшая клика имеет три вершины, каждая вершина принадлежит двум непересекающимся кликам, а самый короткий цикл с рёбрами из различных клик имеет длину пять^[7].

Более сложный процесс размножения применяется к планарным графам. Пусть ${\displaystyle G}$ будет планарным графом, вложенным в плоскость таким образом, что каждая грань четырёхугольна, как у графа куба. Необходимо, если ${\displaystyle G}$ имеет ${\displaystyle n}$ вершин, чтобы грань имел ${\displaystyle n-2}$ графов. Если вклеить квадратную антипризму в грань графа ${\displaystyle G}$, а затем удалить оригинальные рёбра графа ${\displaystyle G}$, получим новый локально линейный планарный граф с ${\displaystyle 5(n-2)+2}$ вершинами и ${\displaystyle 12(n-2)}$ рёбрами^[4]. Например, кубооктаэдр может быть получен таким образом из двух граней (внутренняя и внешняя) 4-цикла.

Алгебраическое посторение

Кнезеровский граф ${\displaystyle KG_{a,b}}$ имеет ${\displaystyle {\tbinom {a}{b}}}$ вершин, представляющий ${\displaystyle b}$-элементные подмножества ${\displaystyle a}$-элементного множества. Две вершины смежны, если соответствующие подмножества не пересекаются. Когда ${\displaystyle a=3b}$, результирующий граф локально линеен, поскольку для каждых двух не пересекающихся ${\displaystyle b}$-элементных подмножеств имеется в точности одно ${\displaystyle b}$-элементное подмножество (дополнение их объединения), которое не пересекается с обоими множествами. Получающийся локально линейный граф имеет ${\displaystyle {\tbinom {3b}{b}}}$ вершин и ${\displaystyle {\tfrac {1}{2}}{\tbinom {3b}{b}}{\tbinom {2b}{b}}}$ рёбер. Например, для ${\displaystyle b=2}$ кнезеровский граф ${\displaystyle KG_{6,2}}$ локально линеен с 15 вершинами и 45 рёбрами^[2].

Локально линейные графы могут также быть построены из свободных от прогрессий множеств чисел. Пусть ${\displaystyle p}$ будет простым числом и пусть ${\displaystyle A}$ будет подмножеством чисел по модулю ${\displaystyle p}$, таких, что никакие три члена ${\displaystyle A}$ не формируют арифметическую прогрессию по модулю ${\displaystyle p}$. (То есть ${\displaystyle A}$ является множеством Салема — Спенсера^[en] по модулю ${\displaystyle p}$.) Тогда существует трёхдольный граф, в котором каждая доля имеет ${\displaystyle p}$ вершин, имеет ${\displaystyle 3|A|p}$ рёбер и каждое ребро принадлежит единственному треугольнику. Тогда, согласно этому построению, ${\displaystyle n=3p}$ и число рёбер равно ${\displaystyle n^{2}/e^{O({\sqrt {\log n}})}}$. Для построения этого графа, пронумеруем вершины на каждой стороне трёхдольного графа от ${\displaystyle 0}$ до ${\displaystyle p-1}$ и строим треугольнике вида ${\displaystyle (x,x+a,x+2a)}$ по модулю ${\displaystyle p}$ для каждого ${\displaystyle x}$ в интервале от ${\displaystyle 0}$ до ${\displaystyle p-1}$ и каждого ${\displaystyle a}$ из ${\displaystyle A}$. Граф, образованный объединением этих треугольников, имеет ожидаемое свойство, что любое ребро принадлежит единственному треугольнику. Если бы это было не так, существовал бы треугольник ${\displaystyle (x,x+a,x+a+b)}$, где ${\displaystyle a}$, ${\displaystyle b}$ и ${\displaystyle c=(a+b)/2}$ принадлежали бы ${\displaystyle A}$, что нарушает предположение об отсутствии арифметических прогрессий ${\displaystyle (a,c,b)}$ в ${\displaystyle A}$.^[8] Например, с ${\displaystyle p=3}$ и ${\displaystyle A=\{\pm 1\}}$, результатом будет Граф Пэли с девятью вершинами.

Регулярные и сильно регулярные графы

Любой локально линейный граф должен иметь чётную степень для каждой вершины, поскольку ребро в каждой вершине может быть разбито на пары на треугольники. Прямое произведение двух локально линейных регулярных графов снова локально линейно и регулярно со степенью, равной сумме степеней множителей. Таким образом, существует регулярные локально линейные графы любой чётной степени^[1]. ${\displaystyle 2r}$-Регулярные локально линейные графы должны иметь по меньшей мере ${\displaystyle 6r-3}$ вершин, поскольку столько есть в треугольниках и соседях. (Никакие две вершины треугольника не могут иметь общих соседей без нарушения локальной линейности.) Регулярные графы с точно таким числом вершин возможны, только когда ${\displaystyle r}$ равно 1, 2, 3 или 5 и единственным образом определены для каждого из этих четырёх случаев. Четыре регулярных графа, на которых достигается эта граница как функция от числа вершин, — это 2-регулярный треугольник ${\displaystyle K_{3}}$ (3 вершины), 4-регулярный граф Пэли (9 вершин), 6-регулярный кнезеровский граф ${\displaystyle KG_{6,2}}$ (15 вершин) и 10-регулярное дополнение графа Шлефли (27 вершин). Последний в списке 10-регулярный граф с 27 вершинами также является графом пересечений 27 прямых на кубической поверхности^[2].

Сильно регулярный граф можно описать четвёркой параметров ${\displaystyle (n,k,\lambda ,\mu )}$, где ${\displaystyle n}$ равно числу вершин, ${\displaystyle k}$ равно числу инцидентных вершине рёбер, ${\displaystyle \lambda }$ равна числу общих соседей для любой смежной пары вершин и ${\displaystyle \mu }$ равно числу общих соседей для любой несмежной пары вершин. Когда ${\displaystyle \lambda =1}$, граф локально линеен. Локально линейные графы, как уже упомянуто выше, сильно регулярны и их параметры равны

• треугольник (3,2,1,0),
• граф Пэли с девятью вершинами (9,4,1,2),
• кнезеровский граф ${\displaystyle KG_{6,2}}$ (15,6,1,3),
• дополнение графа Шлефли (27,10,1,5).

Другие локально линейные строго регулярные графы

• граф Брауэра — Хемерса (81,20,1,6)^[9]
• граф Берлекэмпа — ван Линта — Зейделя (243,22,1,2)^[10]
• Граф Коссиденте — Пенттилы (378,52,1,8),^[11]
• граф Геймса (729,112,1,20).^[12]

Другие потенциально правильные комбинации с ${\displaystyle \lambda =1}$ включают (99,14,1,2) и (115,18,1,3), но не известно, существуют ли сильно регулярные графы с такими параметрами^[13]. Вопрос о существовании сильно регулярного графа с параметрами (99,14,1,2) известен как проблема Конвея 99-графа и Джон Хортон Конвей предложил приз в 1000 долларов тому, кто её решит ^[14].

Существует бесконечно много дистанционно-регулярных графов степени 4 или 6, которые локально линейно. Кроме сильно регулярных графов одинаковой степени, они включают рёберный граф графа Петерсена, граф Хэмминга ${\displaystyle H(3,3)}$ и половинку^[en] графа Фостера^[15].

Плотность

Одна из формулировок проблемы Ружи – Семереди задаёт вопрос о максимальном числе рёбер в локально линейном графе с ${\displaystyle n}$ вершинами. Как доказали Имре З. Ружа и Эндре Семереди, это максимальное число равно ${\displaystyle o(n^{2})}$, но также равно ${\displaystyle \Omega (n^{2-\varepsilon })}$ для любого ${\displaystyle \varepsilon >0}$. Построение локально линейных графов из свободных от прогрессий множеств ведёт к наиболее плотным известным локально линейным графам с ${\displaystyle n^{2}/\exp O({\sqrt {\log n}})}$ рёбрами^[8].

Среди планарных графов максимальное число рёбер в локально линейном графе с ${\displaystyle n}$ вершинами равно ${\displaystyle {\tfrac {12}{5}}(n-2)}$. Граф кубооктаэдра является первым в бесконечной последовательности полиэдральных графов с ${\displaystyle n=5k+2}$ вершинами и ${\displaystyle {\tfrac {12}{5}}(n-2)=12k}$ рёбрами для ${\displaystyle k=2,3,\dots }$, построенными путём расширения квадратных граней ${\displaystyle K_{2,k}}$ в антипризмы. Эти примеры показывают, что эта верхняя граница точна^[4].

Примечания

Эта страница в последний раз была отредактирована 11 мая 2023 в 13:02.