Your browser does not allow JavaScript!
JavaScript is necessary for the proper functioning of this website. Please enable JavaScript or use a modern browser.
Open Science Slovenia
Open Science
DiKUL
slv
|
eng
Search
Browse
New in RUL
About RUL
In numbers
Help
Sign in
Mešanje z naključnimi transpozicijami : delo diplomskega seminarja
ID
Miščič, Matevž
(
Author
),
ID
Jezernik, Urban
(
Mentor
)
More about this mentor...
PDF - Presentation file,
Download
(575,71 KB)
MD5: 2AC9ED3CF03E4444778BAEB52073DB8D
Image galllery
Abstract
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.
Language:
Slovenian
Keywords:
upodobitve grup
,
simetrične grupe
,
naključni sprehodi
,
naključne transpozicije
Work type:
Final seminar paper
Typology:
2.11 - Undergraduate Thesis
Organization:
FMF - Faculty of Mathematics and Physics
Year:
2022
PID:
20.500.12556/RUL-139856
UDC:
512
COBISS.SI-ID:
120837379
Publication date in RUL:
08.09.2022
Views:
827
Downloads:
161
Metadata:
Cite this work
Plain text
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
Copy citation
Share:
Secondary language
Language:
English
Title:
Shuffling by random transpositions
Abstract:
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.
Keywords:
group representations
,
symmetric groups
,
random walks
,
random transpositions
Similar documents
Similar works from RUL:
Similar works from other Slovenian collections:
Back