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

Граф Пэли с девятью вершинами является локально линейным. Один из шести треугольников выделен зелёным.

Локально линейный граф — неориентированный граф в окрестности каждой вершины порождённым паросочетанием. То есть для любой вершины $v$ любая окрестность $v$ должна быть смежной в точности ещё одной вершине, соседней вершине $v$. Эквивалентно, любое ребро $uv$ такого графа принадлежит единственному треугольнику $uvw$. Локально линейные графы называются также локально паросочетаемыми графами.

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

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

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

Кубооктаэдр, планарный локально линейный граф, который может быть образован как рёберный граф куба или путём приклеивания антипризм во внутреннюю и внешнюю грань 4-цикла

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

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

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

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

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

Размножение

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

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

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

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

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

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

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

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

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

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

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

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

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

Плотность

Наиболее плотные возможные локально линейные планарные графы образованы путём вклеивания антипризмы (красные вершины и чёрные рёбра) в каждую квадратную грань планарного графа (синие вершины и пунктирные жёлтые рёбра)

Основная статья: Проблема Ружи – Семереди

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

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