Please also study the 2011 problem set which includes definitions.
Can you prove that a random permutation of $n$ elements has on average $\sim \ln n$ cycles?
Can you prove that Petersen's graph has 120 automorphisms, as does the dodecahedron? Can you show that these two groups are not isomorphic but have a lot in common?
If two graphs are not isomorphic, is there a short proof of this fact?
How long does it take to get from the generators to the farthest corners of a finite group of order $n$? Can you get there in $O(\log^2 n)$ steps?
Can we decide quickly if a randomly assembled (generalized) Rubik's cube is feasible?
We study the asymptotic complexity of questions like these, especially in the contexts of permutation groups and matrix groups over finite fields. Along the way we need to learn about the structure of primitive permutation groups, about methods to estimate their orders, about statistical properties of finite simple groups. We shall also learn about combinatorial properties of vertex-transitive graphs and random walks on such graphs.
The methods range from elementary combinatorial and probabilistic ideas and elementary group theory to applications of simply stated consequences of the classification of finite simple groups and occasionally, detailed information about finite simple groups.
In this class we prove (fun) theorems. This is not an "applied math" course; emphasis is on mathematical elegance. "Efficient" usually means "polynomial time." There will be no programming assignments.
Prerequisites. Linear algebra, finite fields, introductory group theory. No advance knowledge of graph theory or algorithms is required.
Office hours: by appointment (please send e-mail)
Classes: TuTh 1:30 - 2:50, Ry-276
LAST CLASS: Thursday, December 4. Attendace expected.
Your primary text will be your course notes, so please make sure you don't miss classes. If you do, you should copy somebody's class notes and discuss the class with them.
You can find asymptotic notation, the graph theoretic terminology, and the basics of discrete probability to be used in class in the Instructor's Discrete Mathematics Lecture Notes (PDF)
Printed text:
John D. Dixon and Brian Mortimer: "Permutation Groups." Published by Springer, ISBN 0-387-94599-7
Recommended references:
Joseph Rotman: "An Introduction to the Theory of Groups." Published by Springer, ISBN 0-387-94285-8
Ákos Seress: "Permutation Group Algorithms." Cambridge University Press, ISBN 0 521 66103
If a quality grade is desired, please let the instructor know asap.