Граф Пелі

Шаблон:Граф В теорії графів графами Пелі (на честь Шаблон:Не перекладено) називають щільні неорієнтовані графи, побудовані з членів відповідного скінченного поля шляхом з'єднання пар елементів, що відрізняються на квадратичний лишок. Графи Пелі утворюють нескінченне сімейство конференційних графів, оскільки тісно пов'язані з нескінченним сімейством симетричних конференційних матриць. Графи Пелі дають можливість застосувати теоретичні засоби теорії графів у теорії квадратичних лишків і мають цікаві властивості, що робить їх корисними для теорії графів загалом.

Графи Пелі тісно пов'язані з побудовою Пелі для побудови матриць Адамара з квадратичних лишків (Пелі, 1933). Як графи їх незалежно ввели Закс (Sachs, 1962) і Ердеш спільно з Реньї (Erdős, Rényi, 1963). Горст Закс (Horst Sachs) цікавився ними через їхню властивість самодоповнюваності, тоді як Ердеш і Реньї вивчали їхні симетрії.

Орграфи Пелі є прямим аналогом графів Пелі і відповідають антисиметричним конференційним матрицям. Їх увели Грем і Спенсер (і, незалежно, Закс, Ердеш і Реньї) як шлях побудови турніру з властивостями, раніше відомими тільки для випадкових турнірів: в орграфах Пелі підмножина вершин домінується будь-якою вершиною.

Визначення

Нехай q — степінь простого числа, такий, що q = 1 (mod 4). Зауважимо, що звідси випливає існування квадратного кореня з −1 в єдиному скінченному полі F_q, що має порядок q.

Нехай також V = F_q і

$E=\{(a,b)\in {𝐅}_q\times {𝐅}_q:a-b\in ({𝐅}_q^{\times }{)}^2\}$.

Ця множина коректно визначена, оскільки 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).

Властивості

• Графи Пелі є самодоповняльним — доповнення будь-якого графа Пелі ізоморфне самому графу.
• Ці графи сильно регулярні з параметрами

$srg(q,\frac{1}{2}(q-1),\frac{1}{4}(q-5),\frac{1}{4}(q-1)).$

До того ж графи Пелі, фактично, утворюють нескінченне сімейство конференційних графів.

• Власні значення графів Пелі — це числа $\frac{1}{2}(q-1)$ (з кратністю 1) і $\frac{1}{2}(-1\pm \sqrt{q})$ (обидва з кратністю $\frac{1}{2}(q-1)$) і можуть бути обчислені за допомогою Шаблон:Не перекладено.

• Якщо q — просте, межами ізопериметричного числа i(G) будуть:

$\frac{q-\sqrt{q}}{4}\le i(G)\le \sqrt{(q+\sqrt{q})\left(\frac{q-\sqrt{q}}{2}\right)}$

Звідси випливає, що i(G)~O (q), і граф Пелі є експандером.

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

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

Застосування

• Граф Пелі 17-го порядку є єдиним найбільшим графом G, таким, що ні він сам, ні його доповнення не містять повного підграфа з 4 вершинами (Еванс та ін., 1981). З цього випливає, що число Рамсея R(4, 4) = 18.

• Граф Пелі 101-го порядку поки єдиний відомий максимальний граф G, такий, що ні G, ні його доповнення не містять повного підграфа з 6 вершинами.

• Сасакура використовував графи Пелі для узагальнення побудови Шаблон:Не перекладено.

Орграфи Пелі

Нехай q — степінь простого числа, такий, що q = 3 (mod 4). Тоді скінченне поле F_q порядку q не має квадратного кореня з −1. Отже, для будь-якої пари (a,b) різних елементів F_q або a − b, або b − a, але не обидва, є квадратами. Орграф Пелі — це орієнтований граф зі множиною вершин V = F_q і множиною дуг

$A=\{(a,b)\in {𝐅}_q\times {𝐅}_q:b-a\in ({𝐅}_q^{\times }{)}^2\}.$

Орграф Пелі є турніром, оскільки кожна пара різних вершин пов'язана дугою в одному і тільки в одному напрямку.

Орграф Пелі веде до побудови деяких антисиметричних конференційних матриць і двоплощинної геометрії.

Рід графа

Шість сусідів кожної вершини в графі Пелі 13-го порядку з'єднані в цикл, так що граф локально циклічний. Таким чином, цей граф можна вкласти в тріангуляцію Вітні тора, в якій кожна грань є трикутником і кожен трикутник є гранню. У загальнішому випадку, якщо який-небудь граф Пелі порядку q можна вкласти таким чином, що всі його грані є трикутниками, ми можемо обчислити рід отриманої поверхні за допомогою ейлерової характеристики $\frac{1}{24}(q^2-13q+24)$. Шаблон:Нп (Bojan Mohar, 2005) висловив гіпотезу, що мінімальний рід поверхні, в яку можна вкласти граф Пелі, десь біля цього значення в разі, якщо q є квадратом, і поставив питання, чи можна узагальнити такі межі. Зокрема, Могар припустив, що графи Пелі квадратного порядку можна вкласти в поверхні роду

$(q^2-13q+24)(\frac{1}{24}+o(1)),$

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

Вайт (White, 2001) знайшов вкладення графів Пелі порядку q ≡ 1 (mod 8), узагальнюючи природне вкладення графа Пелі 9-го порядку як квадратної ґратки на тор. Однак рід вкладення Вітні вищий приблизно в три рази від межі, яку Могар назвав у своїй гіпотезі.

Див. також

• Граф Брауера — Хемерса

Література

• Шаблон:Стаття
• Шаблон:Стаття

Посилання

• Шаблон:Cite webШаблон:Недоступне посилання
• Шаблон:Cite webШаблон:Недоступне посилання