График Пейли

В математике графы Пейли — это неориентированные графы, построенные из членов подходящего конечного поля путем соединения пар элементов, отличающихся квадратичным вычетом . Графы Пейли образуют бесконечное семейство конференц-графов , которые дают бесконечное семейство симметричных конференц-матриц . Графы Пейли позволяют применять инструменты теории графов к теории чисел квадратичных вычетов и обладают интересными свойствами, которые делают их полезными в теории графов в более общем плане.

Графы Пейли названы в честь Рэймонда Пейли . Они тесно связаны с конструкцией Пейли для построения матриц Адамара из квадратичных вычетов. ^[1] Они были введены как графы независимо Саксом (1962) и Эрдёшем и Реньи (1963). Сакс интересовался ими из-за их свойств самодополнения, ^[2] в то время как Эрдёш и Реньи изучали их симметрии. ^[3]

Орграфы Пейли являются направленными аналогами графов Пейли, которые дают антисимметричные матрицы конференций . Они были введены Грэмом и Спенсером (1971) (независимо от Сакса, Эрдёша и Реньи) как способ построения турниров со свойством, которое, как ранее было известно, было присуще только случайным турнирам: в орграфе Пейли каждое небольшое подмножество вершин доминируется некоторой другой вершиной. ^[4]

Определение

Пусть q будет степенью простого числа , такой что q = 1 (mod 4). То есть, q должно быть либо произвольной степенью пифагорейского простого числа (простого числа, сравнимого с 1 mod 4), либо четной степенью нечетного непифагорейского простого числа. Такой выбор q подразумевает, что в единственном конечном поле F _q порядка q элемент −1 имеет квадратный корень.

Теперь пусть V = F _q и пусть

E=\left\{\{a,b\}\ :\ ab\in (\mathbf {F} _{q}^{\times })^{2}\right\}

Если пара { a , b } включена в E , она включена в любой порядок ее двух элементов. Так как a − b = −( b − a ), а −1 является квадратом, из чего следует, что a − b является квадратом тогда и только тогда, когда b − a является квадратом.

По определению G = ( V , E ) — граф Пейли порядка q .

Пример

Для q = 13 поле F _q представляет собой просто целочисленную арифметику по модулю 13. Числа с квадратными корнями по модулю 13:

±1 (квадратные корни ±1 для +1, ±5 для −1)
±3 (квадратные корни ±4 для +3, ±6 для −3)
±4 (квадратные корни ±2 для +4, ±3 для −4).

Таким образом, в графе Пейли мы формируем вершину для каждого из целых чисел в диапазоне [0,12] и соединяем каждое такое целое число x с шестью соседями: x ± 1 (mod 13), x ± 3 (mod 13) и x ± 4 (mod 13).

Характеристики

Графы Пейли самодополняемы : дополнение любого графа Пейли изоморфно ему. Один изоморфизм осуществляется через отображение, которое переводит вершину $x$ в $xk (mod q)$ , где $k$ — любой невычет $mod q$ . ^[2]

Графы Пейли — это строго регулярные графы с параметрами

srg\left(q,{\tfrac {1}{2}}(q-1),{\tfrac {1}{4}}(q-5),{\tfrac {1}{4}}(q-1)\right).

Это фактически следует из того факта, что граф является реберно-транзитивным и самодополнительным. Сильно регулярные графы с параметрами этого вида (для произвольного $q$ ) называются графами конференций , поэтому графы Пейли образуют бесконечное семейство графов конференций. Матрица смежности графа конференций, такого как граф Пейли, может быть использована для построения матрицы конференций , и наоборот. Это матрицы, коэффициенты которых равны $\pm1$ , с нулем на диагонали, которые дают скалярное множитель единичной матрицы при умножении на их транспонирование. ^[5]

