The first two problem sets have been posted. Solve these problems and discover which of them, if any, you find challenging. Tell the instructor (by email). This will help the instructor in designing the course.
If you think you might be interested in this course, please send email to the instructor. Please answer the questionnaire below. It is not at all too early to do so now; it will help the instructor in designing the course.
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.
Please send email to the instructor with answers to these questions, even if you are only sitting in on the class, did not register, or have an unusual status. Your answers to these questions will help me better to plan the course. Please write "CMSC 36500 data" in the subject.
Office hours: by appointment (please send e-mail)
Teaching assistants:
Paolo Codenotti paoloc(at)cs(dot)nameofuniversity(dot)edu
Jimmy Qiao firstnamelastname86(at)gmail(dot)com.
The TAs holds office hours Tuesday 6 - 7 pm in Ry-162 (the "Theory Lounge"). NOTE CHANGE (was Thursday)
Classes: MWF 11:30 - 12:20, Ry-276
LAST CLASS: Friday, June 3. 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
Copies of this book will be sold at the Seminary Bookstore.
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
Grades will be based on homework, tests, and class participation.