Blockeringsset

Inom geometri , specifikt projektiv geometri , är en blockerande uppsättning en uppsättning punkter i ett projektivt plan som varje linje skär och som inte innehåller en hel linje. Begreppet kan generaliseras på flera sätt. Istället för att prata om punkter och linjer skulle man kunna hantera n -dimensionella delrum och m -dimensionella delrum, eller ännu mer allmänt, objekt av typ 1 och objekt av typ 2 när något begrepp av skärningspunkt är vettigt för dessa objekt. Ett andra sätt att generalisera skulle vara att gå in i mer abstrakta miljöer än projektiv geometri. Man kan definiera en blockerande uppsättning av en hypergraf som en uppsättning som möter alla kanter av hypergrafen.

Definition

I ett ändligt projektivt plan π av ordningen n är en blockerande mängd en uppsättning punkter av π som varje linje skär och som inte innehåller någon linje helt. Enligt denna definition, om B är en blockerande uppsättning, då komplementär uppsättning punkter, är π\ B också en blockerande uppsättning. En blockerande uppsättning B är minimal om avlägsnandet av någon punkt på B lämnar en uppsättning som inte är en blockerande uppsättning. En blockerande uppsättning av minsta storlek kallas en kommitté . Varje kommitté är en minimal blockeringsuppsättning, men inte alla minimala blockeringsuppsättningar är kommittéer. Blockeringssatser finns i alla projektiva plan förutom det minsta projektiva planet av ordning 2, Fano-planet .

Det är ibland användbart att släppa villkoret att en blockeringsuppsättning inte innehåller en rad. Under denna utökade definition, och eftersom varje par av linjer möts i ett projektivt plan, skulle varje linje vara en blockerande uppsättning. Blockeringsuppsättningar som innehöll linjer skulle kallas triviala blockeringsuppsättningar, i denna inställning.

Exempel

I vilket projektivt plan som helst av ordning n (varje linje innehåller n + 1 punkter) bildar punkterna på linjerna som bildar en triangel utan triangelns hörn (3( n - 1) punkter) en minimal blockeringsmängd (om n = 2 denna blockeringsuppsättning är trivial) som i allmänhet inte är en kommitté.

En annan allmän konstruktion i ett godtyckligt projektivt plan av ordning n är att ta alla utom en punkt, säg P , på en given linje och sedan en punkt på var och en av de andra linjerna genom P , och se till att dessa punkter inte alla är kolinjära (detta sista villkoret kan inte uppfyllas om n = 2.) Detta ger en minimal blockeringsuppsättning av storlek 2 n .

En projektiv triangel β på sidan m i PG(2, q ) består av 3( m - 1) punkter, m på varje sida av en triangel, så att triangelns hörn A , B och C är i β, och Följande villkor är uppfyllt: Om punkt P på linje AB och punkt Q på linje BC båda är i β, så är skärningspunkten mellan PQ och AC i β.

En projektiv triad δ på sidan m är en uppsättning av 3 m - 2 punkter, varav m ligger på var och en av tre samtidiga linjer så att samtidighetspunkten C är i δ och följande villkor är uppfyllt: Om en punkt P på en av linjerna och en punkt Q på en annan linje är i δ, då är skärningspunkten för PQ med den tredje linjen i δ.

Sats : I PG(2, q ) med q udda, finns det en projektiv triangel med sidan ( q + 3)/2 som är en blockerande uppsättning av storleken 3( q + 1)/2.

Använd homogena koordinater och låt triangelns hörn vara A = (1,0,0), B = (0,1,0) och C = (0,0,1). Punkterna, förutom hörn, på sidan AB har koordinater av formen (- c , 1, 0), de på BC har koordinater (0,1, a ) och de på AC har koordinater (1,0, b ) där a , b och c är element i det finita fältet GF( q ). Tre punkter, en på var och en av dessa sidor, är kolinjära om och endast om a = bc . Genom att välja alla punkter där a , b och c är kvadrater som inte är noll av GF( q ), är villkoret i definitionen av en projektiv triangel uppfyllt.

