Erdős–Ko–Rado-satsen

Två korsande familjer av tvåelementsundermängder av en fyraelementsuppsättning. Uppsättningarna i den vänstra familjen innehåller alla det nedre vänstra elementet. Uppsättningarna i rätt familj undviker detta element.

Inom matematiken begränsar Erdős–Ko–Rado-satsen antalet mängder i en familj av mängder för vilka varannan mängd har minst ett element gemensamt. Paul Erdős , Chao Ko och Richard Rado bevisade satsen 1938, men publicerade den inte förrän 1961. Den är en del av fältet kombinatorik , och ett av de centrala resultaten av extrema mängdteorin .

Satsen gäller familjer av mängder som alla har samma storlek, $r$ , och alla är delmängder av någon större mängd storlek n { $displaystyle n}$ . Ett sätt att konstruera en familj av uppsättningar med dessa parametrar, där var och en delar ett element, är att välja ett enda element som tillhör alla delmängder och sedan bilda alla delmängder som innehåller det valda elementet. Erdős–Ko–Rado-satsen säger att när $n$ är tillräckligt stor för att problemet ska vara icke-trivialt ( ${\displaystyle n\geq 2r})$ ger denna konstruktion de största möjliga korsande familjerna. När $n=2r$ finns det andra lika stora familjer, men för större värden på $n$ kan bara familjerna konstruerade på detta sätt vara störst.

Erdős–Ko–Rado-satsen kan också beskrivas i termer av hypergrafer eller oberoende uppsättningar i Kneser-grafer . Flera analoga satser gäller andra typer av matematiska objekt än mängder, inklusive linjära delrum , permutationer och strängar . De beskriver återigen de största möjliga korsande familjerna som bildas genom att välja ett element och bilda familjen av alla objekt som innehåller det valda elementet.

Påstående

Antag att ${\mathcal {A}}$ är en familj av distinkta $r}$ -elementdelmängder displaystyle av en $n}$ -elementuppsättning displaystyle med $n\geq 2r$ och att varje två delmängder delar minst ett element. Sedan anger satsen att antalet mängder i ${\mathcal {A}}$ är högst binomialkoefficienten

$${\binom {n-1}{r-1}}.$$

Kravet att $n\geq 2r$ är nödvändigt för att problemet ska vara icke-trivialt: när ${\displaystyle n<2r} ,$ skär alla $r$ -elementuppsättningar , och den största korsande familjen består av alla $r$ -elementuppsättningar , med storlek ${\tbinom {n}{r}}$ .

Samma resultat kan formuleras som en del av teorin om hypergrafer . En familj storlek $r$ av uppsättningar kan också kallas en hypergraf, och när alla uppsättningar (som kallas "hyperedges" i detta sammanhang) har samma kallas det en $r$ -uniform hypergraf. Satsen ger alltså en övre gräns för antalet parvis överlappande hyperkanter i en $r$ -uniform hypergraf med $n$ hörn och $n\geq 2r$ .

Kneser-grafen $KG_{5,2}$ , med en vertex för varje delmängd med 2 element i 5-elementsmängden {1,2,3,4,5} och en kant för varje par disjunkta delmängder. Enligt Erdős–Ko–Rado-satsen har de oberoende mängderna i denna graf högst fyra hörn.

Satsen kan också formuleras i termer av grafteori : oberoendetalet för Kneser-grafen $KG_{n,r}$ för $n\geq 2r$ är

$$\alpha (KG_{n,r})={\binom {n-1}{r-1}}.$$

Detta är en graf med en vertex för varje $r$ -elementdelmängd av en $n$ -elementuppsättning , och en kant mellan varje par av disjunkta uppsättningar . En oberoende uppsättning är en samling av hörn som inte har några kanter mellan sina par, och oberoendestalet är storleken på den största oberoende uppsättningen. Eftersom Kneser-grafer har symmetrier som tar vilken vertex som helst till vilken annan vertex som helst (de är vertextransitiva grafer ) är deras kromatiska bråktal lika med förhållandet mellan deras antal hörn och deras oberoende tal, så ett annat sätt att uttrycka Erdős–Ko–Rado-satsen är att dessa grafer har kromatiskt bråktal exakt $n/k$ .

Historia