Собственные значения графов Пейли равны (с кратностью 1) и (оба с кратностью ). Их можно вычислить с помощью квадратичной суммы Гаусса или с помощью теории сильно регулярных графов. ^[6] ${\tfrac {1}{2}}(q-1)$ ${\tfrac {1}{2}}(-1\pm {\sqrt {q}})$ ${\tfrac {1}{2}}(q-1)$

Если $q$ — простое число, то изопериметрическое число $i (G)$ графа Пейли удовлетворяет следующим ограничениям:

\displaystyle {\frac {q-{\sqrt {q}}}{4}}\leq i(G)\leq {\frac {q-1}{4}}.

^[7]

Когда $q$ — простое число, соответствующий граф Пейли является гамильтоновым циркулянтным графом .

Графы Пейли являются квазислучайными : количество раз, которое каждый возможный граф постоянного порядка встречается как подграф графа Пейли, (в пределе для больших $q$ ) такое же, как и для случайных графов, а большие наборы вершин имеют приблизительно такое же количество ребер, как и в случайных графах. ^[8]

Граф Пейли порядка 9 является локально линейным графом , ладейным графом и графом дуопризмы 3-3 .
Граф Пейли порядка 13 имеет толщину книги 4 и номер очереди 3. ^[9]
Граф Пейли порядка 17 является единственным наибольшим графом G , таким что ни G , ни его дополнение не содержат полного подграфа с 4 вершинами. ^[10] Отсюда следует, что число Рамсея R (4, 4) = 18.
Граф Пейли порядка 101 в настоящее время является крупнейшим известным графом G, таким что ни G, ни его дополнение не содержат полного подграфа из 6 вершин.
Сасукара и др. (1993) используют графы Пейли для обобщения конструкции расслоения Хоррокса–Мамфорда . ^[11]

Пейли-диграфы

Пусть q — простая степень , такая что q = 3 (mod 4). Таким образом, конечное поле порядка q , F _q , не имеет квадратного корня из −1. Следовательно, для каждой пары ( a , b ) различных элементов F _q , либо a − b , либо b − a , но не оба, является квадратом. Орграф Пейли — это направленный граф с множеством вершин V = F _q и множеством дуг

A=\left\{(a,b)\in \mathbf {F} _{q}\times \mathbf {F} _{q}\ :\ ba\in (\mathbf {F} _{q}^{\times })^{2}\right\}.

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

Орграф Пейли приводит к построению некоторых антисимметричных конференц-матриц и биплоскостных геометрий .

Род

Шесть соседей каждой вершины в графе Пейли порядка 13 соединены в цикл; то есть граф локально цикличен . Следовательно, этот граф может быть вложен как триангуляция Уитни тора , в котором каждая грань является треугольником , а каждый треугольник является гранью. В более общем случае, если бы любой граф Пейли порядка q мог быть вложен так, чтобы все его грани были треугольниками, мы могли бы вычислить род результирующей поверхности с помощью характеристики Эйлера как . Боян Мохар предполагает, что минимальный род поверхности, в которую может быть вложен граф Пейли, близок к этой границе в случае, когда q является квадратом, и задается вопросом, может ли такая граница выполняться в более общем случае. В частности, Мохар предполагает, что графы Пейли квадратного порядка могут быть вложены в поверхности с родом ${\tfrac {1}{24}}(q^{2}-13q+24)$

(q^{2}-13q+24)\left({\tfrac {1}{24}}+o(1)\right),

где член o(1) может быть любой функцией q , которая стремится к нулю в пределе, когда q стремится к бесконечности. ^[12]

Уайт (2001) находит вложения графов Пейли порядка q ≡ 1 (mod 8), которые являются высокосимметричными и самодвойственными, обобщая естественное вложение графа Пейли порядка 9 как квадратную сетку 3×3 на торе. Однако род вложений Уайта примерно в три раза выше, чем предполагаемая граница Мохара. ^[13]

Ссылки

