Перегляд вихідного коду сторінки Граф Пелі

{{Граф
 | name = Граф Пелі
 | image = [[Файл:Paley13.svg|250px]]
 | image_caption = Граф Пелі порядку 13
 | namesake = {{Не перекладено|Раймонд Пелі||en|Raymond Paley}}
 | vertices = ''q'' ≡ 1 mod 4,<br>''q'' — [[степінь простого числа]]
 | edges = ''q''(''q'' − 1)/4
 | diameter = 2
 | automorphisms 
 | chromatic_number =
 | chromatic_index =
 | properties = [[Сильно регулярний граф|сильно регулярний]]<br>[[конференсний граф|конференсний]]<br>[[Самодоповняльний граф|самодоповняльний]]
 | notation = QR(''q'')
}}
В [[Теорія графів|теорії графів]] '''графами Пелі''' (на честь {{Не перекладено|Раймонд Пелі|Раймонда Пелі|en|Raymond Paley}}) називають [[Щільний граф|щільні]] неорієнтовані графи, побудовані з членів відповідного [[Поле Галуа|скінченного поля]] шляхом з'єднання пар елементів, що відрізняються на [[квадратичний лишок]]. Графи Пелі утворюють нескінченне сімейство [[Конференсний граф|конференсних графів]], оскільки тісно пов'язані з нескінченним сімейством симетричних [[Конференс-матриця|конференс-матриць]]. Графи Пелі дають можливість застосувати теоретичні засоби теорії графів у [[Теорія чисел|теорії]] квадратичних лишків і мають цікаві властивості, що робить їх корисними для теорії графів загалом.

Графи Пелі тісно пов'язані з [[Побудова Пелі|побудовою Пелі]] для побудови [[Матриці Адамара|матриць Адамара]] з квадратичних лишків (Пелі, 1933)<ref>
{{Стаття|author=R. E. A. C. Paley|title=On orthogonal matrices|видання=[[Journal of Mathematical Physics|J. Math. Phys.]]|том=12|pages=311–320}}
</ref>. Як графи їх незалежно ввели Закс (Sachs, 1962) і [[Пал Ердеш|Ердеш]] спільно з [[Альфред Реньї|Реньї]] (Erdős, Rényi, 1963)<ref>
{{Стаття|аутор P. Erdős, A. Rényi|doi=10.1007/BF01895716|видання=Acta Mathematica Academiae Scientiarum Hungaricae|pages=295–315|title=Asymmetric graphs|том=14|date=1963|issue=3–4}}
</ref>. Горст Закс (Horst Sachs) цікавився ними через їхню властивість самодоповнюваності, тоді як [[Пал Ердеш|Ердеш]] і [[Альфред Реньї|Реньї]] вивчали їхні симетрії.

'''Орграфи Пелі''' є прямим аналогом графів Пелі і відповідають антисиметричним конференс-матрицям. Їх увели Грем і Спенсер<ref>
{{Стаття|author=R. L. Graham, J. H. Spencer|видання=[[Canadian Mathematical Bulletin]]|pages=45–48|title=A constructive solution to a tournament problem|том=14|date=1971|doi=10.4153/CMB-1971-007-1}}
</ref> (і, незалежно, Закс, Ердеш і Реньї) як шлях побудови [[Турнір (теорія графів)|турніру]] з властивостями, раніше відомими тільки для випадкових турнірів: в орграфах Пелі [[підмножина]] вершин домінується будь-якою вершиною.

== Визначення ==
Нехай ''q''&nbsp;— [[степінь простого числа]], такий, що ''q'' = 1 (mod 4). Зауважимо, що звідси випливає існування квадратного кореня з −1 в єдиному скінченному полі '''F'''<sub>''q''</sub>, що має порядок ''q''.

Нехай також ''V'' = '''F'''<sub>''q''</sub> і

: <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'')&nbsp;— граф Пелі порядку ''q''.

== Приклад ==
Задля ''q'' = 13 поле '''F'''<sub>''q''</sub> утворюється числами за модулем 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).

== Властивості ==
* Графи Пелі є [[Самодоповняльний граф|самодоповняльним]]&nbsp;— доповнення будь-якого графа Пелі ізоморфне самому графу<ref>
{{Стаття|author=Horst Sachs|видання=Publicationes Mathematicae Debrecen|pages=270–288|title=Über selbstkomplementäre Graphen|том=9|date=1962}}
</ref>.
* Ці графи [[Сильно регулярний граф|сильно регулярні]] з параметрами

:: <math>srg \left (q, \tfrac{1}{2}(q-1),\tfrac{1}{4}(q-5),\tfrac{1}{4}(q-1) \right ).</math>
: До того ж графи Пелі, фактично, утворюють нескінченне сімейство [[Конференсний граф|конференсних графів]].

* Власні значення графів Пелі&nbsp;— це числа <math>\tfrac{1}{2}(q-1)</math> (з кратністю 1) і <math>\tfrac{1}{2} (-1 \pm \sqrt{q})</math> (обидва з кратністю <math>\tfrac{1}{2}(q-1)</math>) і можуть бути обчислені за допомогою {{Не перекладено|Квадратичні суми Гауса|квадратичних сум Гауса|en|quadratic Gauss sum}}.