Paul Erdős , Chao Ko och Richard Rado bevisade detta teorem 1938 efter att ha arbetat tillsammans på det i England. Rado hade flyttat från Berlin till universitetet i Cambridge och Erdős från Ungern till universitetet i Manchester , båda flydde från Nazitysklands inflytande; Ko var en elev till Louis J. Mordell i Manchester. Men de publicerade inte resultatet förrän 1961, med den långa förseningen som delvis berodde på ett bristande intresse för kombinatorisk mängdteori på 1930-talet och ökat intresse för ämnet på 1960-talet. Tidningen från 1961 angav resultatet i en till synes mer allmän form, där delmängderna endast krävdes att vara högst r $\displaystyle r} ,$ och för att tillfredsställa det ytterligare kravet att ingen delmängd ingick i någon annan. En familj av delmängder som uppfyller dessa villkor kan förstoras till delmängder med storlek exakt $r$ antingen genom en tillämpning av Halls äktenskapsteorem , eller genom att välja varje förstorad delmängd från samma kedja i en symmetrisk kedjeuppdelning av mängder.

Maximala och maximala familjer

Familjer av maximal storlek

Johnson -grafen $J(4,2)$ , med en vertex för varje delmängd av två element av {1,2,3,4} och en kant som förbinder korsande par av delmängder, arrangerade geometriskt som en oktaeder med disjunkta uppsättningar vid motsatta hörn. De största korsande familjerna för $r=2$ och $n=2r=4$ kommer från de triangulära ytorna på denna oktaeder. Att ersätta en mängd i en av dessa familjer med dess komplement motsvarar att flytta från en triangel till en av dess tre angränsande trianglar.

Ett enkelt sätt att konstruera en korsande familj av $r$ -elementuppsättningar vars storlek exakt matchar Erdős–Ko–Rado-gränsen är att välja valfritt fast element ${\displaystyle x} ,$ och låta ${\ mathcal {A}}$ består av alla $r$ -elementdelmängder som inkluderar $x$ . Till exempel, för delmängder med 2 element av uppsättningen med 4 element $\{1,2,3,4\}$ , med $x=1$ , detta producerar familjen

$\{1,2\}$ , $\{1,3\}$ och { $\displaystyle \{1,4\} }$ .

Alla två uppsättningar i denna familj skär varandra, eftersom de båda inkluderar $1$ . Antalet uppsättningar är ${\displaystyle {\tbinom {n-1}{r-1}}},$ eftersom efter att det fasta elementet har valts återstår $n-1$ andra element att välja, och varje uppsättning väljer $r-1$ av dessa återstående element.

När $n>2r$ är detta den enda korsande familjen av denna storlek. Men när $n=2r$ finns det en mer allmän konstruktion. Varje $r$ -elementuppsättning kan matchas upp till dess komplement , den enda $r$ -elementuppsättningen från vilken den är disjunkt. Välj sedan en uppsättning från vart och ett av dessa komplementära par. Till exempel, för samma parametrar ovan, kan denna mer allmänna konstruktion användas för att bilda familjen

$\{3,4\}$ , $\{2,4\}$ och { $\displaystyle \{2,3\} }$ ,

där varannan uppsättning skär varandra trots att inget element tillhör alla tre uppsättningarna. I det här exemplet har alla uppsättningar kompletterats från de i det första exemplet, men det är också möjligt att komplettera endast några av uppsättningarna.

När $n>2r$ är familjer av den första typen (omväxlande kända som stjärnor, diktaturer, juntor, centrerade familjer eller huvudfamiljer) de unika maximala familjerna. I det här fallet har en familj av nästan maximal storlek ett element som är gemensamt för nästan alla dess uppsättningar. Denna egenskap har kallats stabilitet , även om samma term också har använts för en annan egenskap, det faktum att (för ett brett spektrum av parametrar) radering av slumpmässigt valda kanter från Kneser-grafen inte ökar storleken på dess oberoende uppsättningar .

Maximalt korsande familjer

Fanoplanets sju punkter och sju linjer (en ritad som en cirkel) bildar en maximalt korsande familj.

