Sprehodi z naključnimi permutacijami : delo diplomskega seminarja

Milanez, Tim (avtor), Jezernik, Urban (mentor)

Naj bosta $g, h$ naključno izbrana elementa permutacijske grupe $S_n$. Ob predpostavki, da $g, h$ generirata $S_n$, pokažemo, da velja ${\rm diam}({\rm Cay}(S_n, \{g, h, g^{-1}, h^{-1}\})) \leq O(n^2(\log n)^c)$ z verjetnostjo $1- o(1)$ za neko konstanto $c$. Pri tem dokaz naslonimo na dejstvo, da imajo Schreierjevi grafi množice $r$-teric različnih števil iz $\{1, 2,\ldots, n\}$ glede na množico $d$ naključnih permutacij iz $S_n$ skoraj gotovo dobre ekspanzivne lastnosti, kar tudi dokažemo.

• Jezik: Slovenski jezik
• Ključne besede: ekspanzivni grafi, permutacijske grupe, Cayleyjev graf, premer, naključni sprehodi
• Vrsta gradiva: Delo diplomskega seminarja/zaključno seminarsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2022
• PID: 20.500.12556/RUL-140303
• UDK: 512
• COBISS.SI-ID: 121240835
• Datum objave v RUL: 14.09.2022

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Walks with random permutations

Izvleček

Let $g, h$ be a random pair of elements of the permutation group $S_n$. Under the assumption that $g, h$ generate $S_n$, we show that ${\rm diam}({\rm Cay}(S_n, \{g, h, g^{-1}, h^{-1}\})) \leq O(n^2(\log n)^c)$ with probabilty $1-o(1)$ for some constant $c$. We base our proof on the fact that Schreier graphs on the set of $r$-tuples of distinct elements of $\{1, 2,\ldots, n\}$ with respect to the set of $d$ random permutations are almost always good expanders, which we also prove.

• Ključne besede: expander graphs, permutation groups, Cayley graph, diameter, random walks