Tvåräkning

I matematik är en tvågraf en (oordnad) uppsättning trippel vald från en ändlig uppsättning av hörn X på ett sådant sätt att alla (oordnade) fyra i X innehåller ett jämnt antal valda tvågrafiska trippel. I en vanlig (homogen) tvågraf ligger vilket par av hörn som helst i samma antal tripletter av tvågrafen. Två-grafer studeras för deras koppling med ekvikantiga linjer , kopplingen av vanliga två-grafer med starkt regelbundna grafer , och även för kopplingen av vanliga två-grafer med ändliga grupper , eftersom många av dessa grafer har intressanta automorfismgrupper .

Två-grafer är inte grafer och bör inte förväxlas med andra objekt som kallas 2-grafer i grafteorin , i synnerhet 2-reguljära grafer . För att skilja mellan dem används ordet "två", inte siffran "2" [1] .

Tvågrafer introducerades av G. Higman som naturliga objekt som uppstår när man arbetar med några enkla grupper. Sedan dess har de studerats intensivt av Seidel, Taylor och andra i studiet av uppsättningar av ekvikantiga linjer, starkt regelbundna grafer och andra objekt [2] [1] .

Exempel

På vertexuppsättningen {1, ..., 6} är följande oordnade uppsättning trippel en tvågraf:

123 124 135 146 156 236 245 256 345   346

Denna två-graf är regelbunden eftersom varje par av distinkta hörn hamnar tillsammans i exakt två trippel.

Givet en vanlig graf G = ( V ,  E ), så bildar en uppsättning trippel av hörn i V vars genererade subgraf har ett udda antal kanter en två-graf på V . Alla två grafer kan representeras i denna form [3] . Det här exemplet visar standardsättet att bygga en tvågraf från en normal graf.

Låt oss ta ett mer komplicerat exempel. Låt T vara ett träd med kantmängd E . Mängden av alla trillingar av kanter som inte ligger på samma bana i T bildar en tvågraf på mängden E . [4] [5]

Växling och grafer

Två-grafen är ekvivalent med växlingsklassen av grafer, såväl som (signerade) växlingsklassen av signerade kompletta grafer .

Att byta uppsättningen av hörn i en (vanlig) graf innebär att man ändrar närgränsen för varje par av hörn, varav den ena är i mängden och den andra inte är i mängden - det intilliggande paret blir icke-intilliggande och det icke-angränsande paret blir angränsande. Kanter vars ändpunkter är i uppsättningen, eller båda ändpunkterna är utanför uppsättningen, ändras inte. Grafer är växlingslikvärdiga om den ena kan erhållas från den andra genom att växla. Switching ekvivalensklassen kallas switching class . Switching introducerades av van Lint och Seidel ( van Lint, Seidel 1966 ) och utvecklades av Seidel. Namnet grafväxling eller Seidelväxling introducerades, delvis för att skilja det från signerad grafväxling .

I standardkonstruktionen av två grafer från en vanlig graf som ges ovan, ger två grafer samma tvågraf om och endast om de är växlande ekvivalenta, det vill säga de tillhör samma kopplingsklass.

Låt Γ vara en tvågraf på en mängd X . För alla element x från X definierar vi en vertexuppsättningsgraf X där hörnen y och z ligger intill om och endast om { x , y , z } tillhör Γ. I denna graf kommer x att vara en isolerad vertex. Denna konstruktion är vändbar. Givet en vanlig graf G , lägg till ett nytt element x till vertexmängden G och definiera en tvågraf så att alla trippel { x , y , z } har y och z intilliggande hörn i G . Denna två-graf i flödesschemaspråk kallas förlängningen av grafen G med vertex x . [1] I en given växlingsklass av en vanlig tvågraf, låt Γ x vara den enda grafen som har vertex x som en isolerad vertex (en finns alltid, du behöver bara ta vilken graf som helst i klassen och byta relativt icke- intilliggande x hörn), och inkluderar inte själva vertex x . Det vill säga, en tvågraf är en förlängning av Γ x med en vertex x . I det vanliga exemplet med två grafer är Γ x en 5-punktscykel för valfritt x . [6]

Grafen G motsvarar en förtecknad komplett graf Σ på samma uppsättning av hörn, vars kanter är negativa om de tillhör G , och positiva om de inte tillhör G . Omvänt är G en subgraf av Σ och består av alla hörn och negativa kanter. En tvågrafisk G kan också definieras som uppsättningen av tripletter av hörn som bildar en negativ triangel (en triangel med ett udda antal negativa kanter) i Σ. Två signerade kompletta grafer ger samma två-graf om och endast om de byter ekvivalenta.

