20.500.12556/RUL-139856 Mešanje z naključnimi transpozicijami delo diplomskega seminarja Shuffling by random transpositions 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. 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. upodobitve grup simetrične grupe naključni sprehodi naključne transpozicije group representations symmetric groups random walks random transpositions true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2022-09-08 08:15:08 2022-09-08 08:15:10 2024-05-29 12:11:50 0000-00-00 00:00:00 2022 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 512 125615 120837379 5301.pdf 5301.pdf 1 2AC9ED3CF03E4444778BAEB52073DB8D 76728ff0e6a2d40080c4155b54005aa1cf364e132497c8ff89d5a092eeed9f54 8a76a0c4-2f3d-11ed-92af-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=160492 Fakulteta za matematiko in fiziko 0 0 0