Два-граф

У математиці два-граф це (невпорядкована) множина трійок, вибраних зі скінченної множини вершин 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\}$ у графі

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

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

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

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

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

Перемикання $G$ і $\mathrm{\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$ прямих, на яких лежать ці вектори, дорівнює $\varphi$, де $\cos \varphi =1/\rho$. Навпаки, будь-яка множина неортогональних прямих у евклідовому просторі, кут між будь-якою парою яких однаковий, дає два-граф.

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

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

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

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

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

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

Література

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття