Ekstremalna kombinatorika z verjetnostno metodoBogataj, Lucija (Avtor) Petkovšek, Marko (Mentor) ekstremalna kombinatorikaverjetnostna metodamnožica brez vsotturnirdominantna množicaprekrižno številoincidence točk in premicEkstremalna 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 funkcional; slučajna spremenljivka ne more biti povsod strogo večja (niti povsod strogo manjša) od svoje pričakovane vrednosti; za 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 $n\frac{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.20212021-09-22 08:15:14Delo diplomskega seminarja/zaključno seminarsko delo/naloga131037sl