* Якщо q&nbsp;— просте, межами [[Стала Чіґера (теорія графів)|ізопериметричного числа]] ''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''&nbsp;— просте, його граф Пелі є [[Гамільтонів граф|гамільтоновим циклом]] [[Циркулянтний граф|циркулянтного графа]].

* Графи Пелі ''квазівипадкові'' (Чанг та ін., 1989)<ref>
{{Стаття|author=Chung, Fan R. K., [[Рональд Грем|Р. Грэм]], R. M. Wilson,|title=Quasi-random graps|url=https://archive.org/details/sim_combinatorica_1989_9_4/page/345|видання=[[Combinatorica]]|date=1989|том=9|issue=4|pages=345–362|doi=10.1007/BF02125347}}
</ref>&nbsp;— число випадків, коли граф сталого порядку виявиться підграфом графа Пелі, дорівнює (в границі для великих ''q'') тим самим, що й для випадкових графів, а за великих множин вершин має приблизно таке саме число ребер, що й у випадкових графів.

== Застосування ==
* Граф Пелі 17-го порядку є єдиним найбільшим графом ''G'', таким, що ні він сам, ні його доповнення не містять повного підграфа з 4 вершинами (Еванс та ін., 1981).<ref>
{{Стаття|author=Evans, R. J.; Pulham, J. R.; Sheehan, J.|title=On the number of complete subgraphs contained in certain graphs|видання=[[Journal of Combinatorial Theory, Series B]]|том=30|pages=364–371|date=1981|doi=10.1016/0095-8956(81)90054-X|issue=3}}
</ref> З цього випливає, що [[Теорема Рамсея|число Рамсея]] ''R''(4, 4) = 18.

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

* Сасакура<ref>
{{Стаття|author=Sasakura, Nobuo; Enta, Yoichi; Kagesawa, Masataka|title=Construction of rank two reflexive sheaves with similar properties to the Horrocks–Mumford bundle|видання=Proc. Japan Acad., Ser. A|том=69|issue=5|pages=144–148|date=1993|doi=10.2183/pjab.69.144}}
</ref> використовував графи Пелі для узагальнення побудови {{Не перекладено|Пучок Горрокса — Мамфорда|пучка Горрокса — Мамфорда|en|Horrocks–Mumford bundle}}.

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

: <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>. {{Нп|Боян Могар|Могар|en|Bojan Mohar}} (Bojan Mohar, 2005) висловив гіпотезу, що мінімальний рід поверхні, в яку можна вкласти граф Пелі, десь біля цього значення в разі, якщо ''q'' є квадратом, і поставив питання, чи можна узагальнити такі межі. Зокрема, Могар припустив, що графи Пелі квадратного порядку можна вкласти в поверхні роду

: <math>(q^2 - 13q + 24)\left(\tfrac{1}{24} + o(1)\right),</math>

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

Вайт (White, 2001)<ref>
{{Книга
|автор = White, A. T.
|частина = Graphs of groups on surfaces
|заголовок = Interactions and models
|видавництво = North-Holland Mathematics Studies 188
|місце = Amsterdam
|рік = 2001
}}
</ref> знайшов вкладення графів Пелі порядку ''q'' ≡ 1 (mod 8), узагальнюючи природне вкладення графа Пелі 9-го порядку як квадратної ґратки на тор. Однак рід вкладення Вітні вищий приблизно в три рази від межі, яку Могар назвав у своїй гіпотезі.

== Див. також ==
* [[Граф Брауера — Хемерса]]

== Посилання ==
{{примітки|2}}

== Література ==
* {{Стаття|author=Baker, R. D.; Ebert, G. L.; Hemmeter, J.; Woldar, A. J.|title=Maximal cliques in the Paley graphs of square order|видання=J. Statist. Plann. Inference|том=56|date=1996|pages=33–38|doi=10.1016/S0378-3758(96)00006-7}}
* {{Стаття|doi=10.1080/16073606.1988.9631945|author=Broere, I.; Döman, D.; Ridley, J. N.|title=The clique numbers and chromatic numbers of certain Paley graphs|видання=Quaestiones Mathematicae|том=11|date=1988|pages=91–93}}

== Посилання ==
* {{Cite web|last=Brouwer, Andries E.|title=Paley graps|url=http://www.win.tue.nl/~aeb/drg/graps/Paley.html|deadurl=404}}{{Недоступне посилання|date=Июнь 2018|bot=InternetArchiveBot}}
* {{Cite web|last=Mohar, Bojan|title=Genus of Paley graps|year=2005|url=http://www.fmf.uni-lj.si/~mohar/Problems/P0506_ PaleyGenus.html}}{{Недоступне посилання|date=Сентябрь 2018|bot=InternetArchiveBot}}
{{Бібліоінформація}}
[[Категорія:Сильно регулярні графи]]
[[Категорія:Графи, що мають власну назву]]
[[Категорія:Теорія чисел]]
[[Категорія:Параметричні сімейства графів]]