Граф Пелі

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Граф Пелі
Граф Пелі порядку 13
Названо на честь Раймонд Пелі[en]
Вершин q ≡ 1 mod 4,
qстепінь простого числа
Ребер q(q − 1)/4
Діаметр 2
Властивості сильно регулярний
конференційний
самодоповняльний
Позначення QR(q)

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

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

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

Визначення

[ред. | ред. код]

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

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

.

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

Властивості

[ред. | ред. код]
До того ж графи Пелі, фактично, утворюють нескінченне сімейство конференційних графів.
  • Власні значення графів Пелі — це числа (з кратністю 1) і (обидва з кратністю ) і можуть бути обчислені за допомогою квадратичних сум Гауса[en].
Звідси випливає, що i(G)~O (q), і граф Пелі є експандером.
  • Графи Пелі квазівипадкові (Чанг та ін., 1989)[5] — число випадків, коли граф сталого порядку виявиться підграфом графа Пелі, дорівнює (в границі для великих q) тим самим, що й для випадкових графів, а за великих множин вершин має приблизно таке саме число ребер, що й у випадкових графів.

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

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

Орграфи Пелі

[ред. | ред. код]

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

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

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

Рід графа

[ред. | ред. код]

Шість сусідів кожної вершини в графі Пелі 13-го порядку з'єднані в цикл, так що граф локально циклічний. Таким чином, цей граф можна вкласти в тріангуляцію Вітні тора, в якій кожна грань є трикутником і кожен трикутник є гранню. У загальнішому випадку, якщо який-небудь граф Пелі порядку q можна вкласти таким чином, що всі його грані є трикутниками, ми можемо обчислити рід отриманої поверхні за допомогою ейлерової характеристики . Могар[en] (Bojan Mohar, 2005) висловив гіпотезу, що мінімальний рід поверхні, в яку можна вкласти граф Пелі, десь біля цього значення в разі, якщо q є квадратом, і поставив питання, чи можна узагальнити такі межі. Зокрема, Могар припустив, що графи Пелі квадратного порядку можна вкласти в поверхні роду

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

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

Див. також

[ред. | ред. код]

Посилання

[ред. | ред. код]
  1. R. E. A. C. Paley. On orthogonal matrices // J. Math. Phys.. — Т. 12. — С. 311–320.
  2. Asymmetric graphs // Acta Mathematica Academiae Scientiarum Hungaricae. — 1963. — Т. 14, вип. 3–4 (16 червня). — С. 295–315. — DOI:10.1007/BF01895716.
  3. R. L. Graham, J. H. Spencer. A constructive solution to a tournament problem // Canadian Mathematical Bulletin. — 1971. — Т. 14 (16 червня). — С. 45–48. — DOI:10.4153/CMB-1971-007-1.
  4. Horst Sachs. Über selbstkomplementäre Graphen // Publicationes Mathematicae Debrecen. — 1962. — Т. 9 (16 червня). — С. 270–288.
  5. Chung, Fan R. K., Р. Грэм, R. M. Wilson,. Quasi-random graps // Combinatorica. — 1989. — Т. 9, вип. 4 (16 червня). — С. 345–362. — DOI:10.1007/BF02125347.
  6. Evans, R. J.; Pulham, J. R.; Sheehan, J. On the number of complete subgraphs contained in certain graphs // Journal of Combinatorial Theory, Series B. — 1981. — Т. 30, вип. 3 (16 червня). — С. 364–371. — DOI:10.1016/0095-8956(81)90054-X.
  7. Sasakura, Nobuo; Enta, Yoichi; Kagesawa, Masataka. Construction of rank two reflexive sheaves with similar properties to the Horrocks–Mumford bundle // Proc. Japan Acad., Ser. A. — 1993. — Т. 69, вип. 5 (16 червня). — С. 144–148. — DOI:10.2183/pjab.69.144.
  8. White, A. T. Graphs of groups on surfaces // Interactions and models. — Amsterdam : North-Holland Mathematics Studies 188, 2001.

Література

[ред. | ред. код]
  • Baker, R. D.; Ebert, G. L.; Hemmeter, J.; Woldar, A. J. Maximal cliques in the Paley graphs of square order // J. Statist. Plann. Inference. — 1996. — Т. 56 (16 червня). — С. 33–38. — DOI:10.1016/S0378-3758(96)00006-7.
  • Broere, I.; Döman, D.; Ridley, J. N. The clique numbers and chromatic numbers of certain Paley graphs // Quaestiones Mathematicae. — 1988. — Т. 11 (16 червня). — С. 91–93. — DOI:10.1080/16073606.1988.9631945.

Посилання

[ред. | ред. код]
  • Brouwer, Andries E. Paley graps. {{cite web}}: Недійсний |deadurl=404 (довідка)[недоступне посилання з червня 2018]
  • Mohar, Bojan (2005). PaleyGenus.html Genus of Paley graps.[недоступне посилання з вересня 2018]