Sats : I PG(2, q ) med q jämn, finns det en projektiv triad av sidan ( q + 2)/2 som är en blockerande uppsättning av storlek (3 q + 2)/2.

Konstruktionen liknar ovanstående, men eftersom fältet har karakteristik 2 måste kvadrater och icke-kvadrater ersättas med element av absolut spår 0 och absolut spår 1. Låt specifikt C = (0,0,1). Punkter på linjen X = 0 har formens koordinater (0,1, a ), och de på linjen Y = 0 har formens koordinater (1,0, b ). Punkterna på linjen X = Y har koordinater som kan skrivas som (1,1, c ). Tre punkter, en från var och en av dessa linjer, är kolinjära om och endast om a = b + c . Genom att välja alla punkter på dessa linjer där a , b och c är fältelementen med absolut spår 0, är ​​villkoret i definitionen av en projektiv triad uppfyllt.

Sats : I PG(2, p ), med p ett primtal, finns det en projektiv triad av sidan ( p + 1)/2 som är en blockerande uppsättning storlek (3 p + 1)/2.

Storlek

Man söker vanligtvis efter små blockeringsset. Minsta storlek på en blockerande uppsättning av $H$ kallas $\tau (H)$ .

I det Desarguesiska projektiva planet av ordningen q , PG(2, q ), är storleken på en blockerande uppsättning B avgränsad:

$q+{\sqrt {q}}+1\leq |B|\leq q^{2}-{\sqrt {q}}.$

När q är en kvadrat uppnås den nedre gränsen av vilket Baer- underplan som helst och den övre gränsen kommer från komplementet till ett Baer-underplan.

Ett mer generellt resultat kan bevisas,

Varje blockeringsmängd i ett projektivt plan π av ordningen n har minst $n+{\sqrt {n}}+1$ punkter. Dessutom, om denna nedre gräns är uppfylld, så n nödvändigtvis en kvadrat och den blockerande mängden består av punkterna i något Baer-underplan av π.

En övre gräns för storleken på ett minimalt blockerande set har samma smak,

Varje minimal blockeringsmängd i ett projektivt plan π av ordningen n har som mest $n{\sqrt {n}}+1$ punkter. Dessutom, om denna övre gräns nås, så n nödvändigtvis en kvadrat och den blockerande mängden består av punkterna för någon enhet inbäddad i π.

När n inte är en kvadrat mindre kan sägas om de minsta icke-triviala blockerande uppsättningarna. Ett välkänt resultat på grund av Aart Blokhuis är:

Sats : En icke-trivial blockerande uppsättning i PG(2, p ), p a primtal, har storleken minst 3( p + 1)/2.

I dessa plan finns en projektiv triangel som möter denna gräns.

Historia

Blockerande uppsättningar har sitt ursprung i kontexten av ekonomisk spelteori i en artikel från 1956 av Moses Richardson. Spelare identifierades med poäng i ett ändligt projektivt plan och minimala vinnande koalitioner var linjer. En blockerande koalition definierades som en uppsättning punkter som inte innehåller någon linje men som skär varje linje. 1958 studerade JR Isbell dessa spel från en icke-geometrisk synvinkel. Jane W. DiPaola studerade de minsta blockerande koalitionerna i alla projektiva plan av ordning $\leq 9$ 1969.

I hypergrafer

Låt $H=(X,E)$ vara en hypergraf, så att $X$ är en uppsättning element, och $E$ är en samling av delmängder av $X$ , kallad (hyper)kanter. En blockerande uppsättning av $H$ är en delmängd $S$ av $X$ som har en icke-tom skärningspunkt med varje hyperkant.

Blockerande uppsättningar kallas ibland också för " träffuppsättningar " eller " vertexcover ". Även termen " transversal " används, men i vissa sammanhang är en transversal av $H$ en delmängd $T$ av $X$ som möter varje hyperedge i exakt en punkt.

