Граф Пейли

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Граф Пейли
Граф Пейли 13-го порядка
Граф Пейли 13-го порядка
Вершин

q ≡ 1 mod 4, q — степень простого числа

Рёбер

q(q − 1)/4

Свойства

Сильно регулярный
Самодополнительный
Конференсный граф

Обозначение

QR(q)

В теории графов графами Пейли (названы в честь Раймонда Пейли), называются плотные неориентированные графы, построенные из членов подходящего конечного поля путём соединения пар элементов, отличающихся на квадратичный остаток[en]. Графы Пейли образуют бесконечное семейство конференсных графов, поскольку тесно связаны с бесконечным семейством симметричных конференсных матриц. Графы Пейли дают возможность применить теоретические средства теории графов в теории квадратичных вычетов и имеют интересные свойства, что делает их полезными для теории графов в общем.

Графы Пейли тесно связаны с построением Пейли для построения матриц Адамара из квадратичных вычетов (Пейли,1933)[1]. Они были введены как графы независимо Саксом (Sachs, 1962) и Эрдёшем совместно с Реньи (Erdős, Rényi, 1963)[2] . Хорст Сакс (Horst Sachs) интересовался ими из-за их свойства самодополнительности, в то время как Эрдёш и Реньи изучали их симметрии.

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

Определение[править | править исходный текст]

Пусть q — степень простого числа такая, что q = 1 (mod 4). Заметим, что отсюда вытекает существование квадратного корня из  −1 в единственном конечном поле Fq , имеющем порядок q.

Пусть также V = Fq и

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

Это множество хорошо определено, поскольку a − b = −(b − a), и  −1 является квадратом некоего числа, откуда следует, что a − b является квадратом тогда и только тогда, когда b − a является квадратом.

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

Пример[править | править исходный текст]

Для q = 13 поле Fq образуется числами по модулю 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).

Свойства[править | править исходный текст]

srg \left (q, \tfrac{1}{2}(q-1),\tfrac{1}{4}(q-5),\tfrac{1}{4}(q-1) \right ).
Вдобавок, графы Пейли, фактически, образуют бесконечное семейство конференсных графов.
  • Собственные значения графов Пейли — это числа \tfrac{1}{2}(q-1) (с кратностью 1) и \tfrac{1}{2} (-1 \pm \sqrt{q}) (оба с кратностью \tfrac{1}{2}(q-1)) и могут быть вычислены с помощью квадратичных сумм Гаусса[en].
\frac{q-\sqrt{q}}{4}\leq i(G) \leq \sqrt { \left (q+\sqrt{q} \right ) \left (\frac{q-\sqrt{q}}{2} \right ) }
Отсюда следует, что i(G)~O(q), и граф Пейли является экспандером.
  • Графы Пейли квазислучайны (Чанг и др., 1989)[5] — число случаев, когда граф постоянного порядка окажется подграфом графа Пейли, равен (в пределе для больших q) тем же, что и для случайных графов, а при больших множествах вершин имеет примерно то же самое число рёбер, что и у случайных графов.

Приложения[править | править исходный текст]

  • Граф Пейли 17-го порядка является единственным наибольшим графом G, таким что ни он сам, ни его дополнение не содержат полный подграф с 4-мя вершинами (Эванс и др., 1981).[6] Из этого следует, что число Рамсея R(4, 4) = 18.
  • Граф Пейли 101-го порядка пока единственный известный максимальный граф G, такой что ни G, ни его дополнение не содержат полного подграфа с 6-ю вершинами.

Диграфы Пейли[править | править исходный текст]

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

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

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

Диграф Пейли ведёт к построению некоторых антисимметричных конференсных матриц и двухплоскостной геометрии[en].

Род графа[править | править исходный текст]

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

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

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

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

Ссылки[править | править исходный текст]

  1. R.E.A.C. Paley On orthogonal matrices // J. Math. Phys.. — Т. 12. — С. 311–320..
  2. Asymmetric graphs // Acta Mathematica Academiae Scientiarum Hungaricae. — 1963. — В. 3–4. — Т. 14. — С. 295–315. — DOI:10.1007/BF01895716.
  3. R. L.Graham, J. H. Spencer A constructive solution to a tournament problem // Canadian Mathematical Bulletin. — 1971. — Т. 14. — С. 45–48. — DOI:10.4153/CMB-1971-007-1.
  4. Horst Sachs Über selbstkomplementäre Graphen // Publicationes Mathematicae Debrecen. — 1962. — Т. 9. — С. 270–288..
  5. Chung, Fan R. K., Graham, Ronald L.[en], R. M. Wilson, Quasi-random graps // Combinatorica. — 1989. — В. 4. — Т. 9. — С. 345–362. — DOI:10.1007/BF02125347
  6. Evans, R. J.; Pulham, J. R.; Sheehan, J. On the number of complete subgraphs contained in certain graphs // Journal of Combinatorial Theory, Series B. — 1981. — В. 3. — Т. 30. — С. 364–371. — DOI:10.1016/0095-8956(81)90054-X
  7. Sasakura, Nobuo; Enta, Yoichi; Kagesawa, Masataka Construction of rank two reflexive sheaves with similar properties to the Horrocks–Mumford bundle // Proc. Japan Acad., Ser. A. — 1993. — В. 5. — Т. 69. — С. 144–148. — DOI:10.2183/pjab.69.144
  8. White, A. T. Graphs of groups on surfaces // Interactions and models. — Amsterdam: North-Holland Mathematics Studies 188, 2001.
  • Baker, R. D.; Ebert, G. L.; Hemmeter, J.; Woldar, A. J. Maximal cliques in the Paley graphs of square order // J. Statist. Plann. Inference. — 1996. — Т. 56. — С. 33–38. — DOI:10.1016/S0378-3758(96)00006-7
  • Broere, I.; Döman, D.; Ridley, J. N. The clique numbers and chromatic numbers of certain Paley graphs // Quaestiones Mathematicae. — 1988. — Т. 11. — С. 91–93. — DOI:10.1080/16073606.1988.9631945

Ссылки[править | править исходный текст]