delo diplomskega seminarja
Tim Milanez (Author), Urban Jezernik (Mentor)

Abstract

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.

Keywords

matematika;ekspanzivni grafi;permutacijske grupe;Cayleyjev graf;premer;naključni sprehodi;

Data

Language: Slovenian
Year of publishing:
Typology: 2.11 - Undergraduate Thesis
Organization: UL FMF - Faculty of Mathematics and Physics
Publisher: [T. Milanez]
UDC: 512
COBISS: 121240835 Link will open in a new window
Views: 1087
Downloads: 73
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Walks with random permutations
Secondary abstract: 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.
Secondary keywords: mathematics;expander graphs;permutation groups;Cayley graph;diameter;random walks;
Type (COBISS): Final seminar paper
Study programme: 0
Thesis comment: Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja
Pages: 32 str.
ID: 16458503