Два-граф

У математиці два-граф це (невпорядкована) множина трійок, вибраних зі скінченної множини вершин X таким чином, що будь-яка (невпорядкована) четвірка з ${\displaystyle X}$ містить парне число вибраних трійок два-графа. У регулярному (однорідному) два-графі будь-яка пара вершин лежить у тому самому числі трійок два-графа. Два-графи вивчають через їх зв'язок з рівнокутними прямими, зв'язок регулярних два-графів із сильно регулярними графами, а також через зв'язок регулярних два-графів зі скінченними групами, оскільки багато із цих графів мають цікаві групи автоморфізмів.

Два-графи не є графами, і їх не слід плутати з іншими об'єктами, які називаються 2-графами в теорії графів, зокрема, з 2-регулярними графами. Для їх розрізнення використовують слово «два», а не цифру «2».

Два-графи увів Хіґман як природні об'єкти, що виникають під час роботи з деякими простими групами. Відтоді їх інтенсивно вивчали Зайдель, Тейлор та інші, розглядаючи множини рівнокутних прямих, сильно регулярних графів та інших об'єктів.

Приклади

На множині вершин {1, …, 6} такий невпорядкований набір трійок є два-графом:

123  124  135  146  156  236  245  256  345  346

Цей два-граф є регулярним, оскільки будь-яка пара різних вершин присутня разом рівно в двох трійках.

Якщо дано звичайний граф ${\displaystyle G=(V,E)}$, то набір трійок вершин з ${\displaystyle V}$, у яких породжений підграф має непарне число ребер, утворює два-граф на ${\displaystyle V}$. Будь-який два-граф можна подати в такому вигляді. Цей приклад показує стандартний спосіб побудови два-графа зі звичайного графа.

Наведемо складніший приклад. Нехай ${\displaystyle T}$ — дерево зі множиною ребер ${\displaystyle E}$. Множина всіх трійок ребер, що не лежать на одному шляху в ${\displaystyle T}$ утворюють два-граф на множині ${\displaystyle E}$.

Перемикання та графи

Перемикання ${\displaystyle \{X,Y\}}$ у графі

Два-граф еквівалентний класу перемикання графів, а також (знаковому) класу перемикання ^[en].

Перемикання множини вершин у (звичайному) графі означає змінення суміжності кожної пари вершин, одна з яких у множині, а інша не у множині — суміжна пара стає несуміжною, а несуміжна пара стає суміжною. Ребра, кінцеві вершини яких належать множині, або обидва кінці не алежать множині, не змінюються. Графи є еквівалентними за перемиканням, якщо один можна отримати з іншого перемиканням. Клас еквівалентності за перемиканням називають класом перемикання. Перемикання ввели Ван Лінт і Зайдель (van Lint, Seidel, 1966) і розвинув Зайдель. Назву перемикання графів або перемикання Зайделя введено, зокрема, щоб відрізнити від перемикання ^[en].

У наведеній вище стандартній побудові два-графів зі звичайного графа два графи дають той самий два-граф тоді й лише тоді, коли вони еквівалентні за перемиканням, тобто належать до одного класу перемикання.

Нехай ${\displaystyle \Gamma }$ — два-граф на множині ${\displaystyle X}$. Для будь-якого елемента ${\displaystyle x}$ із ${\displaystyle X}$ визначимо граф із множиною вершин ${\displaystyle X}$, у якому вершини ${\displaystyle y}$ і ${\displaystyle z}$суміжні тоді й лише тоді, коли ${\displaystyle \{x,y,z\}}$ належить ${\displaystyle \Gamma }$. У цьому графі ${\displaystyle x}$ буде ізольованою вершиною. Ця побудова оборотна: візьмемо звичайний граф ${\displaystyle G}$, додамо новий елемент ${\displaystyle x}$ до множини вершин ${\displaystyle G}$, зберігши набір ребер, і скористаємося розглянутою стандартною побудовою. Цей два-граф мовою блок-схем називають розширенням графа ${\displaystyle G}$ вершиною ${\displaystyle x}$.

