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

Povzetek

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.

Ključne besede

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

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UL FMF - Fakulteta za matematiko in fiziko
Založnik: [T. Milanez]
UDK: 512
COBISS: 121240835 Povezava se bo odprla v novem oknu
Št. ogledov: 1087
Št. prenosov: 73
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Walks with random permutations
Sekundarni povzetek: 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.
Sekundarne ključne besede: mathematics;expander graphs;permutation groups;Cayley graph;diameter;random walks;
Vrsta dela (COBISS): Delo diplomskega seminarja/zaključno seminarsko delo/naloga
Študijski program: 0
Komentar na gradivo: Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja
Strani: 32 str.
ID: 16458503