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

Граф, где каждое ребро находится в одном треугольнике

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

В теории графов локально линейный граф — это неориентированный граф , в котором каждое ребро принадлежит ровно одному треугольнику. Эквивалентно, для каждой вершины графа ее соседи смежны ровно с одним другим соседом, поэтому соседи могут быть объединены в пары в индуцированное паросочетание . ^[1] Локально линейные графы также называются локально согласованными графами. ^[2] Их треугольники образуют гиперребра 3-однородных линейных гиперграфов без треугольников и блоков некоторых частичных систем троек Штейнера , а локально линейные графы — это в точности графы Гайфмана этих гиперграфов или частичных систем Штейнера.

Известно много конструкций для локально линейных графов. Примерами локально линейных графов являются треугольные кактусовые графы , линейные графы 3-регулярных графов без треугольников и декартовы произведения меньших локально линейных графов. Некоторые графы Кнезера и некоторые сильно регулярные графы также являются локально линейными.

Вопрос о том, сколько ребер могут иметь локально линейные графы, является одной из формулировок проблемы Ружи–Семереди . Хотя плотные графы могут иметь число ребер, пропорциональное квадрату числа вершин, локально линейные графы имеют меньшее число ребер, отставая от квадрата по крайней мере на небольшой непостоянный множитель. Также известны самые плотные планарные графы , которые могут быть локально линейными. Наименее плотные локально линейные графы — это треугольные кактусовые графы.

Конструкции

Склеивание и изделия

Графики дружбы

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

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

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

Из меньших графиков

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

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

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

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

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

Локально линейные графы также могут быть построены из множеств чисел, свободных от прогрессий. Пусть будет простым числом, и пусть будет подмножеством чисел по модулю таким образом, что никакие три члена из не образуют арифметическую прогрессию по модулю . (То есть, является множеством Салема–Спенсера по модулю .) Это множество можно использовать для построения трехдольного графа с вершинами и ребрами, который является локально линейным. Чтобы построить этот граф, создайте три множества вершин, каждое из которых пронумеровано от до . Для каждого числа в диапазоне от до и каждого элемента из постройте треугольник, соединяющий вершину с номером в первом множестве вершин, вершину с номером во втором множестве вершин и вершину с номером в третьем множестве вершин. Сформируйте граф как объединение всех этих треугольников. Поскольку это объединение треугольников, каждое ребро полученного графа принадлежит треугольнику. Однако не может быть никаких других треугольников, кроме образованных таким образом. Любой другой треугольник имел бы вершины, пронумерованные так , что , и все принадлежат , что нарушает предположение об отсутствии арифметических прогрессий в . ^[9] Например, при и результатом этого построения является граф Пейли с девятью вершинами. ${\displaystyle p}$ ${\displaystyle A}$ ${\displaystyle p}$ ${\displaystyle A}$ ${\displaystyle p}$ ${\displaystyle A}$ ${\displaystyle p}$ ${\displaystyle 3p}$ ${\displaystyle 3p\cdot |A|}$ ${\displaystyle 0}$ ${\displaystyle p-1}$ ${\displaystyle x}$ ${\displaystyle 0}$ ${\displaystyle p-1}$ ${\displaystyle a}$ ${\displaystyle A}$ ${\displaystyle x}$ ${\displaystyle x+a}$ ${\displaystyle x+2a}$ ${\displaystyle (x,x+a,x+a+b)}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c=(a+b)/2}$ ${\displaystyle A}$ ${\displaystyle (a,c,b)}$ ${\displaystyle A}$ ${\displaystyle p=3}$ ${\displaystyle A=\{\pm 1\}}$

