Extrem kombinatorik

Extremal kombinatorik är ett område av kombinatorik , som i sig är en del av matematiken . Extremal kombinatorik studerar hur stor eller hur liten en samling ändliga objekt ( tal , grafer , vektorer , mängder , etc.) kan vara, om den måste uppfylla vissa begränsningar.

Mycket av extrem kombinatorik gäller klasser av uppsättningar; detta kallas extremal mängdteori . Till exempel, i en n -elementmängd, vad är det största antalet k -elementundermängder som parvis kan skära varandra? Vilket är det största antalet delmängder av vilka ingen innehåller någon annan? Den senare frågan besvaras av Sperners sats , som gav upphov till mycket av extrema mängdteorin.

Ett annat slags exempel: Hur många personer kan bjudas in till en fest där det bland var tre personer finns två som känner varandra och två som inte känner varandra? Ramseys teori visar att högst fem personer kan delta i en sådan fest. Eller anta att vi får en ändlig uppsättning heltal som inte är noll, och ombeds markera en så stor delmängd som möjligt av denna uppsättning under begränsningen att summan av två markerade heltal inte kan markeras. Det verkar som om vi (oberoende av vad de givna heltal faktiskt är) alltid kan markera minst en tredjedel av dem.

Se även

Jukna, Stasys (2011), Extremal Combinatorics, With Applications in Computer Science , Birkhäuser Verlag, ISBN 3-540-66313-4 .
Alon, Noga ; Krivelevich, Michael (2006), Extremal and Probabilistic Combinatorics (PDF) .
Frankl, Peter ; Rödl, Vojtěch (1987), "Forbidden intersections", Transactions of the American Mathematical Society , 300 (1): 259–286, doi : 10.2307/2000598 .