En korsande familj av $r$ -elementuppsättningar kan vara maximala, genom att ingen ytterligare uppsättning kan läggas till (även genom att förlänga markuppsättningen) utan att förstöra intersection-egenskapen, men inte av maximal storlek. Ett exempel med $n=7$ och $r=3$ är uppsättningen av sju linjer i Fano-planet , mycket mindre än Erdős–Ko–Rado-gränsen på 15. Mer allmänt , linjerna i ett ändligt projektivt plan av ordning $q$ bildar en maximalt korsande familj som endast inkluderar $n$ uppsättningar, för parametrarna $r=q+1$ och $n=q^{2}+q+1$ . Fano-planet är fallet $q=2$ av denna konstruktion.

Den minsta möjliga storleken på en maximalt korsande familj av $r$ -elementuppsättningar , i termer av ${\displaystyle r} ,$ är okänd men minst $3r$ för $r \geq 4$ . Projektiva plan producerar maximala korsande familjer vars antal uppsättningar är ${\displaystyle r^{2}-r+1} ,$ men för oändligt många val av $r$ finns det mindre maximalt skärande familjer av storlek ${\tfrac {3}{4}}r^{2}$ .

De största korsande familjerna av $r$ -elementuppsättningar som är maximala men inte maximala har storlek

$${\binom {n-1}{r-1}}-{\binom {nr-1}{r -1}}+1.$$

De bildas av ett element $x$ och en $r$ -elementuppsättning { $Y$ som inte innehåller $x$ , genom att lägga till $\displaystyle Y}$ till familjen av $r$ -elementuppsättningar som inkluderar både $x$ och minst ett element av $Y$ . Detta resultat kallas Hilton–Milner-teoremet , efter dess bevis av Anthony Hilton och Eric Charles Milner 1967 .

Bevis

Det ursprungliga beviset för Erdős–Ko–Rado-satsen använde induktion på $n$ . Basfallet, för $n=2r$ , följer lätt av fakta att en korsande familj inte kan inkludera både en mängd och dess komplement , och att i detta fall gränsen för Erdős–Ko–Rado-satsen är exakt halva antalet av alla $r$ -elementuppsättningar . Induktionssteget för större $n$ använder en metod som kallas shifting , för att ersätta element i korsande familjer för att göra familjen mindre i lexikografisk ordning och reducera den till en kanonisk form som är lättare att analysera.

1972 gav Gyula OH Katona följande korta bevis med hjälp av dubbelräkning .

Låt ${\mathcal {A}}$ vara vilken som helst korsande familj av $r$ -elementdelmängder av en $n$ -elementuppsättning . Ordna alla $n$ element i valfri cyklisk ordning , och betrakta mängderna från ${\mathcal {A}}$ som bildar intervall med längden $r$ inom denna valda cykliska ordning. Till exempel om $n=8$ och $r=3$ , en möjlig cyklisk ordning för talen $\{1,2,...,8\}$ är ordningen $(3,1,5, 4,2,7,6,8)$ , som har åtta intervall med 3 element (inklusive de som omsluter):

$(3,1,5)$ , $(1,5,4)$ , $(5) ,4,2)$ , $(4,2,7)$ , $(2,7,6)$ , $(7,6,8)$ , $(6,8,3)$ och $(8,3,1 )$ .

Men bara några av dessa intervall kan tillhöra A $\displaystyle {\mathcal {A}}}$ , eftersom de inte alla skär varandra. Katonas nyckelobservation är att högst $r$ -intervall från en enda cyklisk ordning kan tillhöra A $\displaystyle {\mathcal {A}}}$ . Detta beror på att om $(a_{1},a_{2},\dots ,a_{r})$ är ett av dessa intervall, då vartannat intervall av samma cykliska ordning som hör till ${\mathcal {A}}$ skiljer $a_{i}$ från $a_{i+1}$ , för vissa $i$ , genom att innehålla exakt ett av dessa två element. De två intervallen som skiljer dessa element åt är disjunkta, så högst ett av dem kan tillhöra A $\displaystyle {\mathcal {A}}}$ . Således är antalet intervall i ${\mathcal {A}}$ högst ett plus antalet $r-1$ par som kan separeras.

Baserat på denna idé är det möjligt att räkna paren $(S,C)$ , där $S$ är en mängd i ${\mathcal {A}}$ och $C$ är en cyklisk ordning för vilken $S$ är ett intervall, på två sätt. Först, för varje uppsättning $S$ kan man generera $C$ genom att välja en av $r!$ permutationer av $S$ och $(nr)!$ permutationer av de återstående elementen, vilket visar att antalet par är $|{\mathcal {A}}|r!(nr)!$ . Och för det andra, det finns $(n-1)!$ cykliska order, som var och en har högst $r$ intervall av ${\mathcal {A}}$ , så antalet par är högst $r(n-1)!$ . Att jämföra dessa två siffror ger ojämlikheten

