Zobecněný mnohoúhelník - Generalized polygon - Wikipedia

Rozdělený Cayley šestiúhelník řádu 2

v matematika, a zobecněný polygon je struktura výskytu představil Jacques prsa v roce 1959. Zobecněno n-gony zahrnují jako zvláštní případy projektivní roviny (zobecněné trojúhelníky, n = 3) a zobecněné čtyřúhelníky (n = 4). Mnoho zobecněných polygonů vychází z skupiny typu Lie, ale existují i exotické, které takto získat nelze. Zobecněné polygony splňující technický stav známý jako Moufang vlastnictví byly kompletně klasifikovány Tits a Weissem. Každý zobecnil n- s n dokonce je také blízko mnohoúhelníku.

Definice

Zobecněný 2-gon (nebo digon) je struktura výskytu s alespoň 2 body a 2 liniemi, kde každý bod dopadá na každou linii.

Pro ${ displaystyle n geq 3}$ zobecněný n-gon je struktura výskytu ( ${ displaystyle P, L, I}$ ), kde ${ displaystyle P}$ je množina bodů, ${ displaystyle L}$ je sada řádků a ${ displaystyle I subseteq P krát L}$ je vztah výskytu takové, že:

Je to částečný lineární prostor.
Nemá to obyčejné m-gony jako subgeometrie pro ${ displaystyle 2 leq m$ .
Má to obyčejné n-gon jako subgeometrie.
Pro všechny ${ displaystyle {A_ {1}, A_ {2} } subseteq P cup L}$ existuje subgeometrie ( ${ displaystyle P ', L', I '}$ ) izomorfní s obyčejným n- takhle ${ displaystyle {A_ {1}, A_ {2} } subseteq P ' cup L'}$ .

Ekvivalentní, ale někdy jednodušší způsob, jak vyjádřit tyto podmínky, je: zvažte bipartitní graf výskytu se sadou vrcholů ${ displaystyle P cup L}$ a hrany spojující dopadající páry bodů a čar.

The obvod grafu incidence je dvojnásobek průměr n grafu výskytu.

Z toho by mělo být zřejmé, že grafy dopadu zobecněných polygonů jsou Mooreovy grafy.

Zobecněný mnohoúhelník je řádu (Svatý) li:

všechny vrcholy grafu dopadu odpovídající prvkům ${ displaystyle L}$ mít stejný titul s + 1 pro nějaké přirozené číslo s; jinými slovy, každý řádek obsahuje přesně s + 1 bod,
všechny vrcholy grafu dopadu odpovídající prvkům ${ displaystyle P}$ mít stejný titul t + 1 pro nějaké přirozené číslo t; jinými slovy, každý bod leží přesně na t + 1 řádek.

Říkáme, že zobecněný mnohoúhelník je tlustý, pokud každý bod (čára) dopadá alespoň na tři čáry (body). Všechny tlusté zobecněné polygony mají objednávku.

Dvojník generalizovaného n-gon ( ${ displaystyle P, L, I}$ ), je struktura dopadu s pojmem obrácených bodů a čar a vztahem dopadu se rozumí konverzní vztah z ${ displaystyle I}$ . Lze snadno ukázat, že se jedná opět o zobecněný n-gon.

Příklady

Graf výskytu zobecněného digonu je a kompletní bipartitní graf K._s+1,t+1.
Pro každou přirozenou n ≥ 3, zvažte hranici obyčejnosti polygon s n strany. Deklarujte vrcholy mnohoúhelníku jako body a strany jako přímky, přičemž jako incidenční vztah nastavte zařazení. To má za následek zobecnění n-gon s s = t = 1.
Pro každého skupina typu Lie G 2. úrovně je přidružený generalizovaný n-gon X s n rovna 3, 4, 6 nebo 8 takovým G působí přechodně na sadu příznaků X. V konečném případě pro n = 6, jeden získá Split Cayley šestiúhelník řádu (q, q) pro G₂(q) a zkroucený šestiúhelník řádu (q³, q) pro ³D₄(q³), a pro n = 8, jeden získá osmiúhelník Ree-Tits řádu (q, q²) pro ²F₄(q) s q = 2²ⁿ⁺¹. Až do duality jsou to jediné známé tlusté konečné zobecněné šestiúhelníky nebo osmiúhelníky.

Omezení parametrů

Walter Feit a Graham Higman dokázal to konečný zobecněný n-gony objednávky (s, t) ss ≥ 2, t ≥ 2 může existovat pouze pro následující hodnoty n:

2, 3, 4, 6 nebo 8.

Zobecněné „n“ -gony pro tyto hodnoty se označují jako zobecněné digony, trojúhelníky, čtyřúhelníky, šestiúhelníky a osmiúhelníky.

Když je Feit-Higmanova věta kombinována s Haemers-Roosovými nerovnostmi, dostaneme následující omezení,

Li n = 2, graf dopadu je úplný bipartitní graf, a proto „s“, „t“ mohou být libovolná celá čísla.
Li n = 3, struktura je konečná projektivní rovina, a s = t.
Li n = 4, struktura je konečná zobecněný čtyřúhelník, a t^1/2 ≤ s ≤ t².
Li n = 6, tedy Svatý je náměstí, a t^1/3 ≤ s ≤ t³.
Li n = 8, tedy 2 je čtverec a t^1/2 ≤ s ≤ t².
Li s nebo t je povoleno být 1 a struktura není obyčejná n-gon pak kromě hodnot n již uvedeno, pouze n = 12 může být možné.

Každý známý konečný zobecněný šestiúhelník řádu (s, t) pro s, t > 1 má objednávku

(q, q): rozdělené šestiúhelníky Cayley a jejich duály,
(q³, q): zkroucený šestihran testity, nebo
(q, q³): šestiúhelník se dvěma zkroucenými pokusy,

kde q je hlavní síla.

Každý známý konečný zobecněný osmiúhelník řádu (s, t) pro s, t > 1 má objednávku

(q, q²): osmiúhelník Ree-Tits nebo
(q², q): duální osmiúhelník Ree-Tits,

kde q je zvláštní síla 2.

Poloviční konečné polygony

Li s a t jsou oba nekonečné, pak pro každý existují zobecněné polygony n větší nebo rovno 2. Není známo, zda existují nebo neexistují zobecněné polygony s jedním z parametrů konečný (a větší než 1) zatímco druhý nekonečný (tyto případy se nazývají semi-konečný). Peter Cameron prokázal neexistenci semi-konečných zobecněných čtyřúhelníků se třemi body na každém řádku, zatímco Andries Brouwer a Bill Kantor nezávisle prokázali případ čtyř bodů na každé linii. Výsledek neexistence pěti bodů na každém řádku prokázal G. Cherlin pomocí Teorie modelu.^[1] Žádné takové výsledky nejsou známy, aniž by byly vytvořeny další předpoklady pro zobecněné šestiúhelníky nebo osmiúhelníky, a to ani pro nejmenší případ tří bodů na každém řádku.

Kombinatorické aplikace

Jak bylo uvedeno výše, grafy výskytu zobecněných polygonů mají důležité vlastnosti. Například každý zobecněný n-gon objednávky (s, s) je (s + 1,2n) klec. Jsou také příbuzní expandérové grafy protože mají pěkné expanzní vlastnosti.^[2] Několik tříd grafů extremálních expandérů je získáno z generalizovaných polygonů.^[3] v Ramseyova teorie, grafy zkonstruované pomocí zobecněných polygonů nám dávají některé z nejznámějších konstruktivních dolních mezí na mimo diagonálních Ramseyových číslech.^[4]

Viz také

Reference

^ Cherlin, Gregory (2005). „Lokálně konečné zobecněné čtyřúhelníky s maximálně pěti body na řádek“. Diskrétní matematika. 291 (1–3): 73–79. doi:10.1016 / j.disc.2004.04.021.
^ Tanner, R. Michael (1984). "Explicitní koncentrátory zobecněných N-Gons". SIAM Journal o algebraických a diskrétních metodách. 5 (3): 287–293. doi:10.1137/0605030. hdl:10338.dmlcz / 102386.
^ Nozaki, Hiroshi (2014). Msgstr "Hranice lineárního programování pro běžné grafy". arXiv:1407.4562 [math.CO ].
^ Kostochka, Alexandr; Pudlák, Pavel; Rödl, Vojtech (2010). "Některé konstruktivní limity na Ramseyho čísla". Journal of Combinatorial Theory, Series B. 100 (5): 439–445. doi:10.1016 / j.jctb.2010.01.003.

Godsil, Chris; Royle, Gordone (2001), Algebraická teorie grafů, Postgraduální texty z matematiky, 207, New York: Springer-Verlag, doi:10.1007/978-1-4613-0163-9, ISBN 978-0-387-95220-8, PAN 1829620.
No tak, Waltere; Higman, Graham (1964), „Neexistence určitých zobecněných polygonů“, Journal of Algebra, 1 (2): 114–131, doi:10.1016/0021-8693(64)90028-6, PAN 0170955.

Haemers, W. H .; Roos, C. (1981), „Nerovnost pro zobecněné šestiúhelníky“, Geometriae Dedicata, 10 (1–4): 219–222, doi:10.1007 / BF01447425, PAN 0170955.

Kantor, W. M. (1986). "Zobecněné polygony, SCAB a GAB". Budovy a geometrie diagramů. Přednášky z matematiky. 1181. Springer-Verlag, Berlín. str. 79–158. CiteSeerX 10.1.1.74.3986. doi:10.1007 / BFb0075513. ISBN 978-3-540-16466-1.

Van Maldeghem, Hendrik (1998), Zobecněné polygonyMonografie z matematiky, 93, Basilej: Birkhäuser Verlag, doi:10.1007/978-3-0348-0271-0, ISBN 978-3-7643-5864-8, PAN 1725957.
Stanton, Dennis (1983), „Generalized n-gons a Chebychev polynomials ", Journal of Combinatorial Theory, Řada A, 34 (1): 15–27, doi:10.1016/0097-3165(83)90036-5, PAN 0685208.
Kozy, Jacques; Weiss, Richard M. (2002), Mufangové polygonySpringer Monografie z matematiky, Berlín: Springer-Verlag, ISBN 978-3-540-43714-7, PAN 1938841.

[1] Cherlin, Gregory (2005). „Lokálně konečné zobecněné čtyřúhelníky s maximálně pěti body na řádek“. Diskrétní matematika. 291 (1–3): 73–79. doi:10.1016 / j.disc.2004.04.021.

[2] Tanner, R. Michael (1984). "Explicitní koncentrátory zobecněných N-Gons". SIAM Journal o algebraických a diskrétních metodách. 5 (3): 287–293. doi:10.1137/0605030. hdl:10338.dmlcz / 102386.

[3] Nozaki, Hiroshi (2014). Msgstr "Hranice lineárního programování pro běžné grafy". arXiv:1407.4562 [math.CO ].

[4] Kostochka, Alexandr; Pudlák, Pavel; Rödl, Vojtech (2010). "Některé konstruktivní limity na Ramseyho čísla". Journal of Combinatorial Theory, Series B. 100 (5): 439–445. doi:10.1016 / j.jctb.2010.01.003.

[1]

[2]

[3]

[4]