Русская Википедия:Граф Пэли
Шаблон:Also Шаблон:Граф В теории графов графами Пэли (названы в честь Шаблон:Iw) называются плотные неориентированные графы, построенные из членов подходящего конечного поля путём соединения пар элементов, отличающихся на квадратичный вычет. Графы Пэли образуют бесконечное семейство конференсных графов, поскольку тесно связаны с бесконечным семейством симметричных конференсных матриц. Графы Пэли дают возможность применить теоретические средства теории графов в теории квадратичных вычетов и имеют интересные свойства, что делает их полезными для теории графов в общем.
Графы Пэли тесно связаны с построением Палея для построения матриц Адамара из квадратичных вычетов (Пэли, 1933)[1]. Они были введены как графы независимо Саксом (Sachs, 1962) и Эрдёшем совместно с Реньи (Erdős, Rényi, 1963)[2]. Хорст Сакс (Horst Sachs) интересовался ими из-за их свойства самодополнительности, в то время как Эрдёш и Реньи изучали их симметрии.
Орграфы Пэли являются прямым аналогом графов Пэли и соответствуют антисимметричным конференсным матрицам. Они были введены Грэмом и Спенсером[3] (и, независимо, Саксом, Эрдёшем и Реньи) как путь построения турниров со свойствами, ранее известными только для случайных турниров: в орграфах Пэли любое подмножество вершин доминируется какой-либо вершиной.
Определение
Пусть q — степень простого числа, такая, что q = 1 (mod 4). Заметим, что отсюда вытекает существование квадратного корня из −1 в единственном конечном поле Fq , имеющем порядок q.
Пусть также V = Fq и
- <math>E= \left \{(a,b)\in \mathbf{F}_q\times\mathbf{F}_q \ : \ a-b\in (\mathbf{F}_q^{\times})^2 \right \}</math>.
Это множество корректно определено, поскольку a − b = −(b − a), и −1 является квадратом некоего числа, откуда следует, что a − b является квадратом тогда и только тогда, когда b − a является квадратом.
По определению 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).
Свойства
- Графы Пэли являются самодополнительным — дополнение любого графа Пэли изоморфно самому графу.[4]
- Эти графы сильно регулярны с параметрами
- <math>srg \left (q, \tfrac{1}{2}(q-1),\tfrac{1}{4}(q-5),\tfrac{1}{4}(q-1) \right ).</math>
- Вдобавок графы Пэли, фактически, образуют бесконечное семейство конференсных графов.
- Собственные значения графов Пэли — это числа <math>\tfrac{1}{2}(q-1)</math> (с кратностью 1) и <math>\tfrac{1}{2} (-1 \pm \sqrt{q})</math> (оба с кратностью <math>\tfrac{1}{2}(q-1)</math>) и могут быть вычислены с помощью Шаблон:Не переведено 5.
- Если q — простое, границами изопериметрического числа i(G) будут:
- <math>\frac{q-\sqrt{q}}{4}\leq i(G) \leq \sqrt { \left (q+\sqrt{q} \right ) \left (\frac{q-\sqrt{q}}{2} \right ) }</math>
- Отсюда следует, что i(G)~O(q), и граф Пэли является экспандером.
- Если q — простое, его граф Пэли является гамильтоновым циклом циркулянтного графа.
- Графы Пэли квазислучайны (Чанг и др., 1989)[5] — число случаев, когда граф постоянного порядка окажется подграфом графа Пэли, равен (в пределе для больших q) тем же, что и для случайных графов, а при больших множествах вершин имеет примерно то же самое число рёбер, что и у случайных графов.
Приложения
- Граф Пэли 17-го порядка является единственным наибольшим графом G, таким, что ни он сам, ни его дополнение не содержат полный подграф с 4 вершинами (Эванс и др., 1981).[6] Из этого следует, что число Рамсея R(4, 4) = 18.
- Граф Пэли 101-го порядка пока единственный известный максимальный граф G, такой, что ни G, ни его дополнение не содержат полного подграфа с 6 вершинами.
- Сасакура[7] использовал графы Пэли для обобщения построения Шаблон:Не переведено 5.
Орграфы Пэли
Пусть q — степень простого числа, такая, что q = 3 (mod 4). Тогда конечное поле Fq порядка q не имеет квадратного корня из −1. Следовательно, для любой пары (a,b) различных элементов Fq либо a − b, либо b − a, но не оба, являются квадратами. Орграф Пэли — это ориентированный граф с множеством вершин V = Fq и множеством дуг
- <math>A = \left \{(a,b)\in \mathbf{F}_q\times\mathbf{F}_q \ : \ b-a\in (\mathbf{F}_q^{\times})^2 \right \}.</math>
Орграф Пэли является турниром, поскольку каждая пара различных вершин связана дугой в одном и только в одном направлении.
Орграф Пэли ведёт к построению некоторых антисимметричных конференсных матриц и двухплоскостной геометрии.
Род графа
Шесть соседей каждой вершины в графе Пэли 13-го порядка соединены в цикл, так что граф локально цикличен. Таким образом, этот граф может быть вложен в триангуляцию Уитни тора, в которой каждая грань является треугольником и каждый треугольник является гранью. В более общем случае, если какой-либо граф Пэли порядка q может быть вложен таким образом, что все его грани являются треугольниками, мы можем вычислить род результирующей поверхности с помощью эйлеровой характеристики <math>\tfrac{1}{24}(q^2 - 13q + 24)</math>. Мохар (Bojan Mohar, 2005) высказал гипотезу, что минимальный род поверхности, в которую может быть вложен граф Пэли, где-то около этого значения в случае, если q является квадратом, и поставил вопрос, можно ли обобщить такие границы. В частности, Мохар предположил, что графы Пэли квадратного порядка могут быть вложены в поверхности рода
- <math>(q^2 - 13q + 24)\left(\tfrac{1}{24} + o(1)\right),</math>
где член o(1) может быть любой функцией от q, стремящейся к нулю при стремлении q к бесконечности.
Уайт (White, 2001) [8] нашёл вложение графов Пэли порядка q ≡ 1 (mod 8), обобщая естественное вложение графа Пэли 9-го порядка как квадратной решётки на тор. Однако род вложения Уитни выше примерно в три раза границы, которую Мохар высказал в своей гипотезе.
Ссылки
Внешние ссылки
