Ekstremalna kombinatorika z verjetnostno metodo

delo diplomskega seminarja

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

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2021
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FMF - Faculty of Mathematics and Physics
Publisher:	[L. Bogataj]
UDC:	519.1
COBISS:	78308867
Views:	743
Downloads:	96
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Extremal combinatorics with the probabilistic method
Secondary abstract:	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.
Secondary keywords:	extremal combinatorics;probabilistic method;sum-free set;tournament;dominating set;crossing number;point-line incidence;
Type (COBISS):	Final seminar paper
Study programme:	0
Thesis comment:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja
Pages:	26 str.
ID:	13505878