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

{{Граф
 | name = Граф Гофмана — Синглтона
 | image = [[File:Hoffman-Singleton graph.svg|200px]]
 | namesake = {{Нп|Алан Гофман|||Alan J. Hoffman}}<br/>[[Роберт Синглтон]]
 | vertices = 50
 | edges = 175
 | automorphisms = {{formatnum:252000}}<br>([[Projective special unitary group|PSU]](3,5<sup>2</sup>):2)<ref>Hafner, P. R. "The Hoffman-Singleton Graph and Its Automorphisms." J. Algebraic Combin. 18, 7-12, 2003.</ref>
 | chromatic_number = 4
 | chromatic_index = 7<ref>Royle, G. "Re: What is the Edge Chromatic Number of Hoffman-Singleton?" GRAPHNET@istserv.nodak.edu posting. Sept. 28, 2004. [http://listserv.nodak.edu/scripts/wa.exe?A2=ind0409&L=graphnet&F=&S=&P=4981.]{{Недоступне посилання}}</ref>
 | girth = 5<ref name="MW">{{MathWorld|urlname=Hoffman-SingletonGraph|title=Hoffman-Singleton Graph}}</ref>
 | diameter = 2<ref name="MW"/>
 | radius = 2
 | properties = [[Сильно регулярний граф|Сильно регулярний]]<br>[[Симетричний граф|Симетричний]]<br>[[Гамільтонів граф|Гамільтонів]]<br>[[Цілий граф|Цілий]]<br>[[Клітка (теорія графів)|Клітка]]<br>[[Граф Мура]]
}}

[[Файл:Hoffman_singleton_graph_circle2.gif|міні|250x250пкс|Граф Гофмана&nbsp;— Синглтона. Підграф синіх ребер є сумою десяти неперетинних п'ятикутників.]]

У [[Математика|математичній]] [[Теорія графів|теорії графів]], '''граф Гофмана&nbsp;— Синглтона''' це 7-[[Регулярний граф|регулярнимй]] [[Граф (математика)|неорієнтованимй граф]]<nowiki/> зі 50 вершинами і 175 ребрами. Це єдиний [[сильно регулярний граф]] із параметрами (50,7,0,1)<ref>{{citation|title=Hoffman-Singleton graph|url=http://www.win.tue.nl/~aeb/drg/graphs/Hoffman-Singleton.html|author=Brouwer, Andries E.|authorlink=Андріс Броувер|accessdate=5 грудня 2016|archive-date=3 березня 2016|archive-url=https://web.archive.org/web/20160303173424/http://www.win.tue.nl/~aeb/drg/graphs/Hoffman-Singleton.html}}.</ref>. Його побудували {{Нп|Алан Гофман||en|Alan J. Hoffman}} і Роберт Синглтон, коли намагалися класифікувати всі [[Граф Мура|графи Мура]], він є графом Мура з найвищим порядком, для якого відомо, що граф існує<ref>{{citation|title=Moore graphs with diameter 2 and 3|url=http://www.research.ibm.com/journal/rd/045/ibmrd0405H.pdf|year=1960|last1=Hoffman|last2=Singleton|first1=Alan J.|first2=Robert R.|journal=IBM Journal of Research and Development|volume=5|issue=4|pages=497–504|doi=10.1147/rd.45.0497|mr=0140437|accessdate=5 грудня 2016|archive-date=18 травня 2008|archive-url=https://web.archive.org/web/20080518053636/http://www.research.ibm.com/journal/rd/045/ibmrd0405H.pdf}}.</ref>. Оскільки це граф Мура, в якому кожна вершина має степінь 7, а [[Обхват (теорія графів)|обхват]] 5, тоді він є (7,5)-[[Клітка (теорія графів)|кліткою]].

== Побудова ==
Тут наведено дві побудови графа Гофмана&nbsp;— Синглтона.<ref name="vi">{{citation|last=Baez|first=John|title=Hoffman–Singleton Graph|date=1 лютого 2016|url=http://blogs.ams.org/visualinsight/2016/02/01/hoffman-singleton-graph/|authorlink=Джон Баес|work=Visual Insight|publisher=American Mathematical Society|accessdate=5 грудня 2016|archive-date=14 листопада 2016|archive-url=https://web.archive.org/web/20161114063729/http://blogs.ams.org/visualinsight/2016/02/01/hoffman-singleton-graph/}}</ref>

=== Побудова з п'ятикутників та пентаграм ===
Візьміть п'ять [[п'ятикутник]]ів&nbsp;''P<sub>h</sub>'' і п'ять [[Пентаграма|пентаграми]] ''Q<sub>i</sub>'', так щоб вершина ''j'' з ''P<sub>h</sub>'' була суміжною з вершинами ''j''−1 та ''j''+1 з ''P<sub>h</sub>'' і вершина ''j'' з ''Q<sub>i</sub>'' &nbsp;була суміжною з вершинами ''j''−2 та ''j''+2 з ''Q<sub>i</sub>''. Тепер приєднайте вершину ''j'' з ''P<sub>h</sub>'' до вершини ''h''·''i''+''j'' з ''Q<sub>i</sub>''. (Всі індекси за модулем 5.)<ref name="vi" />

=== Побудова з площин Фано ===
Будь-яку множину зі семи точок (як абстрактних математичних об'єктів) можна перетворити на [[Площина Фано|площину Фано]], додавши сім ліній на них. Кількість різних способів зробити це&nbsp;— 30 = 7!/168. Тут 7!&nbsp;— це число [[Перестановка|перестановок]] із семи точок. 168&nbsp;— число&nbsp;симетрій площини Фано, і, як наслідок, кількість перестановок, які зберігають будь-який заданий набір ліній, які утворюють площину Фано. Серед цих 30 різних площин Фано, кожна підмножина трьох точок використовується як лінія в 6 з 30 площин. Для будь-якої з цих 30 площин Фано, є 14 інших, які розділяють принаймні один рядок з ними.

Також сама множина з семи точок теж має 35 різних підмножин, які складаються з трьох елементів («тріад»), підрахованих за допомогою [[Біноміальний коефіцієнт|біноміального коефіцієнта]] <math>\tbinom{7}{3}=35</math>.

Граф Гофмана&nbsp;— Синглтона в такому разі можна побудувати з двох множин вершин:
* по одній&nbsp;для кожної площини Фано в наборі з 15 площин, які формуються вибором однієї довільної і 14 інших, які розділяють лінію з ним, та
* по одній для кожної тріади.

Ці вершини з'єднані ребрами двох типів:
* між кожною вибраною площиною Фано і 7 тріад, які відповідають її лінії, та
* між тріадами зі спільних точок.<ref name="vi" />

== Алгебраїчні властивості ==
Група [[Автоморфізм|автоморфізмів графа]] Гофмана&nbsp;— Синглтона є групою порядку 252 000 ізоморфною PΣU(3,5<sup>2</sup>) [[Напівпрямий добуток|напівпрямому добутку]] {{Нп|Проєктивна спеціальна унітарна група|проєктивної спеціальної унітарної групи||Projective unitary group}} PSU(3,5<sup>2</sup>) з циклічною групою порядку 2, породженої автоморфізму Фробеніуса. Він діє транзитивно на вершини, ребра і дуги графа. Тому граф Гофмана&nbsp;— Синглтона [[симетричний граф]]. Стабілізатор вершини графа є ізоморфом [[Симетрична група|симетричної групи]] S<sub>7</sub> по 7 букв. Стабілізатор множини ребер ізоморфний Aut(A<sub>6</sub>)=A<sub>6</sub>.2<sup>2</sup>, де A<sub>6</sub> є [[Знакозмінна група|знакозмінною групою]] по 6 букв. Обидва з цих двох типів стабілізаторів є максимальними підгрупами всієї групи автоморфізмів графа Гофмана&nbsp;— Синглтона.

[[Характеристичний поліном]] графа Гофмана&nbsp;— Синглтона дорівнює <math>(x-7) (x-2)^{28} (x+3)^{21}</math>. Тому граф Гофмана&nbsp;— Синглтона є інтегральним графом: його [[Спектральна теорія графів|спектр]] повністю складається з цілих чисел.

== Підграфи ==
Використовуючи тільки той факт, що граф Гофмана&nbsp;— Синглтона є сильно регулярним графом із параметрами (50,7,0,1), можна показати, що існує 1260 5-циклів, що містяться у графі Гофмана&nbsp;— Синглтона.

Крім того, граф Гофмана&nbsp;— Синглтона містить 525 копій [[Граф Петерсена|графа Петерсена]]. Видалення будь-якого одного з них залишає копію унікальної (6,5)-клітки.<ref>{{cite journal|last=Wong|first=Pak-Ken|title=On the uniqueness of the smallest graph of girth 5 and valency 6|journal=[[Journal of Graph Theory]]|volume=3|pages=407–409|doi=10.1002/jgt.3190030413}}</ref>

== Див. також ==
* [[Задача степеня — діаметра]]
* {{Нп|Таблиця найбільших відомих графів заданого діаметра і максимального степеня|||Table of the largest known graphs of a given diameter and maximal degree}}
* [[Граф Гофмана]]

== Примітки ==
{{reflist}}

== Посилання ==
* {{Citation|title=On a graph of Hoffman and Singleton|year=1971|last1=Benson|last2=Losey|first1=C. T.|first2=N. E.|journal=Journal of Combinatorial Theory. Series B|volume=11|issue=1|pages=67–79|doi=10.1016/0095-8956(71)90015-3|issn=0095-8956|mr=0281658}}
* {{citation|title=The Petersen graph|year=1993|last1=Holton|last2=Sheehan|first1=D.A.|first2=J.|pages=186 and 190|publisher=[[Cambridge University Press]]|isbn=0-521-43594-3}}.

{{DEFAULTSORT:Гофмана — Синглтона граф}}
[[Категорія:Графи, що мають власну назву]]
[[Категорія:Сильно регулярні графи]]