$$|{\mathcal {A}}|r!(nr)!\leq r(n-1)!$$

och dividera båda sidor med $r!(nr)!$ ger resultatet

$$|{\mathcal {A}}|\leq {\frac {r(n-1)!}{r!(nr)!}}={n-1 \choose r-1}.$$

Det är också möjligt att härleda Erdős–Ko–Rado-satsen som ett specialfall av Kruskal–Katona-satsen , ett annat viktigt resultat i extremmängdsteorin . Många andra bevis är kända.

Relaterade resultat

Generaliseringar

En generalisering av satsen gäller delmängder som krävs för att ha stora skärningspunkter. Denna version av satsen har tre parametrar: $n$ , antalet element som delmängderna är hämtade från, $r$ , storleken på delmängderna, som tidigare, och $t$ , minsta storleken på skärningspunkten mellan två delmängder. För den ursprungliga formen av Erdős–Ko–Rado-satsen är $t=1$ . I allmänhet, för $n$ tillräckligt stor med avseende på de andra två parametrarna, anger den generaliserade satsen att storleken på en $t$ -korsande familj av delmängder är som mest

$${\binom {nt}{kt}}.$$

Mer exakt gäller denna gräns när ${\displaystyle n\geq (t+1)(k-t+1)} ,$ och gäller inte för mindre värden på $n$ . När ${\displaystyle n>(t+1)(k-t+1)} ,$ erhålls de enda $t$ -korsande familjerna av denna storlek genom att ange $t$ element som den gemensamma skärningspunkten för alla delmängder, och konstruera familjen av alla $r$ -elementundermängder som inkluderar dessa $t$ designade element.

Den motsvarande grafteoretiska formuleringen av denna generalisering involverar Johnson-grafer i stället för Kneser- grafer. För tillräckligt stora värden på $n$ och i synnerhet för ${\displaystyle n>{\tfrac {1}{2}}k^{2}},$ både Erdős–Ko–Rado satsen och dess generalisering kan stärkas från oberoendetalet till Shannon-kapaciteten för en graf : Johnson-grafen som motsvarar $t$ -skärande $r$ -elementdelmängder har Shannon- kapacitet ${\tbinom {nt}{kt}}$ .

Teoremet kan också generaliseras till familjer där varje $h$ delmängder har en gemensam skärningspunkt. Eftersom detta förstärker villkoret att varje par skär varandra (för vilka $h=2$ ), har dessa familjer samma gräns för sin maximala storlek, ${\tbinom { n-1}{r-1}}$ när $n$ är tillräckligt stor. Men i det här fallet kan betydelsen av "tillräckligt stor" lättas från $n\geq 2r$ till $n\geq {\tfrac {h}{h -1}}r$ .

Analoger

Många resultat som är analoga med Erdős–Ko–Rado-satsen, men för andra klasser av objekt än ändliga mängder, är kända. Dessa innefattar i allmänhet ett uttalande att de största familjerna av skärande objekt, för en viss definition av skärningspunkt, erhålls genom att välja ett element och konstruera familjen av alla objekt som inkluderar det valda elementet. Exempel inkluderar följande:

Det finns en q -analog av Erdős–Ko–Rado-satsen för korsande familjer av linjära delrum över finita fält . Om ${\mathcal {S}}$ är en korsande familj av $k$ -dimensionella delrum av ett $n$ -dimensionellt vektorrum över ett ändligt ordningsfält q $\displaystyle q }$ , och $n\geq 2k$ , sedan

$$|{\mathcal {S}}|\leq {\binom {n-1}{k-1}}_{q},$$

där nedsänkt q markerar notationen för den gaussiska binomialkoefficienten , antalet delrum av en given dimension inom ett vektorrum med en större dimension över ett ändligt ordningsfält q . I detta fall kan en största korsande familj av delrum erhållas genom att välja vilken vektor som helst som inte är noll och konstruera familjen av delrum med den givna dimensionen som alla innehåller den valda vektorn.