Графу ${\displaystyle G}$ відповідає знаковий повний граф ${\displaystyle \Sigma }$ на тій самій множині вершин, ребра якого від'ємні, якщо належать ${\displaystyle G}$, і додатні, якщо не належать ${\displaystyle G}$. І навпаки, ${\displaystyle G}$ є підграфом ${\displaystyle \Sigma }$ і складається з усіх вершин та від'ємних ребер. Два-граф ${\displaystyle G}$ можна визначити як множину трійок вершин, які утворюють від'ємний трикутник (трикутник із непарним числом від'ємних ребер) у ${\displaystyle \Sigma }$. Два знакових повних графи дають той самий два-граф тоді й лише тоді, коли вони еквівалентні за перемиканням.

Перемикання ${\displaystyle G}$ і ${\displaystyle \Sigma }$ пов'язані: перемикання тих самих вершин дає граф ${\displaystyle H}$ і відповідний йому знаковий повний граф.

Матриця суміжності

Матриця суміжності два-графа це ^[en] знакового повного графа. Тобто вона симетрична, має нулі на діагоналі, і значення поза діагоналлю дорівнюють ±1. Якщо ${\displaystyle G}$ — граф, який відповідає знаковому повному графу Σ, то цю матрицю називають (0, − 1, 1) матрицею суміжності або ^[en] графа ${\displaystyle G}$. Матриця суміжності Зайделя має нулі на головній діагоналі -1 для елементів, відповідних суміжним вершин, і +1 для елементів, відповідних несуміжним вершинам.

Якщо графи ${\displaystyle G}$ і ${\displaystyle H}$ перебувають у одному класі перемикання, мультимножини власних значень двох матриць суміжності Зайделя для ${\displaystyle G}$ і ${\displaystyle H}$ збігаються, оскільки матриці подібні.

Два-граф на множині ${\displaystyle V}$ є регулярним тоді й лише тоді, коли його матриця суміжності має лише два різних власних значення, скажімо ${\displaystyle \rho _{1}>0>\rho _{2}}$ , де ${\displaystyle \rho _{1}\rho _{2}=1-|V|}$.

Рівнокутні прямі

Будь-який два-граф еквівалентний множині прямих у деякому багатовимірному евклідовому просторі, кут між будь-якою парою прямих з якої однаковий. Множину прямих можна побудувати з два-графа з ${\displaystyle n}$ вершинами в такий спосіб. Нехай ${\displaystyle -\rho }$ — найменше власне значення ^[en] ${\displaystyle A}$ два-графа, і припустимо, що його кратність дорівнює ${\displaystyle n-d}$. Тоді матриця ${\displaystyle \rho I+A}$ є додатно напіввизначеною матрицею рангу ${\displaystyle d}$, і її можна подати як матрицю Грама скалярних добутків ${\displaystyle n}$ векторів у евклідовому просторі розмірності ${\displaystyle d}$. Ці вектори також мають однакову норму (а саме, ${\displaystyle {\sqrt {\rho }}}$) та попарний скалярний добуток ${\displaystyle \pm 1}$, а кут між будь-якою парою з ${\displaystyle n}$ прямих, на яких лежать ці вектори, дорівнює ${\displaystyle \phi }$, де ${\displaystyle \cos \phi =1/\rho }$. Навпаки, будь-яка множина неортогональних прямих у евклідовому просторі, кут між будь-якою парою яких однаковий, дає два-граф.

У позначеннях, наведених вище, найбільша потужність ${\displaystyle n}$ задовольняє нерівності ${\displaystyle n\leq d(\rho ^{2}-1)/(\rho ^{2}-d)}$, і межа досягається тоді й лише тоді, коли два граф регулярний.

Сильно регулярні графи