En " tvåfärgning " av $H$ är en partition $\{C,D\}$ av $X$ i två delmängder (färgklasser) så att ingen kant är monokromatisk, dvs ingen kant finns helt inom $C$ eller inom $D$ . Nu är både $C$ och $D$ blockerande uppsättningar.

Kompletta k-bågar

I ett projektivt plan är en komplett k -båge en uppsättning av k punkter, inga tre kolinjära , som inte kan förlängas till en större båge (alltså varje punkt som inte är på bågen är på en sekantlinje i bågen – en linje som möter bågen i två punkter.)

Sats : Låt K vara en fullständig k -båge i Π = PG(2, q ) med k < q + 2. Dualen i Π av mängden sekantlinjer av K är en blockerande mängd, B , av storleken k ( k - 1)/2.

Rédei blockerande set

I vilket projektivt plan som helst av ordningen q , för varje icke-trivial blockeringsuppsättning B (med b = | B |, storleken på blockeringsuppsättningen) betrakta en linje som möter B i n punkter. Eftersom ingen linje finns i B måste det finnas en punkt, P , på denna linje som inte är i B . De q andra linjerna om P måste var och en innehålla minst en punkt av B för att kunna blockeras. Således är $b\geq n+q.$ Om för någon linjelikhet gäller i denna relation, kallas blockeringsmängden en blockerande uppsättning av Rédei-typ och linjen en Rédei-linje i blockeringsmängden (observera att n kommer att vara den största antal kolinjära punkter i B ). Alla blockeringsset är inte av Rédei-typ, men många av de mindre är det. Dessa uppsättningar är uppkallade efter László Rédei vars monografi om lakunära polynom över ändliga fält var inflytelserik i studiet av dessa uppsättningar.

Affina blockeringsset

En uppsättning punkter i det finita Desarguesiska affina rymden $AG(n,q)$ som skär varje hyperplan icke-trivialt, dvs varje hyperplan faller samman med någon punkt i mängden, kallas en affin blockeringsuppsättning. Identifiera utrymmet med $\mathbb {F} _{q}^{n}$ genom att fixa ett koordinatsystem. Då är det lätt att visa att uppsättningen punkter som ligger på koordinataxlarna bildar en blockerande uppsättning av storleken $1+n(q-1)$ . Jean Doyen gissade på en i Oberwolfach 1976 att detta är den minsta möjliga storleken på en blockerande uppsättning. Detta bevisades av RE Jamison 1977, och oberoende av AE Brouwer , A. Schrijver 1978 med användning av den så kallade polynommetoden. Jamison bevisade följande generella täckningsresultat från vilket bunden på affina blockeringsuppsättningar följer med hjälp av dualitet:

Låt $V$ vara ett $n$ dimensionellt vektorrum över $\mathbb {F} _{q}$ . Då är antalet $k$ -dimensionella coset som krävs för att täcka alla vektorer utom nollvektorn minst $q^{nk}-1+k (q-1)$ . Dessutom är denna gräns skarp.

Anteckningar

•    Barwick, Susan; Ebert, Gary (2008), Unitals in Projective Planes , New York: Springer, doi : 10.1007/978-0-387-76366-8 , ISBN 978-0-387-76364-4 , ISSN 1439-7382
• C. Berge , Graphs and hypergraphs, North-Holland, Amsterdam, 1973. (Definierar $\tau (H)$ .)
• P. Duchet, Hypergraphs, kapitel 7 i: Handbook of Combinatorics, North-Holland, Amsterdam, 1995.
•   Hirschfeld, JWP (1979), Projective Geometries over Finite Fields , Oxford: Oxford University Press, ISBN 978-0-19-853526-3
• Holder, Leanne D. (2001), Blocking Sets of Conics, Ph.D. avhandling , University of Colorado Denver
•   De Beule, Jan; Storme, Leo (2011), Current Research Topics in Galois Geometry , Nova Science Publishers, ISBN 978-1-61209-523-3 , arkiverad från originalet 2016-01-29 , hämtad 2016-01-23