hrvatski

Erdös-Ko-Rado teorem

Tema ovog diplomskog rada je teorem Erdösa, Koa i Radoa. Diplomski rad je podijeljen u tri poglavlja. U prvom poglavlju cilj je upoznati se s definicijom presijecajuće i t-presijecajuće familije k-članih podskupova i iskazati i dokazati EKR teorem. Definirane su i dokazane neke pomoćne tvrdnje. U drugom poglavlju obrađujemo alternativne dokaze EKR teorema. Prvo se bavimo Hilton-Milnerovim teoremom. Zatim definiramo pomoćne tvrdnje i iskazujemo Katonin teorem pomoću kojih dokazujemo EKR teorem za t=1. Na kraju poglavlja iskazujemo Kruskal-Katona teorem i pomoću njega pokazujemo da jedino kanonske presijecajuće familije dostižu jednakost u EKR teoremu za t=1. U trećem poglavlju iskazujemo analogone EKR teorema za druge objekte. Prvo definiramo Kneserove grafove, kliku i kokliku. Zatim za permutacije, particije, vektorske prostore nad konačnim poljima i riječi definiramo osnovne pojmove i iskazujemo analogone EKR teorema.

presijecajuća familija skupova

nije evidentirano