Два-граф

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

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

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

Приклади

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

123  124  135  146  156  236  245  256  345  346

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Література

• 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) — ISBN 978-0-521-42385-4.
• Charles J. Colbourn, Jeffrey H. Dinitz. Handbook of Combinatorial Designs. — 2nd. — Boca Raton : Chapman & Hall/ CRC, 2007. — С. 875—882. — ISBN 1-58488-506-8.
• 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).