20.500.12556/RUL-140303 Sprehodi z naključnimi permutacijami delo diplomskega seminarja Walks with random permutations 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. 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. ekspanzivni grafi permutacijske grupe Cayleyjev graf premer naključni sprehodi expander graphs permutation groups Cayley graph diameter random walks true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2022-09-14 08:15:02 2022-09-14 08:15:03 2024-05-29 12:12:58 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 127026 121240835 5358.pdf 5358.pdf 1 6E1D80D268C4FF1D8ADBE91F7529CC99 8e5a998909964a8eaa3881c7d7bbeb37e95f560aebdb853f559c36cf5d0ae603 81308d10-33f4-11ed-92af-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=161011 Fakulteta za matematiko in fiziko 0 0 0