Граф Пэли

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

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

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

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

Определение [ править ]

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

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

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

.

Если пара { a , b } включена в E , она включается в любой порядок ее двух элементов. For, 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 - любой невычет по модулю q ( Sachs 1962 ).

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

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

Фактически это следует из того факта, что граф является дугово-транзитивным и самодополняющим. Кроме того, графы Пэли образуют бесконечное семейство графов конференций . ^{[ необходима цитата ]}

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

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

{\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 ( Wolz 2018 ).
Граф Пэли порядка 17 - это единственный наибольший граф G такой, что ни G, ни его дополнение не содержат полного 4-вершинного подграфа (Evans et al. 1981). Отсюда следует, что число Рамсея R (4, 4) = 18.
Граф Пэли порядка 101 в настоящее время является самым большим из известных графов G , так что ни G, ни его дополнение не содержат полного 6-вершинного подграфа.
Sasukara et al. (1993) использовали графы Пэли для обобщения конструкции расслоения Хоррокса – Мамфорда .

Орграфы Пэли [ править ]

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

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

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

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

Род [ править ]

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

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

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

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

Брауэр, Андрис Э. "Графы Пэли" .
Mohar, Bojan (2005). "Genus of Paley graphs".