Треугольники в локально линейном графе можно эквивалентно рассматривать как образующие 3-однородный гиперграф . Такой гиперграф должен быть линейным, что означает, что никакие два его гиперребра (треугольники) не могут иметь более одной общей вершины. Сам локально линейный граф является графом Гайфмана гиперграфа, графом пар вершин, принадлежащих общему гиперребру. С этой точки зрения имеет смысл говорить об обхвате гиперграфа. В терминах графа это длина кратчайшего цикла, который не является одним из треугольников графа. Алгебраическая конструкция, основанная на графах полярности (также называемых графами Брауна), использовалась в этом контексте для поиска плотных локально линейных графов, которые не имеют 4-циклов; обхват их гиперграфа равен пяти. Граф полярности определяется из конечной проективной плоскости , а полярность — сохраняющей инцидентность биекции между ее точками и ее линиями. Вершины графа полярности являются точками, а ребро соединяет две точки, когда одна из них является полярной, с линией, содержащей другую. Более алгебраически, вершины одного и того же графа могут быть представлены однородными координатами : это тройки значений из конечного поля , не все из которых равны нулю, где две тройки определяют одну и ту же точку на плоскости, когда они являются скалярными кратными друг другу. Две точки, представленные тройками таким образом, являются смежными, когда их скалярное произведение равно нулю. Граф полярности для конечного поля нечетного порядка имеет вершины, из которых являются самосмежными и не принадлежат никаким треугольникам. Когда они удаляются, результатом является локально линейный граф с вершинами, ребрами и обхватом гиперграфа пятью, что дает максимально возможное количество ребер для локально линейного графа этого обхвата с точностью до членов низшего порядка. ^[10] ${\displaystyle (x,y,z)}$ ${\displaystyle q}$ ${\displaystyle q^{2}+q+1}$ ${\displaystyle q+1}$ ${\displaystyle q^{2}}$ ${\displaystyle {\bigl (}{\tfrac {1}{2}}+o(1){\bigr )}q^{3}}$

Регулярность

Регулярные графы с небольшим количеством вершин

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

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

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

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

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

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

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

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

Дистанционно-регулярные графы

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

Плотность

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

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

Среди планарных графов максимальное число ребер в локально линейном графе с вершинами равно . Граф кубооктаэдра является первым в бесконечной последовательности многогранных графов с вершинами и ребрами, для , построенных путем расширения четырехугольных граней в антипризмы. Эти примеры показывают, что верхняя граница может быть достигнута. ^[5] ${\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}}$ ${\displaystyle {\tfrac {12}{5}}(n-2)}$

Каждый локально линейный граф обладает свойством, что он остается связным после того, как из него удаляется любое сопоставление, потому что в любом пути через граф каждое сопоставленное ребро может быть заменено двумя другими ребрами его треугольника. Среди графов с этим свойством наименее плотными являются треугольные кактусовые графы, которые также являются наименее плотными локально линейными графами. ^[4]

Приложения

Одно из применений локально линейных графов происходит в формулировке диаграмм Гричи, которые используются в квантовой логике для определения того, могут ли некоторые уравнения гильбертова пространства быть выведены друг из друга. В этом применении треугольники локально линейных графов образуют блоки диаграмм Гричи с размером блока три. Диаграммы Гричи, соответствующие решеткам, происходят из локально линейных графов с обхватом гиперграфа пять или более, ^[18], как построено, например, из графов полярности. ^[10]

Комбинация случайной выборки и леммы удаления графа может быть использована для поиска больших 3-однородных гиперграфов с высоким обхватом в произвольных 3-однородных линейных гиперграфах или частичных системах троек Штейнера. Этот метод затем может быть использован для доказательства асимптотически точных нижних границ числа независимости 3-однородных линейных гиперграфов и частичных систем троек Штейнера. ^[19]

Ссылки

