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 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