Ekstremalna kombinatorika z verjetnostno metodo

delo diplomskega seminarja

Lucija Bogataj (Avtor), Marko Petkovšek (Mentor)

Povzetek

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.

Ključne besede

ekstremalna kombinatorika;verjetnostna metoda;množica brez vsot;turnir;dominantna množica;prekrižno število;incidence točk in premic;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2021
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
Založnik:	[L. Bogataj]
UDK:	519.1
COBISS:	78308867
Št. ogledov:	743
Št. prenosov:	96
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Extremal combinatorics with the probabilistic method
Sekundarni povzetek:	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.
Sekundarne ključne besede:	extremal combinatorics;probabilistic method;sum-free set;tournament;dominating set;crossing number;point-line incidence;
Vrsta dela (COBISS):	Delo diplomskega seminarja/zaključno seminarsko delo/naloga
Študijski program:	0
Komentar na gradivo:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja
Strani:	26 str.
ID:	13505878