189-480B/189-695B, A reading course in Combinatorics and Graph Theory
Tuesday, Thursday 2:30-4pm, BURN 1234.
There will be on class on Thursday, February 8. However, you can meet to discuss the solutions of homework problems.
Tuesday, February 27: Depth First Search, Breadth First Search
Thursday, March 8: Sperner's Lemma, Brouwer's Fixed Point Theorem
Pavel Dimitrov and Carlos Phillips.
Thursday, March 15: Subgraph Isomorphism and related problems in Computer Vision
Thursday, March 15: Ramsey Theory
Olivier Dubois and Martin Gagne.
Tuesday, March 20: Knot Theory
Norm Ferns and Scott Shafer.
Thursday, March 22: Chromatic Polynomials
Thursday, March 22: Sharkovski's theorem and related questions in Graph Theory (continued on March 27)
Tuesday, March 27: Group Rings
Kristina Loeschner and Alice McLeod.
Thursday, March 29: Polya's Theorem
Clotilde Paris de Bollardiere.
Tuesday, April 3: Cayley Graphs
Office: BURN 1212. Phone: 398-3828. Email: jakobson@math
Office hours: Tuesday 11:30-12:30, Wednesday 11-12 or by appointment.
N. Biggs. Discrete Mathematics
R. Diestel. Graph Theory,
(you can download the pdf file anonymously from that site).
B. Bollobas. Graph Theory: an introductory course (on reserve)
J. Bondy and U. Murty. Graph Theory with Applications (doesn't seem to be in the library)
J. van Lint and R. Wilson. A course in combinatorics (on reserve)
Some of the possible topics: graphs, trees, matching problems, networks and flows, connectivity, colouring problems, planarity, independent sets, graph Laplacians, expanders, extremal graph theory; finite geometries, generating functions, partitions, error-correcting codes. If you would like to discuss some other topics, please email me your suggestions!
(As of February 6): starting from next week, we shall be doing more Combinatorics and Group Theory (rather than Graph Theory), mostly the material from Biggs covered in Problem sets 5 and 6. Also, a lot of time will be devoted to your talks (so get ready!) Finally, I plan to explain the proof of Kuratowski's theorem (Diestel, Chapter 4), and maybe talk a little bit about expanders some time after the break.
Problem sets - 30%.
A 30-60 minute talk in class - 70%. Two people may give a talk together.
Topics for the talks
In the talk you should discuss a particular problem or a set of problems in combinatorics or graph theory. You should present the main ideas; it is not necessary to present all the technical details, but you should be prepared to answer questions about the results you present.
A suggestion: if you are currently working on a project related to combinatorics or graph theory, you can speak about it in class later in the term.
Topics that were chosen:
Sharkovski's theorem (Nica)
Ramsey theory, see Diestel, Chapter 9 for definitions
Sperner's lemma and a combinatorial proof of Brouwer's fixed point theorem (Chung)
Subgraph recognition problems and applications in computer vision
Group Rings, Hall's Multiplier Theorem
Cayley graphs, see this
Graph algorithms: depth-first and breadth-first searches (Braun); labelling algorithm for network flows; applications of expanders in sorting etc (there may be several talks, and I can give a talk or two myself)
Wiener index (mean distance) and Laplacians on trees
The N-queens problem
Asymptotics for the partition number
Colin de Verdiere's graph invariant
Various constructions of expanders (there may be several talks related to different constructions, and I may give a lecture or two myself)
Graph addressing problems
The structure of 2-connected and 3-connected graphs
Edge-disjoint spanning trees
The Van der Waerden conjecture
De Bruijn graphs and sequences
Lattices and Mobius inversion
Hadamard product of matrices
If you want to speak about a topic that is not on the list, please let me know!
Problem set 1
(due Thursday, Jan. 18), covering Ch. 8, sections 8.1 - 8.5 of Biggs' book.
Biggs, Ch. 8 (pp. 177-178), #4, 7, 14, 18, 19. Additional problem: Let A be the adjacency matrix of a connected graph G that has diameter d. Prove that the degree of the minimal polynomial of A is at least d.
(don't turn them in): Biggs, p. 162 (section 8.2), #1,2; p. 165 (section 8.4), #2,5; p. 171, #1; p. 177, #3, 5, 6, 12
Problem set 2
(due Tuesday, Jan. 30), covering Diestel (section 1.9) and the matrix tree (Kirchhoff's) theorem.
Problems to turn in:
(don't turn in). For a $k$-regular graph $G$, prove that $k$ is an eigenvalue whose multiplicity is equal to the number of connected components of $G$ Find the eigenvalues and tree numbers of the $n$-cube, the Petersen graph, and the complete graph K
Problem set 3
(due Thursday, March. 1), covering Diestel, (sections 3.3, 6.1, 6.2) and Biggs (sections 11.1-11.4).
Problems to turn in:
Prove that in a two-connected graph with at least three vertices, any two vertices can be joined by two internally disjoint paths (DO NOT use any results about flows in networks). Biggs, Ch. 11, p. 246, # 3, 6, 12.
Ignore problem 15 on p. 247; it is wrong as stated.
(don't turn in). Biggs, Ch. 11, p. 230 (section 11.1), #2,4; p. 233 (section 11.2), #1; p. 237 (section 11.3), #1; p. 240 (section 11.4), #1,2.
Problem set 4
(due Thursday, March 8), covering Biggs (sections 8.6, 8.7; sections 10.1-10.5) and Diestel (chapters 2 and 4).
Problems to turn in:
Biggs, Ch. 8, p. 179, #22. Ch. 10, p. 225, #1,5,7,10,17.
(don't turn in). Biggs, Ch. 10 p. 209 (section 10.2) #2; p. 211 (section 10.3) #4,5,6; p. 219 (section 10.4) #2,3; p. 223 (section 10.5) #2,3. A funny "practice" problem: assume that you know that any FINITE map in the plane is 4-colourable; prove the same statement for a (countably) INFINITE map.
Problem set 5
(due Tuesday, March 20), covering Biggs, sections 4.4-4.7, 6.4-6.5, 10.3, 16.5-16.8.
Turn in SIX
of the following problems: Biggs, Ch. 4, p. 87, #8,10; Ch. 6, p. 130, #15,20; Ch. 10, p. 226, #10; Ch. 16, p. 372, #5,10,12.
(don't turn in). Biggs, p. 74, #2,4,5; p. 78 #2,3; p. 79 #5 (there is a typo in the formula for phi(n)); p. 83, #2,3,4; p. 86 #2,4; p. 87 #4,13,16,18,19; p. 125 #3,4; p. 128 #2,4; p. 130 #11,13,17; p. 215 #2,3; p. 226 # 11,20; p. 354 #1,2,4; p. 357 #2,3; p. 360 #2,3,4; p. 364 #2,4,5; p. 367 #1,3,4; p. 372 #7,8,11,14,17.
Problem set 6
(due Thursday, March 29), covering Biggs, sections 5.1-5.5, Chapters 18, 19. Also, review Chapter 14.
Turn in SIX
of the following problems: Biggs, Ch. 5, p. 111, #10,12,19; Ch. 14, p. 319, #7,[20 and 21]; Ch. 18, p. 421, #10,13,17,20; Ch. 19, p. 439, #4,8,11,16.
will be added later.
Everybody is excused from
of the problem sets 4,5,6 (so that you have time to prepare for your talk). You can choose which problem sets you would like to skip; I'll adjust the grading so that every problem set has the same maximal score.
How to get started
Things to review (we shall review some of them later, but it's a good idea to start early): Groups - permutations, subgroups, cosets, Lagrange's theorem, cyclic groups; Rings - polynomials, Euclidean algorithm for polynomials and integers, greatest common divisor, prime factorization, fields
; Linear Algebra - matrices, determinants, eigenvalues and eigenvectors, Cauchy-Binet theorem.
If you haven't seen graphs before, you can look at a nice online
, work through a few
, and do some
. This site also has a nice introduction to
and other things.
A previous site is very similar to the
page at Los Alamos.
A nice online
in graph theory.
Online graph theory glossaries:
Other nice online introductions to graph theory problems:
The bridges of Königsberg
Three Houses, Three Utilities
13h15 SÉMINAIRE/SEMINAR (Combinatoire et informatique mathématique): UQAM, Pav. Président-Kennedy, 201, av. Président-Kennedy, salle PK-4323 Conférencier: Christophe Reutenauer, Université de Strasbourg et LaCIM-UQAM.
Sur l'inverse d'un mot.
There will be a special lecture by Dr. Vera Rosta on "Generalized and Geometric Ramsey numbers" on Monday, February 5, from 15:30-16:30 in Burnside 920. The abstract is on the bulletin board on the 10th floor.
A year on
Groups and Geometry
McGill, Dept. of Mathematics and Statistics
McGill, Dept. of Computer Science
Univ. of Waterloo, Dept. of Combinatorics and Optimization
Centre for Discrete and Applicable Math,
London School of Economics
Electronic Journal of Combinatorics, World Combinatorics Exchange
SIAM activity group on Discrete Mathematics
UC Davis front end for Loas Alamos e-print archive
Google directories in
Math Archives: Combinatorics
Erdös Number page
The Four Colour Theorem (proved in 1976 by Appel and Haken):
, and a
(by Robertson, Sanders, Seymour and Thomas).
Databases for Moore graphs, cages etc:
The Hamiltonian page
The Steiner Tree page
Open problems: a
Topological Graph Theory
; an enlarged
of Bondy and Murty (by C. Locke);
The Geometry Junkyard
"Can you hear the shape of the drum?" pages:
, and a
by Buser, Conway, Doyle and Semmler
Web applications (search engines): a
by S. Brin and L. Page (founders of
), and a
on web page reputations by D. Rafiei and