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.
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.)
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.
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.
to contact Goren directly to make special
arrangements.
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.
Eyal Goren
Schedule of Lectures
Lecturer
and
date 
Topics 
Notes 
Dylan AttwellDuval, 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 AlonMilman 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 AlonBoppana theorem (including proof). Again, see HLW for
references. 
here

Atefeh Mohajeri, January 29, 2010 
padic 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: Padic numbers, padic analysis, and zetafunctions. The structure of lattices in Q_p^2 and the BruhatTits 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
BruhatTits 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, 151 and no. 2, 97126.). For the rest, a place to
start is LubotzkySamuelVishne paper. 
here 
Neil Olver, February 5, 2010 
The zigzag product of graphs.
See HLW. 
here

Cameron Franc, February 12, 2010 
Cayley graphs and the works of
Helfgott, generalized by BourgainGamburd, Kassabov, and
KassabovLubotzkyNikolov. 
here 
Xander Faber, February 12, 2010 
Cayley graphs and semidirect 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 BroederShamir. 
Some References
Hoory, Linial,
Wigderson
Lubotzky, Samuels, Vishne
Kassabov, Lubotzky,
Nikolov
Reingold, Vadhan,
Wigderson