Два-графи на ${\displaystyle X}$, що складаються з усіх можливих трійок з ${\displaystyle X}$, і порожні (що не мають трійок) є регулярними два-графами, але їх прийнято вважати тривіальними два-графами і, як правило, виключають із розгляду.

Нетривіальний два-граф на множині ${\displaystyle X}$ є регулярним тоді й лише тоді, коли для будь-якого ${\displaystyle x}$ із ${\displaystyle X}$ граф ${\displaystyle \Gamma _{x}}$ є сильно регулярним з ${\displaystyle k=2\mu }$ (степінь будь-якої вершини вдвічі більший за кількість вершин, суміжних обом з будь-якої несуміжної пари вершин). Якщо ця умова виконується для одного ${\displaystyle x}$ із ${\displaystyle X}$, вона виконується для всіх елементів із ${\displaystyle X}$.

Звідси випливає, що нетривіальний регулярний два-граф має парну кількість вершин.

Якщо ${\displaystyle G}$ — регулярний граф, розширений два-граф ${\displaystyle \Gamma }$ якого має ${\displaystyle n}$ вершин, то ${\displaystyle \Gamma }$ є регулярним два-графом тоді й лише тоді, коли ${\displaystyle G}$ є сильно регулярним графом із власними значеннями ${\displaystyle k}$, ${\displaystyle r}$ і ${\displaystyle s}$ для яких виконується ${\displaystyle n=2(k-r)}$ або ${\displaystyle n=2(k-s)}$.

Примітки

1. Cameron, van Lint, 1991, с. 58—59.
2. G. Eric Moorhouse. Two-Graphs and Skew Two-Graphs in Finite Geometries // Linear Algebra and its Applications. — 1995. — 18 червня.
3. Colbourn, Dinitz, 2007, с. 876, примечание 13.2.
4. P. J. Cameron. Two-graphs and trees // Discrete Mathematics. — 1994. — Т. 127 (18 червня). — С. 63—74. — DOI:10.1016/0012-365x(92)00468-7., як процитовано в Colbourn, Dinitz, 2007, с. 876, підсумок 13.12.
5. Peter J. Cameron. Counting two-graphs related and trees // The Electonic Journal of Combinatorics. — 1995. — Т. 2 (18 червня). — ISSN 1077-8926.
6. Cameron, van Lint, 1991, с. 61.
7. Colbourn, Dinitz, 2007, с. 878, #13.24.
8. van Lint, Seidel, 1966
9. Cameron, van Lint, 1991, с. 62, теорема 4.11.
10. Cameron, van Lint, 1991, с. 62, теорема 4.12.

Література

• A. E. Brouwer, A. M. Cohen, A. Neumaier. Параграфи 1.5, 3.8, 7.6C // Distance-Regular Graphs. — Berlin : Springer-Verlag, 1989.
• P. J. Cameron, J. H. van Lint. Designs, Graphs, Codes and their Links. — Cambridge University Press, 1991. — Т. 22. — (London Mathematical Society Student Texts) — .
• Charles J. Colbourn, Jeffrey H. Dinitz. Handbook of Combinatorial Designs. — 2nd. — Boca Raton : Chapman & Hall/ CRC, 2007. — С. 875—882. — .
• Chris Godsil, Gordon Royle. Глава 11 // Algebraic Graph Theory. — New York : Springer-Verlag, 2001. — Т. 207. — (Graduate Texts in Mathematics)
• J. J. Seidel. Colloquio Internazionale sulle Teorie Combinatorie. — Rome, 1973. — Т. I. — С. 481—511.
• D. E. Taylor. Proceedings of the London Mathematical Society. — 1977. — Т. 35. — С. 257—274.
• J. H. van Lint, J. J. Seidel. Equilateral point sets in elliptic geometry // Indagationes Mathematicae. — 1966. — Т. 28. — С. 335—348. — (Proc. Koninkl. Ned. Akad. Wetenschap. Ser. A 69).