Hebrew University 
Amitsur Algebra Seminar
Time: Thursday, March 17, at 12:00.
Place: room 209, Mathematics building
Speaker: Ori Hacohen (HUJI)
Title: On the Diameter of Cayley Graphs of the Symmetric Group.
Let G be a finite group and let S be a generating subset of G. The
pair (G, S) determines a connected Cayley graph, the vertices of which
are the elements of G and the edges of which are { {g,sg} : g in G, s
in S}. The diameter of this graph is the smallest integer d such that
every element of G can be expressed as a word of length d using
elements from S U S^-1. We discuss the diameter of Cayley graphs of
the symmetric group Sn. We focus on "slow" (or "worst case")
generators, giving maximum diameter. Babai & Seress conjecture that
the maximum diameter of Sn is polynomial in n. However, the best
result found thus far bounds the diameter by exp[sqrt(n ln(n))
(1+o(1))] (Babai & Seress, 1988). We prove this result and mention
related, more recent, results.
You are cordially invited!
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from: Gili Schul   <gili.schul@mail.huji.ac.il>