Generaliserad polygon

Den generaliserade polygonen är en incidensstruktur som föreslogs av Jacques Tits 1959. Generaliserade n -goner inkluderar projektiva plan (generaliserade trianglar, n =3) och generaliserade fyrhörningar ( n =4) som specialfall . Många generaliserade polygoner erhålls från Lie-grupper , men det finns några exotiska generaliserade polygoner som inte erhålls på detta sätt. Generaliserade polygoner som uppfyller ett villkor som kallas Moufang-egenskapen klassificeras helt av Tits och Weiss. Varje generaliserad n -gon med jämn n är också en nära-polygon .

Definition

En generaliserad 2 -gon (dygon) är en infallsstruktur med minst 2 punkter och 2 linjer, där varje punkt faller in mot varje linje.

För en generaliserad n -gon är detta incidensstrukturen ( ), där är mängden punkter, är mängden linjer och är incidensrelationen , så att: $n\geq 3$ $P,L,I$ $P$ $L$ $I\subseteq P\times L$

Detta är ett delvis linjärt utrymme.
Den har inte de vanliga m -gonerna som subgeometri för . $2\leq m<n$
Den har inte de vanliga n -gonerna som subgeometri.
För alla finns det en subgeometri ( ) som är isomorf till en n -gon sådan att . $\{A_{1},A_{2}\}\subseteq P\cup L$ $P',L',I'$ $\{A_{1},A_{2}\}\subseteq P'\cup L'$

Ett likvärdigt men ibland enklare sätt att uttrycka dessa termer är följande. Ta en tvådelad infallsgraf med många hörn och kanter som förbinder par av punkter och linjer. $P\cup L$

Omkretsen på incidensgrafen är dubbelt så stor som diametern n av incidensgrafen.

Härifrån bör det vara klart att incidensgraferna för generaliserade polygoner är Moore-grafer .

En generaliserad polygon har ordning (s,t) if

alla hörn av incidensgrafen som motsvarar element av har samma grad s + 1 för vissa naturliga tal s . Med andra ord, vilken linje som helst innehåller exakt s + 1 poäng, $L$
alla hörn av incidensgrafen som motsvarar element av har samma grad t + 1 för något naturligt tal t . Med andra ord, vilken punkt som helst ligger på exakt t + 1 linjer. $P$

Vi säger att en generaliserad polygon är tjock om någon punkt (linje) faller samman med minst tre linjer (punkter). Alla tjocka generaliserade polygoner har ordning.

Dualen för den generaliserade n - gon ( ) är incidensstrukturen, där punkter och linjer byter roll, respektive incidensrelationen blir invers till relationen. Det kan lätt visas att den dubbla strukturen också är en generaliserad n -gon. $P,L,I$ $jag$

Exempel

Incidensgrafen för en generaliserad digon är en komplett tvådelad graf K s +1, t +1 .
För alla naturliga tal n ≥ 3 tar vi gränsen för en vanlig polygon med n sidor. Låt oss förklara polygonens hörn som punkter och sidorna som raka linjer. Incidensrelationen är naturlig. Vi får en generaliserad n -gon med s = t = 1.
För varje grupp G av Lie typ av rang 2, finns det en associerad generaliserad n -gon X med n lika med 3, 4, 6 eller 8 så att G agerar transitivt på uppsättningen av flaggor X . I det sista fallet, för n=6 , kan man få en bruten Cayley-hexagon av ordningen ( q , q ) för G 2 ( q ) och en vriden trippel hexagon av ordningen ( q 3 , q ) för 3 D 4 ( q 3 ) , och för n=8 får vi en Ree-Tits-oktagon av ordningen ( q , q 2 ) för 2 F 4 ( q ) med q =2 2 n +1 . Upp till dualitet är endast ändliga tjocka generaliserade hexagoner och oktagoner kända.

Parametergräns

Walter Veit [1] och Graham Higman bevisade att finita generaliserade n -goner av ordning ( s , t ) med s ≥ 2, t ≥ 2 endast kan existera för följande värden på n :

2, 3, 4, 6 eller 8.

Generaliserade "n"-goner för dessa värden kallas generaliserade digoner (digoner), trianglar, fyrhörningar, hexagoner och oktagoner.

Om vi kombinerar Veit-Higman-satsen med Hemers-Roos-ojämlikheterna får vi följande begränsningar,

Om n = 2 är incidensgrafen en komplett tvådelad graf, och "s" och "t" kan vara godtyckliga heltal.
Om n =3 är strukturen ett ändligt projektivt plan och s = t .
Om n =4 är strukturen en finit generaliserad fyrhörning och t 1/2 ≤ s ≤ t 2 .
Om n =6 är st en kvadrat och t 1/3 ≤ s ≤ t 3 .
Om n =8 är 2st en kvadrat och t 1/2 ≤ s ≤ t 2 .
Om s eller t är 1 och strukturen inte är en vanlig n -gon, är, förutom värdena på n listade ovan , endast värdet n =12 möjligt.