1. Фрончек, Далибор (1989), «Локально линейные графы», Mathematica Slovaca , 39 (1): 3–6, hdl : 10338.dmlcz/136481 , MR  1016323
2. Ларрион, Ф.; Пизанья, Массачусетс; Вильярроэль-Флорес, Р. (2011), «Малые локально графы nK2» (PDF) , Ars Combinatoria , 102 : 385–391, MR  2867738
3. Эрдеш, Пол ; Реньи, Альфред ; Сос, Вера Т. (1966), «Об одной задаче теории графов» (PDF) , Studia Sci. Математика. Венгрия. , 1 : 215–235
4. Farley, Arthur M.; Proskurowski, Andrzej (1982), «Сети, устойчивые к отказам отдельных линий», Networks , 12 (4): 393–403, doi :10.1002/net.3230120404, MR  0686540; см. в частности стр. 397: «Мы называем полученную сеть треугольным кактусом; это сеть кактусов, в которой каждая линия принадлежит ровно одному треугольнику».
5. Зелинка, Богдан (1988), "Политопические локально линейные графы", Mathematica Slovaca , 38 (2): 99–103, hdl : 10338.dmlcz/133017 , MR  0945363
6. Девиллерс, Алиса; Цзинь, Вэй; Ли, Цай Хэн; Прегер, Шерил Э. (2013), «Локальная 2-геодезическая транзитивность и кликовые графы», Журнал комбинаторной теории , Серия A, 120 (2): 500–508, doi : 10.1016/j.jcta.2012.10.004 , MR  2995054. В обозначениях этой ссылки семейство -регулярных графов обозначается как . ${\displaystyle 2r}$ ${\displaystyle F(r,2)}$
7. Мунаро, Андреа (2017), «О линейных графиках субкубических графов без треугольников», Дискретная математика , 340 (6): 1210–1226, doi : 10.1016/j.disc.2017.01.006 , MR  3624607
8. Фань, Конг (1996), «Об обобщенных клетках», Журнал теории графов , 23 (1): 21–31, doi :10.1002/(SICI)1097-0118(199609)23:1<21::AID-JGT2>3.0.CO;2-M, MR  1402135
9. Ружа, Издательство ; Семереди, Э. (1978), «Тройные системы без шести точек, несущих три треугольника», Комбинаторика (Труды пятого венгерского коллоквиума, Кестхей, 1976), Vol. II , коллок. Математика. Соц. Янош Бояи, том. 18, Амстердам и Нью-Йорк: Северная Голландия, стр. 939–945, MR  0519318.
10. Lazebnik, Felix; Verstraëte, Jacques (2003), "О гиперграфах обхвата пять", Electronic Journal of Combinatorics , 10 : R25:1–R25:15, doi : 10.37236/1718 , MR  2014512
11. Махнёв, АА (1988), "Сильно регулярные графы с ", Академия наук СССР , 44 (5): 667–672, 702, doi :10.1007/BF01158426, MR  0980587, S2CID  120911900 ${\displaystyle \lambda =1}$
12. Брауэр, AE ; Хемерс, WH (1992), «Структура и уникальность сильно регулярного графа (81,20,1,6)», Сборник статей в честь Джека ван Линта, Дискретная математика , 106/107: 77–82, doi :10.1016/0012-365X(92)90532-K, MR  1181899
13. Берлекамп, Э. Р .; ван Линт, Дж. Х .; Зайдель, Дж. Дж. (1973), «Строго регулярный граф, полученный из совершенного троичного кода Голея», Обзор комбинаторной теории (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) , Амстердам: Северная Голландия: 25–30, doi : 10.1016/B978-0-7204-2262-7.50008-9, ISBN 9780720422627, МР  0364015
14. Коссиденте, Антонио; Пенттила, Тим (2005), «Гемисистемы на эрмитовой поверхности», Журнал Лондонского математического общества , Вторая серия, 72 (3): 731–741, doi :10.1112/S0024610705006964, MR  2190334
15. Бондаренко, Андрей В.; Радченко, Данил В. (2013), «О семействе сильно регулярных графов с », Журнал комбинаторной теории , Серия B, 103 (4): 521–531, arXiv : 1201.0383 , doi : 10.1016/j.jctb.2013.05.005, MR  3071380 ${\displaystyle \lambda =1}$
16. Зехави, Саар; Оливейра, Иво Фагундес Давид (2017), Не проблема Конвея с 99 графами , arXiv : 1707.08047
17. Хираки, Акира; Номура, Казумаса; Судзуки, Хироси (2000), «Дистанционно-регулярные графы валентности 6 и », Журнал алгебраической комбинаторики , 11 (2): 101–134, doi : 10.1023/A:1008776031839 , MR  1761910 ${\displaystyle a_{1}=1}$
18. Маккей, Брендан Д .; Мегилл, Норман Д.; Павичич, Младен (2000), «Алгоритмы для диаграмм Гречи», Международный журнал теоретической физики , 39 (10): 2381–2406, arXiv : quant-ph/0009039 , doi :10.1023/A:1026476701774, MR  1803695
19. Хеннинг, Майкл А.; Йео, Андерс (2020), «Глава 12: Частичные тройные системы Штейнера», Трансверсали в линейных однородных гиперграфах , Развитие математики, т. 63, Cham: Springer, стр. 171–177, doi : 10.1007/978-3-030-46559-9_12, ISBN 978-3-030-46559-9, МР  4180641