Två permutationer på samma uppsättning element är definierade att skära varandra om det finns något element som har samma bild under båda permutationerna. På en $n$ -elementuppsättning finns det en uppenbar familj av $(n-1)!$ korsande permutationer, de permutationer som fixerar ett av elementen (stabilisatorundergruppen för detta element). Den analoga satsen är att ingen korsande familj av permutationer kan vara större, och att de enda korsande familjerna av storlek $(n-1)!$ är en-elements stabilisatorer . Dessa kan mer direkt beskrivas som de familjer av permutationer som mappar något fast element till ett annat fast element. Mer generellt, för alla $t$ och tillräckligt stora $n$ , har en familj av permutationer som vart och ett par har $t$ element gemensamma maximal storlek $(nt)!$ , och de enda familjerna av denna storlek är uppsättningar av punktvisa stabilisatorer. Alternativt, i grafteoretiska termer, motsvarar $n$ -elementpermutationerna den perfekta matchningen av en komplett tvådelad graf $K_{n,n}$ och satsen säger att bland familjer av perfekta matchningar av vilka varje par delar $t$ kanter, de största familjerna bildas av matchningarna som alla innehåller $t$ valda kanter. En annan analog till satsen, för partitioner av en mängd , inkluderar som ett specialfall de perfekta matchningarna av en komplett graf $K_{n}$ (med $n$ jämnt). Det finns $(n-1)!!$ matchningar, där $!!$ betecknar dubbelfaktorial . Den största familjen av matchningar som parvis skär varandra (vilket betyder att de har en kant gemensam) har storlek $(n-3)!!$ och erhålls genom att fixera en kant och välja alla sätt att matcha de återstående $n-2$ hörnen.

En partiell geometri är ett system av ändligt många abstrakta punkter och linjer, som uppfyller vissa axiom inklusive kravet att alla linjer innehåller samma antal punkter och alla punkter tillhör samma antal linjer. I en partiell geometri kan ett största system av parvis skärande linjer erhållas från uppsättningen linjer genom vilken enskild punkt som helst.

En signerad uppsättning består av en uppsättning tillsammans med teckenfunktion som mappar varje element till $\{1,-1\}$ . Två tecken med tecken kan sägas skära varandra när de har ett gemensamt element som har samma tecken i var och en av dem. Då består en korsande familj av $r$ -elementsignerade uppsättningar, ritade från ett $n$ -elementuniversum , av högst

$$2^{r-1}{\binom {n-1}{r-1}}$$

signerade set. Detta antal signerade uppsättningar kan erhållas genom att fixera ett element och dess tecken och låta de återstående $r-1$ elementen och tecknen variera.

För strängar med längden $n$ över ett alfabet med storleken $q$ , kan två strängar definieras så att de skär varandra om de har en position där båda delar samma symbol. De största korsande familjerna erhålls genom att välja en position och en fast symbol för den positionen, och låta resten av positionerna variera godtyckligt. Dessa familjer består av ${\textstyle q^{n-1}}$ strängar och är de enda parvis korsande familjerna av denna storlek. Mer allmänt erhålls de största familjerna av strängar där varannan har $t$ -positioner med lika symboler genom att välja $t+2i$ -positioner och symboler för dessa positioner, för ett nummer ${ \displaystyle i}$ som beror på $n$ , $q$ och $t$ , och konstruera familjen av strängar som var och en har minst $t+i$ av de valda symbolerna. Dessa resultat kan tolkas grafteoretiskt i termer av Hamming-schemat .

Olöst problem i matematik :

Erhålls den största familjen av korsande trianguleringar av en konvex polygon genom att skära av en vertex och välja alla trianguleringar i den återstående polygonen?

(fler olösta problem i matematik)

En obevisad gissning , ställd av Gil Kalai och Karen Meagher, gäller en annan analog för familjen av triangulering av en konvex polygon med $n$ hörn. Antalet trianguleringar är ett katalanskt tal $C_{n-2}$ , och gissningen säger att en familj av trianguleringar som varje par delar en kant har maximal storlek $C_{n-3}$ . En korsande familj med storlek exakt $C_{n-3}$ kan erhållas genom att skära av en enda vertex på polygonen med en triangel och välja alla sätt att triangulera de återstående ${ \displaystyle (n-1)}$ -vertexpolygon .

Ansökningar

