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
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
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
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
only expander graphs, are invited
to contact Goren directly to make special arrangements.
The first meeting of the
seminar is on
January 7, at 10:00. Henri Darmon
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.
Schedule of Lectures
|Dylan Attwell-Duval, January 22,
||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.
|Victoria de Quehen, January 22,
||ore examples and applications of
expanders. Here follow the "magical mystery tour" of HLW and present 3
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
|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
|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.
|Andrew Fiori, February 5,
||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.
|Neil Olver, February 5, 2010
||The zig-zag product of graphs.
|Cameron Franc, February 12, 2010
||Cayley graphs and the works of
Helfgott, generalized by Bourgain-Gamburd, Kassabov, and
|Xander Faber, February 12, 2010
Cayley graphs and semi-direct product of groups.
|Christophe Weibel, February 19, 2010||Random graphs: basic notions and
|Ben Young, February 19, 2010||Survey of Fredman's theorem:
epsilon, almost all graphs are Ramanujan. A more detailed result of an
earlier result, due to Broeder-Shamir.