Ekstremalna kombinatorika z verjetnostno metodo : delo diplomskega seminarja

Bogataj, Lucija (avtor), Petkovšek, Marko (mentor)

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 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.

• Jezik: Slovenski jezik
• Ključne besede: ekstremalna kombinatorika, verjetnostna metoda, množica brez vsot, turnir, dominantna množica, prekrižno število, incidence točk in premic
• Vrsta gradiva: Delo diplomskega seminarja/zaključno seminarsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2021
• PID: 20.500.12556/RUL-131037
• UDK: 519.1
• COBISS.SI-ID: 78308867
• Datum objave v RUL: 22.09.2021

BOGATAJ, Lucija, 2021, Ekstremalna kombinatorika z verjetnostno metodo : delo diplomskega seminarja [na spletu]. Diplomsko delo. [Dostopano 18 maj 2025]. Pridobljeno s: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=131037

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Extremal combinatorics with the probabilistic method

Izvleček

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 $n\frac{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 $n\frac{1+\ln(d+1)}{d+1}$. The crossing number theorem is followed by the Szemerédi-Trotter theorem, one of its corollaries, and Beck's theorem.

• Ključne besede: extremal combinatorics, probabilistic method, sum-free set, tournament, dominating set, crossing number, point-line incidence