Граф Пэли - Paley graph

Граф Пэли
Граф Пэли порядка 13
Названный в честь	Раймонд Пейли
Вершины	q ≡ 1 мод 4, q основная сила
Края	q(q − 1)/4
Диаметр	2
Характеристики	Сильно регулярный График конференции Самодостаточный
Обозначение	QR (q)
Таблица графиков и параметров

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

Графы Пэли названы в честь Раймонд Пейли. Они тесно связаны с Строительство Пейли для строительства Матрицы Адамара из квадратичных вычетов (Пейли 1933 Они были введены в виде графов независимо Сакс (1962) и Эрдеш и Реньи (1963). Sachs интересовались ими из-за их свойств самодополнимости, в то время как Erds и Реньи изучили их симметрии.

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

Определение

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

Теперь позвольте V = F_q и разреши

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

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

По определению грамм = (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] и соединяем каждое такое целое число Икс шести соседям: Икс ± 1 (мод 13), Икс ± 3 (mod 13), и Икс ± 4 (мод 13).

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

• Графики Пэли самодостаточный: дополнение любого графа Пэли изоморфно ему, например через отображение, которое берет вершину Икс к xk (модq), куда k любой мод без остаткаq (Сакс 1962 г. ).
• Эти графики сильно регулярные графы с параметрами

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

Кроме того, графы Пэли образуют бесконечное семейство графики конференций.

• Собственные значения графов Пэли равны ${\displaystyle {\tfrac {1}{2}}(q-1)}$ (с кратностью 1) и ${\displaystyle {\tfrac {1}{2}}(-1\pm {\sqrt {q}})}$ (оба с кратностью ${\displaystyle {\tfrac {1}{2}}(q-1)}$) и может быть рассчитана с помощью квадратичная сумма Гаусса или используя теорию сильно регулярных графов.
• Если q простое число, оценки изопериметрическое число я(грамм) находятся:

${\displaystyle {\frac {q-{\sqrt {q}}}{4}}\leq i(G)\leq {\sqrt {\left(q+{\sqrt {q}}\right)\left({\frac {q-{\sqrt {q}}}{2}}\right)}}.}$

• Когда q простое, его граф Пэли Гамильтониан циркулянтный график.
• Графики Пэли квазислучайный (Чанг и др., 1989): сколько раз каждый возможный граф постоянного порядка встречается как подграф графа Пэли (в пределе для больших q) так же, как и для случайных графов, а большие наборы вершин имеют примерно такое же количество ребер, как и в случайных графах.

Приложения

• Граф Пэли порядка 9 - это локально линейный граф, а график ладьи, а график 3-3 дуопризма.
• Граф Пэли порядка 13 имеет толщина книги 4 и номер очереди 3 (Вольц 2018 ).
• Граф Пэли 17-го порядка - единственный наибольший граф грамм так что ни грамм ни его дополнение не содержит полного 4-вершинного подграфа (Evans et al. 1981). Отсюда следует, что Число Рамсея р(4, 4) = 18.
• Граф Пэли порядка 101 в настоящее время является самым большим из известных графов. грамм так что ни грамм и его дополнение не содержит полного 6-вершинного подграфа.
• Sasukara et al. (1993) использовали графы Пэли для обобщения конструкции Набор Хоррокса – Мамфорда.

Диграфы Пэли

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

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

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

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

Род

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

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

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

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

Рекомендации

• Baker, R.D .; Ebert, G.L .; Hemmeter, J .; Волдар, А. Дж. (1996). «Максимальные клики в графе Пэли квадратного порядка». J. Statist. Plann. Вывод. 56: 33–38. Дои:10.1016 / S0378-3758 (96) 00006-7.
• Broere, I .; Döman, D .; Ридли, Дж. Н. (1988). «Кликовые числа и хроматические числа некоторых графов Пэли». Quaestiones Mathematicae. 11: 91–93. Дои:10.1080/16073606.1988.9631945.
• Чунг, Фан Р. К.; Грэм, Рональд Л.; Уилсон, Р. М. (1989). «Квазислучайные графы». Комбинаторика. 9 (4): 345–362. Дои:10.1007 / BF02125347.
• Эрдеш, П.; Реньи, А. (1963). «Асимметричные графы». Acta Mathematica Academiae Scientiarum Hungaricae. 14 (3–4): 295–315. Дои:10.1007 / BF01895716. МИСТЕР  0156334.
• Evans, R.J .; Pulham, J. R .; Шихан, Дж. (1981). «О количестве полных подграфов, содержащихся в определенных графах». Журнал комбинаторной теории. Серия Б. 30 (3): 364–371. Дои:10.1016 / 0095-8956 (81) 90054-Х.
• Грэм, Р. Л.; Спенсер, Дж. Х. (1971). «Конструктивное решение турнирной задачи». Канадский математический бюллетень. 14: 45–48. Дои:10.4153 / CMB-1971-007-1. МИСТЕР  0292715.
• Мохар, Боян (2005). «Триангуляции и гипотеза Хаджоса». Электронный журнал комбинаторики. 12: N15. МИСТЕР  2176532.
• Пейли, R.E.A.C. (1933). «Об ортогональных матрицах». J. Math. Phys. 12 (1–4): 311–320. Дои:10.1002 / sapm1933121311.
• Сакс, Хорст (1962). "Über selbstkomplementäre Graphen". Publicationes Mathematicae Debrecen. 9: 270–288. МИСТЕР  0151953.
• Сасакура, Нобуо; Энта, Йоичи; Кагесава, Масатака (1993). «Построение рефлексивных пучков ранга два со свойствами, аналогичными расслоению Хоррокса – Мамфорда». Proc. Japan Acad., Ser. А. 69 (5): 144–148. Дои:10.3792 / pjaa.69.144.
• Уайт, А. Т. (2001). «Графы групп на поверхностях». Взаимодействия и модели. Амстердам: Математические исследования Северной Голландии 188.
• Вольц, Джессика (2018). Инженерные линейные схемы с SAT. Дипломная работа. Тюбингенский университет.

внешняя ссылка

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