^ Paley, REAC (1933). «Об ортогональных матрицах». J. Math. Phys. 12 (1–4): 311–320. doi :10.1002/sapm1933121311.
^ аб Сакс, Хорст (1962). «Дополнительный графен». Публикации Mathematicae Дебрецен . 9 : 270–288. дои : 10.5486/PMD.1962.9.3-4.11 . МР 0151953.
^ Эрдеш, П .; Реньи, А. (1963). «Асимметричные графы». Acta Mathematica Academiae Scientiarum Hungaricae . 14 (3–4): 295–315. дои : 10.1007/BF01895716. МР 0156334.
^ Грэм, Р. Л .; Спенсер, Дж. Х. (1971). «Конструктивное решение турнирной задачи». Канадский математический бюллетень . 14 : 45–48. doi :10.4153/CMB-1971-007-1. MR 0292715.
^ Брауэр, А.Э.; Коэн, AM; Ноймайер, А. (1989). «Матрицы конференций и графики Пэли». Дистанционно-регулярные графы . Ergebnisse der Mathematik und ihrer Grenzgebiete. Том. 18. Берлин: Шпрингер-Верлаг. п. 10. дои : 10.1007/978-3-642-74341-2. ISBN 3-540-50619-5. МР 1002568.
^ Брауэр, Андрис Э.; Хемерс, Виллем Х. (2012). «9.1.2 Графы Пейли». Спектры графов . Universitext. Нью-Йорк: Springer. С. 114–115. doi :10.1007/978-1-4614-1939-6. ISBN 978-1-4614-1938-9. МР 2882891.Для получения спектра из сильной регулярности см. Теорему 9.1.3, стр. 116. Для связи с суммами Гаусса см. Раздел 9.8.5 Циклотомия, стр. 138–140.
^ Крамер, Кевин; Кребс, Майк; Шабази, Николь; Шахин, Энтони; Восканян, Эдвард (2016). «Изопериметрические константы и константы Каждана, связанные с графом Пейли». Involve . 9 (2): 293–306. doi :10.2140/involve.2016.9.293. MR 3470732.
^ Чунг, Фань Р. К .; Грэм, Рональд Л.; Уилсон, Р. М. (1989). «Квазислучайные графы». Combinatorica . 9 (4): 345–362. doi :10.1007/BF02125347.
^ Вольц, Джессика (2018). Проектирование линейных макетов с помощью SAT . Магистерская работа. Тюбингенский университет.
^ Эванс, Р. Дж.; Пулхэм, Дж. Р.; Шихан, Дж. (1981). «О числе полных подграфов, содержащихся в некоторых графах». Журнал комбинаторной теории . Серия B. 30 (3): 364–371. doi : 10.1016/0095-8956(81)90054-X .
^ Сасакура, Нобуо; Энта, Ёити; Кагесава, Масатака (1993). «Построение рефлексивных пучков ранга два со свойствами, аналогичными расслоению Хоррокса–Мамфорда». Proc. Japan Acad., Ser. A . 69 (5): 144–148. doi : 10.3792/pjaa.69.144 .
^ Мохар, Боян (2005). «Триангуляции и гипотеза Хайоша». Электронный журнал комбинаторики . 12 : N15. doi : 10.37236/1982 . MR 2176532.
^ Уайт, AT (2001). "Графы групп на поверхностях". Взаимодействия и модели . Амстердам: North-Holland Mathematics Studies 188.

Дальнейшее чтение

Бейкер, РД; Эберт, ГЛ; Хемметер, Дж.; Уолдар, А.Дж. (1996). «Максимальные клики в графе Пейли квадратного порядка». J. Statist. Plann. Inference . 56 : 33–38. doi :10.1016/S0378-3758(96)00006-7.
Broere, I.; Döman, D.; Ridley, JN (1988). «Числа клик и хроматические числа некоторых графов Пейли». Quaestiones Mathematicae . 11 : 91–93. doi :10.1080/16073606.1988.9631945.

Внешние ссылки

Брауэр, Андрис Э. «Графы Пейли».
Мохар, Боян (2005). «Род графов Пейли».