Extremale combinatoriek
Extremale combinatoriek is een vakgebied van de combinatoriek. Extremale combinatoriek bestudeert hoe groot of hoe klein een verzameling eindige objecten (getallen, grafen, vectoren, verzamelingen, etc.) kan zijn, als deze aan bepaalde beperkingen moet voldoen.
Een groot deel van de extremale combinatoriek heeft betrekking op klassen van verzamelingen; dit heet extremale verzamelingenleer. Wat is bijvoorbeeld in een verzameling van n elementen het grootste aantal deelverzamelingen van k elementen die met elkaar paarsgewijs een doorsnede hebben? Wat is het grootste aantal deelverzamelingen waarvan geen enkele verzameling een andere verzameling bevat? De laatste vraag wordt beantwoord door de stelling van Sperner. Deze stelling gaf aanleiding tot een groot deel van de extremale verzamelingenleer.
Nog een voorbeeld: hoeveel mensen kunnen worden uitgenodigd voor een feest, waar er van elke drie mensen er twee zijn die elkaar kennen en twee die elkaar niet kennen? Ramsey-theorie laat zien dat er maximaal vijf personen zo'n feest kunnen bijwonen. Of stel dat we een eindige verzameling gehele getallen krijgen die niet nul zijn, en dat ons wordt gevraagd een zo groot mogelijke deelverzameling van deze verzameling te markeren, met de beperking dat de som van twee gemarkeerde gehele getallen niet kan worden gemarkeerd. Het lijkt erop dat we (onafhankelijk van wat de gegeven gehele getallen eigenlijk zijn) altijd minstens een derde ervan kunnen markeren.