Erdős–Ko–Rado-satsen kan användas för att bevisa följande resultat i sannolikhetsteori . Låt $x_{i}$ vara oberoende 0–1 slumpvariabler med sannolikheten att $p\geq {\tfrac {1}{2}}$ är ett, och låt $c({\vec {x}})$ vara vilken fast konvex kombination som helst av dessa variabler. Sedan

$$\Pr \left[c({\vec {x}})\geq {\tfrac {1}{2}}\right]\geq p.$$

Beviset innebär att observera att delmängder av variabler vars indikatorvektorer har stora konvexa kombinationer måste vara icke-disjunkta och använda Erdős–Ko–Rado-satsen för att binda antalet av dessa delmängder.

Stabilitetsegenskaperna för Erdős–Ko–Rado-satsen spelar en nyckelroll i en effektiv algoritm för att hitta monokromatiska kanter i felaktig färgning av Kneser-grafer. Erdős–Ko–Rado-satsen har också använts för att karakterisera symmetrierna i rymden av fylogenetiska träd .

Se även

• Hellys teorem , om villkor som säkerställer att korsande familjer av konvexa mängder har en gemensam skärningspunkt
• Sperners teorem , en övre gräns för familjer av parvisa icke-kapslade uppsättningar
• Steiner-system , familjer med maximal storlek i enhetliga uppsättningar där inget par (snarare än varje par) har en stor skärningspunkt
• Sunflower (matematik) , en familj av mängder där (till skillnad från de maximalt korsande familjerna här) alla par har lika stora skärningspunkter
• Thrackle , ett olöst problem med storleken på familjer med korsande kurvor

Anförda verk

