Mešanje z naključnimi transpozicijami

delo diplomskega seminarja

Matevž Miščič (Avtor), Urban Jezernik (Mentor)

Povzetek

V diplomski nalogi dokažemo, da pri mešanju z naključnimi transpozicijami pride do odreza ob času $\frac{1}{2}n\log{n}$. Pri dokazu zgornje meje odreza uporabimo nekomutativno Fourierovo transformacijo, za njeno uporabo pa predstavimo teorijo upodobitev končnih grup s posebnim poudarkom na simetrične grupe. Klasificiramo Spechtove module in pokažemo, da standardni politabloidi tvorijo njihove baze. Spodnjo mejo odreza dokažemo z verjetnostnimi metodami. Predstavimo tudi nekaj nadaljnjih primerov odreza pri sprehodih po grupah.

Ključne besede

matematika;upodobitve grup;simetrične grupe;naključni sprehodi;naključne transpozicije;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2022
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
Založnik:	[M. Miščič]
UDK:	512
COBISS:	120837379
Št. ogledov:	593
Št. prenosov:	133
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Shuffling by random transpositions
Sekundarni povzetek:	In this thesis we prove that in the case of random transposition shuffling cutoff occurs at time $\frac{1}{2}n\log{n}$. The upper bound is proved using noncommutative Fourier transform. To understand it representation theory of finite groups is presented with emphasis on symmetric groups. Specht modules are classified and it is shown that standard polytabloids form their bases. Lower bound is proved using methods from probability. We also discuss some further examples of cutoff for random walks on groups.
Sekundarne ključne besede:	mathematics;group representations;symmetric groups;random walks;random transpositions;
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:	37 str.
ID:	16400972