Varje känd ändlig generaliserad hexagon av ordning ( s , t ) för s , t > 1 har ordning

( q , q ) är uppdelade Cayley-hexagoner och deras dubbla,
( q 3 , q ) är en vriden trippel hexagon, eller
( q , q 3 ) är den dubbeltvinnade trippelhexagonen,

där q är potensen av ett primtal.

Alla kända generaliserade oktagoner av ordning ( s , t ) för s , t > 1 har ordning

( q , q 2 ) är Ree-Tits-oktagonen, eller
( q 2 , q ) är dualen av Ree-Tits-oktagonen,

där q är en udda potens av 2.

Semifinita generaliserade polygoner

Om båda talen, s och t , är oändliga, existerar generaliserade polygoner för alla n större än eller lika med 2. Det är inte känt om det finns generaliserade polygoner för vilka en av parametrarna är ändlig (och större än 1 ) och andra är oändligt (dessa polygoner kallas semi -ändliga ). Peter Cameron bevisade att halvändliga generaliserade fyrhörningar med tre punkter på varje linje inte existerar. Endres Brewer och Bill Kantor oberoende bevisade icke-existens för fyra poäng på en linje. Icke-existensen av generaliserade fyrhörningar för fem punkter på varje linje bevisades av G. Cherlin med hjälp av teorin om modeller [2] . Inga andra resultat är kända utan att göra några ytterligare antaganden om generaliserade hexagoner eller oktagoner, även för det minsta fallet med tre punkter på varje linje.

Kombinatoriska applikationer

Som noterats ovan har incidensgraferna för generaliserade polygoner viktiga egenskaper. Till exempel är vilken generaliserad n -gon som helst av ordning (s, s) en (s+1,2n) cell . De är också relaterade till expanderare då de har goda expansionsegenskaper [3] . Vissa klasser av extrema expanderare erhålls från generaliserade polygoner [4] . I Ramsey-teorin ger grafer konstruerade med hjälp av generaliserade polygoner några bättre nedre gränser för off-diagonala Ramsey-tal [5] .

Se även

Struktur (matematik)
Par (B, N)
Ree grupp
Moufang plan
Nästan polygon

Anteckningar

↑ Som tyskt läses efternamnet Feit Veit , men eftersom Veit emigrerade till USA kan läsningen av hans efternamn där vara annorlunda.
↑ Lokalt ändliga generaliserade fyrkanter med högst fem pekar per linje . Hämtad 20 augusti 2017. Arkiverad från originalet 29 juli 2021. (obestämd)
↑ Explicita koncentratorer från generaliserade N -Gons | SIAM Journal om algebraiska diskreta metoder | Vol. 5, nr. 3 | Föreningen för industriell och tillämpad matematik
↑ Arkiverad kopia . Hämtad 20 augusti 2017. Arkiverad från originalet 22 augusti 2017. (obestämd)
↑ Samma Ramsey-nummer gränsar Arkiverad 29 juli 2021 på Wayback Machine , erhållen av Kostochka, Pudlak och Rödl.

Litteratur

Godsil Chris, Royle Gordon. Algebraisk grafteori. - New York: Springer-Verlag, 2001. - Vol 207. - (Graduate Texts in Mathematics). — ISBN 0-387-95220-9 . - doi : 10.1007/978-1-4613-0163-9 .
Feit Walter, Higman Graham. Att vissa generaliserade polygoner inte finns // Journal of Algebra. - 1964. - T. 1 . — S. 114–131 . - doi : 10.1016/0021-8693(64)90028-6 .
Haemers WH, Roos C. En ojämlikhet för generaliserade hexagoner // Geometriae Dedicata. - 1981. - T. 10 . - S. 219-222 . - doi : 10.1007/BF01447425 .
Kantor WM Generaliserade polygoner, SCABs och GABs // Buildings and the Geometry of Diagrams . - Springer-Verlag, Berlin, 1986. - T. 1181. - S. 79-158. — (Föreläsningsanteckningar i matematik).
Van Maldeghem Hendrik. Generaliserade polygoner. - Basel: Birkhäuser Verlag, 1998. - Vol. 93. - (Monographs in Mathematics). — ISBN 3-7643-5864-5 . - doi : 10.1007/978-3-0348-0271-0 .
Stanton Dennis. Generaliserade n -goner och Chebychev-polynom // Journal of Combinatorial Theory . - 1983. - T. 34 . — S. 15–27 . - doi : 10.1016/0097-3165(83)90036-5 .
Tits Jacques, Weiss Richard M. Moufang polygoner. - Berlin: Springer-Verlag, 2002. - (Springer Monographs in Mathematics). — ISBN 3-540-43714-2 .