Omkopplare G och Σ är anslutna — om du byter samma hörn får grafen H och motsvarande förtecknade fullständiga graf.

Adjacency matris

Närliggande matris för en två-graf är närliggande matris motsvarande signerade fullständiga graf. Det vill säga, den är symmetrisk , har nollor på diagonalen och off-diagonala värden är ±1. Om G är en graf som motsvarar en förtecknad komplett graf Σ, kallas denna matris (0, −1, 1) närliggande matris eller Seidel närliggande matris [ av G . Seidelmatrisen har nollor på huvuddiagonalen, −1 för element som motsvarar angränsande hörn och +1 för element som motsvarar icke-angränsande hörn.

Om graferna G och H är i samma omkopplingsklass, sammanfaller multiuppsättningarna av egenvärden för de två Seidel-angränsande matriserna för G och H , eftersom matriserna är lika. [7]

En tvågraf på en mängd V är regelbunden om och endast om dess närliggande matris bara har två distinkta egenvärden , säg ρ 1 > 0 > ρ 2 , där ρ 1 ρ 2 = 1 − | V |. [åtta]

Likvida linjer

Varje tvågraf är ekvivalent med en uppsättning linjer i något flerdimensionellt euklidiskt utrymme , och vinkeln mellan ett par linjer från denna uppsättning är densamma. En uppsättning linjer kan konstrueras från en tvågraf med n hörn enligt följande. Låt −ρ vara det minsta egenvärdet för Seidels närliggande matris A för en tvågraf, och antag att dess multiplicitet är n  −  d . Då är matrisen ρ I  +  A en positiv semidefinitiv matris av rang d , och den kan representeras som grammatrisen av inre produkter av n vektorer i ett euklidiskt utrymme med dimensionen d . Dessa vektorer har också samma norm (nämligen ) och den parvisa skalära produkten ±1, och vinkeln mellan vilket par av n linjer som helst som sträcks av dessa vektorer är lika med φ, där cos φ = 1/ρ. Omvänt ger varje uppsättning icke-ortogonala linjer i det euklidiska rummet, vars vinkel mellan vilket par som helst, en tvågraf [9] .

I notationen ovan uppfyller den maximala kardinaliteten n olikheten n ≤ d (ρ 2 − 1)/(ρ 2 − d ), och gränsen nås om och endast om tvågrafen är regelbunden.

Starkt regelbundna grafer

Två-grafer på X som består av alla möjliga trippel från X och tomma (som inte har några trippel) är vanliga två-grafer, men de anses vanligtvis vara triviala två-grafer och är vanligtvis uteslutna från hänsyn.

En icke-trivial två-graf på en mängd X är regelbunden om och endast om grafen Γ x för något x från X är starkt regelbunden med k = 2μ (graden av en vertex är dubbelt så stor som antalet hörn som gränsar till båda i ett icke-angränsande par av hörn). Om detta villkor är sant för ett x av X , så är det sant för alla element i X. [tio]

Detta innebär att en icke-trivial regelbunden tvågraf har ett jämnt antal hörn.

Om G är en vanlig graf vars utökade två-graf Γ har n hörn, så är Γ en vanlig två-graf om och endast om G är en starkt regelbunden graf med egenvärden k , r och s så att n = 2( k  −  r ) eller n = 2( k  −  s ). [elva]

Anteckningar

  1. ↑ 1 2 3 Cameron, van Lint, 1991 , sid. 58-59.
  2. ↑ G. Eric Moorhouse. Två-grafer och skeva Två-grafer i ändliga geometrier // Linjär algebra och dess tillämpningar. — 1995.
  3. ↑ Colbourn, Dinitz, 2007 , sid. 876, not 13.2.
  4. ↑ P. J. Cameron. Två grafer och träd // Diskret matematik. - 1994. - T. 127 . - S. 63-74 . - doi : 10.1016/0012-365x(92)00468-7 . , som citeras i Colbourn och Dinitz, 2007 , sid. 876, avslutning 13.12.
  5. ↑ Peter J. Cameron. Räkna två grafer relaterade och träd // The Electronic Journal of Combinatorics. - 1995. - T. 2 . — ISSN 1077-8926 .
  6. ↑ Cameron, van Lint, 1991 , sid. 62.
  7. ↑ Cameron, van Lint, 1991 , sid. 61.
  8. ↑ Colbourn, Dinitz, 2007 , sid. 878, #13.24.
  9. ↑ van Lint, Seidel, 1966
  10. ↑ Cameron, van Lint, 1991 , sid. 62, sats 4.11.
  11. ↑ Cameron, van Lint, 1991 , sid. 62, sats 4.12.

Litteratur