Sprehodi z naključnimi permutacijamiMilanez, Tim (Avtor) Jezernik, Urban (Mentor) ekspanzivni grafipermutacijske grupeCayleyjev grafpremernaključni sprehodiNaj 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.20222022-09-14 08:15:02Delo diplomskega seminarja/zaključno seminarsko delo/naloga140303sl