Граф Пейли

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

Определение


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

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

Пример


 Для q = 13 поле F\textsubscriptq образуетсячислами по модулю 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 (mod4). Тогда конечное поле F\textsubscriptq порядкаq не имеет квадратного корня из −1. Следовательно, для любой пары(a,b) различных элементовF\textsubscriptq либо ab, либоba, но не оба, являются квадратами. ДиграфПейли — это ориентированный граф с множеством вершин V =F\textsubscriptq и множеством дуг

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-го порядка как квадратной решётки на тор. Однако род вложения Уитни выше примерно в три раза границы, которую Мохар высказал в своей гипотезе.