Loading AI tools
щільний неорієнтований граф, побудований із членів скінченного поля з'єднанням пар елементів, що відрізняються на квадратичний лишок З Вікіпедії, вільної енциклопедії
В теорії графів графами Пелі (на честь Раймонда Пелі[en]) називають щільні неорієнтовані графи, побудовані з членів відповідного скінченного поля шляхом з'єднання пар елементів, що відрізняються на квадратичний лишок. Графи Пелі утворюють нескінченне сімейство конференційних графів, оскільки тісно пов'язані з нескінченним сімейством симетричних конференційних матриць. Графи Пелі дають можливість застосувати теоретичні засоби теорії графів у теорії квадратичних лишків і мають цікаві властивості, що робить їх корисними для теорії графів загалом.
Граф Пелі | |
---|---|
Названо на честь | Раймонд Пелі[en] |
Вершин | q ≡ 1 mod 4, q — степінь простого числа |
Ребер | q(q − 1)/4 |
Діаметр | 2 |
Властивості | сильно регулярний конференційний самодоповняльний |
Позначення | QR(q) |
Графи Пелі тісно пов'язані з побудовою Пелі для побудови матриць Адамара з квадратичних лишків (Пелі, 1933)[1]. Як графи їх незалежно ввели Закс (Sachs, 1962) і Ердеш спільно з Реньї (Erdős, Rényi, 1963)[2]. Горст Закс (Horst Sachs) цікавився ними через їхню властивість самодоповнюваності, тоді як Ердеш і Реньї вивчали їхні симетрії.
Орграфи Пелі є прямим аналогом графів Пелі і відповідають антисиметричним конференційним матрицям. Їх увели Грем і Спенсер[3] (і, незалежно, Закс, Ердеш і Реньї) як шлях побудови турніру з властивостями, раніше відомими тільки для випадкових турнірів: в орграфах Пелі підмножина вершин домінується будь-якою вершиною.
Нехай q — степінь простого числа, такий, що q = 1 (mod 4). Зауважимо, що звідси випливає існування квадратного кореня з −1 в єдиному скінченному полі Fq, що має порядок q.
Нехай також V = Fq і
Ця множина коректно визначена, оскільки a − b = −(b − a), і −1 є квадратом якогось числа, звідки випливає, що a − b є квадратом тоді і лише тоді, коли b − a є квадратом.
За визначенням G = (V, E) — граф Пелі порядку q.
Задля q = 13 поле Fq утворюється числами за модулем 13. Числа, що мають квадратні корені за модулем 13:
Таким чином, граф Пелі утворюють вершини, які відповідають числам з інтервалу [0,12], і кожна вершина x з'єднана з шістьма сусідами: x ± 1 (mod 13), x ± 3 (mod 13), і x ± 4 (mod 13).
Нехай q — степінь простого числа, такий, що q = 3 (mod 4). Тоді скінченне поле Fq порядку q не має квадратного кореня з −1. Отже, для будь-якої пари (a,b) різних елементів Fq або a − b, або b − a, але не обидва, є квадратами. Орграф Пелі — це орієнтований граф зі множиною вершин V = Fq і множиною дуг
Орграф Пелі є турніром, оскільки кожна пара різних вершин пов'язана дугою в одному і тільки в одному напрямку.
Орграф Пелі веде до побудови деяких антисиметричних конференційних матриць і двоплощинної геометрії.
Шість сусідів кожної вершини в графі Пелі 13-го порядку з'єднані в цикл, так що граф локально циклічний. Таким чином, цей граф можна вкласти в тріангуляцію Вітні тора, в якій кожна грань є трикутником і кожен трикутник є гранню. У загальнішому випадку, якщо який-небудь граф Пелі порядку q можна вкласти таким чином, що всі його грані є трикутниками, ми можемо обчислити рід отриманої поверхні за допомогою ейлерової характеристики . Могар[en] (Bojan Mohar, 2005) висловив гіпотезу, що мінімальний рід поверхні, в яку можна вкласти граф Пелі, десь біля цього значення в разі, якщо q є квадратом, і поставив питання, чи можна узагальнити такі межі. Зокрема, Могар припустив, що графи Пелі квадратного порядку можна вкласти в поверхні роду
де член o(1) може бути будь-якою функцією від q, яка прямує до нуля при прямуванні q до нескінченності.
Вайт (White, 2001)[8] знайшов вкладення графів Пелі порядку q ≡ 1 (mod 8), узагальнюючи природне вкладення графа Пелі 9-го порядку як квадратної ґратки на тор. Однак рід вкладення Вітні вищий приблизно в три рази від межі, яку Могар назвав у своїй гіпотезі.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.