Граф Пейли

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

Определение


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

E={(a,b)Fq×Fq : ab(Fq×)2}.
  Это множество хорошо определено, поскольку ab = −(ba), и −1 является квадратом некоего числа, откуда следует, что ab является квадратом тогда и только тогда, когда ba является квадратом.
 По определению G = (V, E) — граф Пейли порядка 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).

Свойства



  • Графы Пейли являются самодополнительным — дополнение любого графа Пейли изоморфен самому графу.\textless!-- , например, путём отображения вершины x в xk (mod q), где k — любой невычет по модулю q

 Такое странное суждение. Видимо, имеются в виду квадратичные невычеты. Найти бы источник\ldots--\textgreater

  • Эти графы сильно регулярны с параметрами



srg(q,12(q1),14(q5),14(q1)).


  • Собственные значения графов Пейли — это числа 12(q1) (с кратностью 1) и 12(1±q) (оба с кратностью 12(q1)) и могут быть вычислены с помощью .


  • Если q — простое, границами изопериметрического числа i(G) будут:



qq4i(G)(q+q)(qq2)


  • Если q — простое, его граф Пейли является гамильтоновым циклом циркулянтного графа.


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

Приложения



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


  • Граф Пейли 101-го порядка пока единственный известный максимальный граф G, такой, что ни G, ни его дополнение не содержат полного подграфа с 6-ю вершинами.


  • Сасакура использовал графы Пейли для обобщения построения .

Диграфы Пейли


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

A={(a,b)Fq×Fq : ba(Fq×)2}.
  Диграф Пейли является турниром, поскольку каждая пара различных вершин связана дугой в одном и только в одном направлении.
 Диграф Пейли ведёт к построению некоторых антисимметричных конференсных матриц и .

Род графа


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

(q213q+24)(124+o(1)),
  где член o(1) может быть любой функцией от q, стремящейся к нулю при стремлении q к бесконечности.
 Уайт (White, 2001)
 \textttнашёл вложение графов Пейли порядка \textttq\texttt ≡ 1 (mod 8), обобщая естественное вложение графа Пейли 9-го порядка как квадратной решётки на тор. Однако род вложения Уитни выше примерно в три раза границы, которую Мохар высказал в своей гипотезе.