Extremal combinatorics with the probabilistic method

Ekstremalna kombinatorika se ukvarja z vprašanji, kako velik oziroma majhen je lahko neki matematični objekt ali družina objektov, ki zadošča določenim pogojem. Verjetnostna metoda rešuje ekstremalne probleme s pomočjo katere od naslednjih trditev: pričakovana vrednost je linearni funkcionalslučajna spremenljivka ne more biti povsod strogo večja (niti povsod strogo manjša) od svoje pričakovane vrednostiza dokaz obstoja objekta z dano lastnostjo v neki končni množici objektov zadošča pokazati, da je verjetnost obstoja takega objekta pozitivna. S pomočjo verjetnostne metode so predstavljeni dokazi naslednjih izrekov: V poljubni množici neničelnih števil obstaja podmnožica brez vsot, katere moč je vsaj ena tretjina moči prvotne množice. Obstaja turnir z $n$ igralci, ki ima vsaj $n!/2^{n-1}$ Hamiltonovih poti. Če je $n geq k^{2}2^{k+1}$, potem obstaja turnir z $n$ igralci, pri katerem zunaj vsake podmnožice igralcev moči $k$ obstaja igralec, ki je premagal vse igralce v tej podmnožici. V grafu z $n$ vozlišči, katerih stopnja je vsaj $d$, obstaja dominantna množica vozlišč moči manjše ali enake $nfrac{1+ln(d+1)}{d+1}$. Graf z $n$ vozlišči in $e geq 4n$ povezavami ima prekrižno število večje ali enako $frac{e^3}{64n^2}$. Izreku o prekrižnem številu grafa sledijo še Szemerédi-Trotterjev izrek, njegova posledica in Beckov izrek o incidencah točk in premic v ravnini.Extremal combinatorics deals with questions about how big or small a certain mathematical object or family of objects can be to satisfy certain restrictions. The probabilistic method entails solving extremal problems using one of the following theorems: The expectation is a linear functional. A random variable cannot always be strictly greater (nor always strictly smaller) than its expectation. For a proof of existence of an object with a certain property within a finite set of objects it is enough to prove that the probability of existence of such an object is positive. The following theorems which use the probabilistic method are stated and proved: In any set of nonzero integers there is a sum-free subset with the size of at least one third of the original set. There is a tournament with $n$ players and at least $n!/2^{n-1}$ Hamiltonian paths. If $n geq k^{2}2^{k+1}$, then there is a tournament of $n$ players in which for every $k$ players there is a player who defeated them all. A graph with $n$ vertices with a minimum degree $d$ has a dominating set with at most $nfrac{1+ln(d+1)}{d+1}$ vertices. The crossing number of a graph with $n$ vertices and $e geq 4n$ edges is greater or equal to $nfrac{1+ln(d+1)}{d+1}$. The crossing number theorem is followed by the Szemerédi-Trotter theorem, one of its corollaries, and Beck\u27s theorem