Probabilistic method in combinatorics

U ovom radu, bavimo se vjerojatnosnom metodom - moćnim alatom za dokazivanje da objekti s određenim svojstvima postoje. Ključna ideja vjerojatnosne metode je sljedeća: da bismo pokazali da postoji objekt koji zadovoljava određena svojstva, konstruiramo odgovarajući vjerojatnosni prostor i dokažemo da slučajno odabrani objekt iz tog prostora zadovoljava tražena svojstva s vjerojatnošću strogo većom od 0. U prvom poglavlju, na primjerima pokazujemo osnovne ideje vjerojatnosne metode te način na koji se ona može iskoristiti. Drugo poglavlje uvodi matematičko očekivanje koje ima široku primjenu u vjerojatnosnoj metodi. Bavimo se i situacijama u kojima vjerojatnosna metoda ne nudi rješenje odmah, već je potrebno odraditi neke prepravke kako bismo dobili željeni rezultat. U trećem poglavlju je predstavljen vrlo važan teorem mađarskog matematičara Lászla Lovásza - lokalna lema. Lokalna lema je primjenjiva u slučajevima kad relativno mali broj objekata u vjerojatnosnom prostoru zadovoljava svojstvo od interesa. Konačno, četvrto poglavlje se bavi koncentracijskim nejednakostima te martingalima. Koncentracijske nejednakosti generalno daju ocjenu na devijaciju slučajne varijable od njezinog očekivanja. Martingali su se ispostavili kao vrlo koristan alat vjerojatnosne metode, a na primjerima pokazujemo kako se mogu koristiti u teoriji grafova.In this thesis, a brief introduction to probabilistic method is given. Probabilistic method is a powerful tool used to prove the existence of objects with certain properties. The key idea behind the method is the following: in order to show the existence of an object that has some wanted property, an adequate probability space is constructed and then we prove that a randomly chosen object in this space satisfies the wanted property with positive probability. In the first chapter, basic ideas of probabilistic method are showcased through a number of examples. The second chapter is dedicated to the concept of mathematical expectation which is widely applied in probabilistic method. We also consider the situations in which the method does not offer the solution immediately, but some alterations are necessary in order to get the end result. Third chapter introduces a very important theorem by Hungarian mathematician László Lovász - the local lemma. Local lemma is generally used when the objects of interest are scarce. Finally, the fourth chapter is dedicated to the use of concentration inequalities and martingales. Concentration inequalities are generally used to estimate the deviation of a random variable from its mean. Martingales are very useful tool of probabilistic method. Through some examples in graph theory, the use of martingales is demonstrated