•   Ahlswede, Rudolf; Khachatrian, Levon H. (1998), "The diametric theorem in Hamming spaces—optimal anticodes", Advances in Applied Mathematics , 20 (4): 429–449, doi : 10.1006/aama.1998.0588 , MR 1612855
•     Aigner, Martin ; Ziegler, Günter M. (2018), "Chapter 30: Three famous theorems on finite sets", Proofs from THE BOOK (6:e upplagan), Springer, s. 213–217, doi : 10.1007/978-3-662-57265 -8_15 , ISBN 978-3-662-57265-8 , MR 3823190 , Zbl 1392.00001
•    Anderson, Ian (1987), "Kapitel 5: Intersecting systems and the Erdős–Ko–Rado theorem", Combinatorics of Finite Sets , Oxford Science Publications, Oxford University Press, s. 70–86, ISBN 0-19-853367-5 MR 0892525 _
•    Anderson, Ian (2013), "Combinatorial set theory", i Wilson, Robin ; Watkins, John J. (red.), Combinatorics: Ancient and Modern , Oxford University Press, s. 309–328, doi : 10.1093/acprof:oso/9780199656592.003.0014 , ISBN 978-0-159-26 , ISBN 978-0-159-26 3204727
• Balogh, József ; Krueger, Robert A.; Luo, Haoran (2022), "Sharp threshold for the Erdős–Ko–Rado theorem", Random Structures & Algorithms , 62 : 3–28, arXiv : 2105.02985 , doi : 10.1002 / rsa.2409000.2909 , 3209ID  
•    Bollobás, Béla ; Leader, Imre (1997), "An Erdős–Ko–Rado theorem for signed sets", Computers and Mathematics with Applications , 34 ( 11): 9–13, doi : 10.1016/S0898-1221(97)00215-0 , MR 1486880 , Zbl 0901.05088
•   Bollobás, Béla ; Narayanan, Bhargav P.; Raigorodskii, Andrei M. (2016), "Om stabiliteten i Erdős-Ko-Rado-teorem", Journal of Combinatorial Theory , Series A, 137 : 64–78, doi : 10.1016/j.jcta.2015.08.002 , MR . 3403515
•   Borg, Peter (2012), "Cross-intersecting sub-families of hereditary families", Journal of Combinatorial Theory , Series A, 119 (4): 871–881, doi : 10.1016/j.jcta.2011.12.002 , MR 3 288122
•   Cameron, Peter J .; Ku, CY (2003), "Intersecting families of permutations", European Journal of Combinatorics , 24 (7): 881–890, doi : 10.1016/S0195-6698(03 ) 00078-7 , MR 20094000 , Z.0501  
•   Das, Shagnik; Tran, Tuan (2016), "Avlägsnande och stabilitet för Erdős–Ko–Rado", SIAM Journal on Discrete Mathematics , 30 (2): 1102–1114, doi : 10.1137/15M105149X , MR 3504983
•   Deza, Michel ; Frankl, Péter (1983), "Erdős–Ko–Rado theorem – 22 years later", SIAM Journal on Algebraic and Discrete Methods , 4 (4): 419–431, doi : 10.1137/0604042 , MR 0721612
•    Dinur, Irit ; Friedgut, Ehud (2009), "Intersecting familys are essentially contained in juntas", Combinatorics , Probability and Computing , 18 (1–2): 107–122, doi : 10.1017/S0963548308009309 , 72C 3722 49 , 72C 372249 , 72C 376249
•   Dow, Stephen J.; Drake, David A. ; Füredi, Zoltán; Larson, Jean A. (1985), "A lower bound for the cardinality of a maximum family of mutually intersecting sets of equal size", Proceedings of the sixteenth Southeastern international conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1985), Congressus Numerantium , 48 : 47–48, MR 0830697
•   Ellis, David; Friedgut, Ehud; Pilpel, Haran (2011), "Intersecting families of permutations", Journal of the American Mathematical Society , 24 (3): 649–682, doi : 10.1090 /S0894-0347-2011-00690-5 , MR 27842314 9,1 S.  
•     Erdős, Paul (1987), "My joint work with Richard Rado" (PDF) , i Whitehead, C. (red.), Surveys in combinatorics, 1987: Invited Papers for the Eleventh British Combinatorial Conference , London Mathematical Society Lecture Note Series vol. 123, Cambridge University Press, s. 53–80, ISBN 978-0-521-34805-8 , MR 0905276 , Zbl 0623.01010
•   Erdős, P. ; Ko, Chao ; Rado, R. ( 1961), "Intersection theorems for systems of finite sets" (PDF) , Quarterly Journal of Mathematics , Second Series, 12 : 313–320, doi : 10.1093/qmath/12.1.313 , MR 01409  
•   Frankl, Péter (1976), "On Sperner familys satisfying an additional condition", Journal of Combinatorial Theory , Series A, 20 (1): 1–11, doi : 10.1016/0097-3165(76)90073-x , MR 03988422
•    Frankl, Péter ; Deza, Mikhail (1977), "Om det maximala antalet permutationer med givet maximalt eller minimalt avstånd", Journal of Combinatorial Theory , Series A, 22 (3): 352–360, doi : 10.1016/0097-3165(77)90009 -7 , MR 0439648 , Zbl 0352.05003
•   Frankl, Péter ; Füredi, Zoltán (1986), "Nontrivial intersecting families", Journal of Combinatorial Theory , Series A, 41 (1): 150–153, doi : 10.1016/0097-3165(86)90121-4 , MR 48266
•   Frankl, Péter ; Graham, Ronald L. (1989), "Gamla och nya bevis för Erdős–Ko–Rado-teorem" (PDF) , Journal of Sichuan University Natural Science Edition , 26 (Special Issue): 112–122, MR 1059690
•    Frankl, Péter ; Wilson, Richard M. (1986), "The Erdős–Ko–Rado theorem for vector spaces", Journal of Combinatorial Theory , Series A, 43 (2): 228–236, doi : 10.1016/0097-3165(86)90063 -4 , MR 0867648 , Zbl 0609.05055
•     Friedgut, Ehud (2008), "Om måttet på korsande familjer, unikhet och stabilitet" (PDF) , Combinatorica , 28 (5): 503–528, doi : 10.1007/s00493-008-2318-9 , S22CID 25, S22CID 25 , 7225916 , Zbl 1199.05319 , arkiverad från originalet (PDF) 2021-01-25
•   Füredi, Zoltán (1980), "On maximal intersecting familys of finite sets", Journal of Combinatorial Theory , Series A, 28 (3): 282–289, doi : 10.1016/0097-3165(80)90071-0 , MR 105700
•    Füredi, Zoltán (1995), "Extremala hypergrafer och kombinatorisk geometri" (PDF) , Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Zürich, 1994) , Basel: Birkhäuser, s. 1343–1352, doi : 10.1007/978-3-0348-9078-6_65 , MR 1404036 , Zbl 008739 .
•    Godsil, Chris ; Meagher, Karen (2009), "A new proof of the Erdős–Ko–Rado theorem for intersecting familys of permutations", European Journal of Combinatorics , 30 (2): 404–414, doi : 10.1016/j.ejc.2008.05. 006 , MR 2489272 , Zbl 1177.05010
•   Godsil, Christopher ; Meagher, Karen (2015), Erdős–Ko–Rado Theorems: Algebraic Approaches , Cambridge Studies in Advanced Mathematics, Cambridge University Press, ISBN 9781107128446
•    Grindstaff, Gillian (2020), "The isometry group of phylogenetic tree space is S _n ", Proceedings of the American Mathematical Society , 148 ( 10): 4225–4233, arXiv : 1901.02982 , doi : 10.1091/45proc/50901/45proc / 51901 , S2CID 57761161
•     Harvey, Daniel J.; Wood, David R. (2014), "Treewidth of the Kneser graph and the Erdős–Ko–Rado theorem", Electronic Journal of Combinatorics , 21 (1), Paper 1.48, arXiv : 1310.5400 , doi : 10.37236/59 : 10.37236/ 59 , S2CID 15461040 , Zbl 1300.05084
•   Haviv, Ishay (2022), "A fixed-parameter algorithm for the Kneser problem", i Bojanczyk, Mikolaj; Merelli, Emanuela; Woodruff, David P. (red.), 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, 4–8 juli 2022, Paris, Frankrike , LIPIcs, vol. 229, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, s. 72:1–72:18, arXiv : 2204.06761 , doi : 10.4230/LIPIcs.ICALP.2022.72 , ISBN 97723958
•   Hilton, AJW ; Milner, EC (1967), "Some intersection theorems for systems of finite sets", Quarterly Journal of Mathematics , Second Series, 18 : 369–384, doi : 10.1093/qmath/18.1.369 , MR 0219428
•    Katona, GOH (1972), "A simple proof of the Erdös–Chao Ko–Rado theorem", Journal of Combinatorial Theory , Series B, 13 (2): 183–184, doi : 10.1016/0095-8956(72)90054 -8 , MR 0304181 , Zbl 0262.05002
•   Larose, Benoit; Malvenuto, Claudia (2004), "Stable sets of maximal size in Kneser-type graphs", European Journal of Combinatorics , 25 (5): 657–673, doi : 10.1016/j.ejc.2003.10.006 , MR 2061391
•   Liggett, Thomas M. (1977), "Extensions of the Erdős–Ko–Rado theorem and a statistical application", Journal of Combinatorial Theory , Series A, 23 (1): 15–21, doi : 10.1016/0097-3165( 77)90075-9 , MR 0441750
•    van Lint, JH ; Wilson, Richard M. (1992), A Course in Combinatorics , Cambridge University Press, Cambridge, s. 45–46, ISBN 0-521-41057-6 , MR 1207813
•    Olarte, Jorge Alberto; Santos, Francisco ; Spreer, Jonathan; Stump, Christian (2020), "The EKR property for flag pure simplicial complexes without boundary" (PDF) , Journal of Combinatorial Theory , Series A, 172 : 105205, 29, doi : 10.1016/j.jcta.2019.105205 ​​, 3MR 405 , 3MR 705 S2CID 119158469
•     Polcyn, Joanna; Ruciński, Andrzej (2017), "A hierarchy of maximal intersecting triple systems", Opuscula Mathematica , 37 (4): 597–608, arXiv : 1608.06114 , doi : 10.7494 /OpMath.7.45.3 7.209 7.209 7.2014 , 7.37.2017 . ID 55674958 , Zbl 1402.05209
•   Schrijver, Alexander (1981), "Associationsscheman och Shannon-kapaciteten: Eberlein-polynom och Erdős-Ko-Rado-satsen", i Lovász, László ; Sós, Vera T. (red.), Algebraic Methods in Graph Theory, Vol. I, II: Dokument från konferensen som hölls i Szeged, 24–31 augusti 1978, Colloquia Mathematica Societatis János Bolyai, vol. 25, North-Holland, s. 671–688, MR 0642067
•    Wilson, Richard M. (1984), "The exact bound in the Erdős–Ko–Rado theorem", Combinatorica , 4 (2–3): 247–257, doi : 10.1007/BF02579226 , MR 0771733 , S5048449 , S504849

externa länkar

• Cameron, Peter (29 september 2017), "EKR, Steiner-system, associationsscheman och allt det där" , Peter Camerons blogg