A working seminar on the topics of Expander Graphs and on Point counting (MATH 667), Winter 2010


Original announcement

Instructors: Profs. Henri Darmon and Eyal Goren.

Time: Winter 2010 (TBA). First meeting on Jan. 7, 2010 at 10:00 in BURN 920.

This working seminar has as one of its goals to provide students with preparation
for some of the workshops in the scope of the thematic semester at the CRM
"Number Theory as Experimental and Applied Science"
(see www.crm.umontreal.ca/NT2010/ for details.)

Goren will take responsibility of the seminar during the months of January Ð February.
This part of the seminar will be devoted to topics in expander graphs, using the
paper by Hoory, Linial and Wigderson (Bull. AMS, 43 (2006)) as our main text.
The requirement from the students is to present a 2 hour lecture on a topic selected
together with the instructor and to participate in the weekly meetings.

Darmon will take responsibility of the seminar during the months of March Ð April.
This part of the seminar will be devoted to point counting on algebraic varieties
in positive characteristic and the machinery that goes into it. For addition details,
please contact Darmon.

Students wishing to take the seminar, but study only expander graphs, are invited
to contact Goren directly to make special arrangements.

The first meeting of the seminar is on Thursday, January 7, at 10:00.
In this meeting, an overview of the topics to be covered in the seminar is to be provided
and we shall also fix a time for the future meetings. Students unable to attend the
meeting but are firm in their intention to enroll are invited to contact Goren by email
to let us know their time restrictions.

Henri Darmon                                                                                 
Eyal Goren

Schedule of Lectures

Lecturer and date
Topics
Notes
Dylan Attwell-Duval, January 22, 2010
Basic notions of graphs (connected, simple, regular, degree, adjacency matrix)
Basic properties of the adjacency matrix A and 1/d(I - A) as a combinatorial laplacian. (for example that d is the maximal eval, that it has mult 1 if the graph is connected, that -d is eval iff the graph is bipartite)
Proof of the Alon-Milman theorem (see references in HLW)
Proof of the expander mixing lemma (see HLW).
Some basic examples to illustrate all this.
here
Victoria de Quehen, January 22, 2010.
ore examples and applications of expanders. Here follow the "magical mystery tour" of HLW and present 3 applications:
1. To error correcting codes using the bipartite expander;
2. To superconcentrators;
3. To construction of hash functions. The idea is exceedingly simple. Follow Goren's paper with Charles and Lauter and use the note by Dana Mackenzie to get a feeling to what's going on. Both available from http://www.math.mcgill.ca/goren/publications.html
here
Luiz Takei, January 29, 2010
The combinatorial laplacian on the infinite tree and its action on L^2 functions. The spectrum of this operator + a proof (or at least a sketch of proof of this result). See HLW for basic discussion and references. Definition of Ramanujan graphs. The Alon-Boppana theorem (including proof). Again, see HLW for references.
here
Atefeh Mohajeri, January 29, 2010
p-adic numbers (Q_p only). Here give a very quick resume and prepare an exercise set to allow anyone interested to complete the details. Follow the book by Koblitz:
P-adic numbers, p-adic analysis, and zeta-functions. The structure of lattices in Q_p^2 and the Bruhat-Tits tree of GL_2.
here
and
here
Andrew Fiori,  February 5, 2010
The building of GL_n (we want to see it from the perspective of parabolic subgroups and the Weyl group and not from the combinatorial perspective) - it generalizes the Bruhat-Tits tree. Combinatorial Laplacians on that building and the definition of Ramanujan complexes. A reference for buildings is two survey papers written by Mark Ronan ( Bull. London Math. Soc. 24 (1992), no. 1, 1--51 and no. 2, 97--126.). For the rest, a place to start is Lubotzky-Samuel-Vishne paper.
here
Neil Olver, February 5, 2010
The zig-zag product of graphs. See HLW.
here
Cameron Franc, February 12, 2010
Cayley graphs and the works of Helfgott, generalized by Bourgain-Gamburd, Kassabov, and Kassabov-Lubotzky-Nikolov.
here
Xander Faber, February 12, 2010

Cayley graphs and semi-direct product of groups.

Christophe Weibel, February 19, 2010 Random graphs: basic notions and typical applications.

 
Ben Young, February 19, 2010 Survey of Fredman's theorem: given any epsilon, almost all graphs are Ramanujan. A more detailed result of an earlier result, due to Broeder-Shamir.

Some References

Hoory, Linial, Wigderson
Lubotzky, Samuels, Vishne
Kassabov, Lubotzky, Nikolov
Reingold, Vadhan, Wigderson

Pyber, Szabo
Breuillard, Green, Tao