Discrete Mathematics, Summer 2006 REU

Instructor: László Babai

What's New? | Course Info | Handouts | Lecture Notes

What's New?

• LAST PROBLEM SESSION. The last class (Friday, August 11) will be a Problem Session. The problem sheet is available.
• Location: Classes are in Eck 202.

Course Info

• Course descriptions, schedules, links
• Instructor: László Babai
  Office: Ry-164, email: laci [at] cs [dt] uchicago [dt] edu

Online text

• L. Babai: Discrete Mathematics (lecture notes, preliminary (Oct 2003) version, 96 pp., in PDF)

Hard copy handouts

• Chapters 2 and 4 of online text (June 20)

Lecture Notes (weeks 1--8)

• Lecture Notes of June 20: the limit of a sequence, the zeta function, the divisor game, arithmetic functions (additive and multiplicative); asymptotics and primes: Stirling's formula, the prime number theorem, Dirichlet's theorem, an interlude on the biographies of Erdős and Turán, asymptotic inequalities; more arithmetic functions: Euler's function, the Möbius μ function,the partition function, a Hardy-Ramanujan formula. PDF
• Lecture Notes of June 22: roots of unity, R_n and μ, probability w.r.t. modular arithmetic and divisibility, Fibonacci numbers and the golden ratio, least common multiples and order of permutation, partitions of n, generating functions. PDF
• Lecture Notes of June 26: permutation groups: degree, support, sign, k-cycles, generators, asymptotics (w/ notation), application to probability. PDF
• Lecture Notes of June 28: solutions to two exercises in asymptotics and probability, Buffon's needle problem, the multinomial theorem, prime partitions, Cayley's theorem, the "handshake" theorem, the Prüfer code. PDF
• Lecture Notes of June 30: review of graph theory terminology, graph isomorphisms and automorphisms, planar graphs, Petersen's graph, automorphisms of trees, automorphisms in random graphs, counting graphs, symmetric groups, the Rubik's cube, matchings. PDF
• Lecture Notes of July 6: symmetries of regular polyhedra and Peterson's graph, Kneser graphs, girth, chromatic number, tournaments. PDF
• Lecture Notes of July 10: results on polynomials, eigenvalues and characteristic polynomials, orthogonality, the spectral theorem, the connection between graph theory and linear algebra: adjacency matrices, proof of the Hoffman-Singleton theorem. PDF
• Lecture Notes of July 12: solutions to a few problems on bipartite subgraphs, embarrassing tournaments, collineations; existence and construction of embarrassing tournaments, a theorem by André Weil. PDF
• Lecture Notes of July 14: group characters, André Weil's character sum estimate, Paley tournament, chromatic number and girth of a graph. PDF
• Lecture Notes of July 24: primality testing: the Monte Carlo algorithm, Mersenne and Fermat primes, Carmichael numbers and their square-freeness, quadratic residues and the Law of Quadratic Reciprocity. PDF
• Lecture Notes of July 26: primality test continued: Chinese remainder theorem, a simple primality test, Jacobi symbol and quadratic reciprocity, the Solovay-Strassen primality test. PDF
• Lecture Notes of July 28: primality test continued: analysis of the Solovay-Strassen test, the Miller-Rabin primality test. PDF
• Lecture Notes of July 31: communication complexity: testing equality of strings, lower bound analysis, communicational complexity, the Mehlhorn-Schmidt theorem. PDF
• Lecture Notes of August 2: communication complexity continued: lower bound analysis continued, distributional complexity; Hadamard matrices. PDF
• Lecture Notes of August 4: communication complexity continued: randomized and distributional complexity, Hadamard matrices, J.H. Lindsey's lemma; Indian head poker. PDF
• Lecture Notes of August 7: Hadamard matrices: construction and eigenvalues; Boolean circuits. PDF
• Lecture Notes of August 9: Boolean circuits continued: Yao-Håstad theorem, Razborov-Smolensky theorem. PDF