189-480B/189-695B, A reading course in Combinatorics and Graph Theory

Lectures

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

    • Student Talks

  • David Braun. Tuesday, February 27: Depth First Search, Breadth First Search
  • Derrick Chung. 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
  • Jean-Martin Albert. 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
  • Bogdan Nica. Thursday, March 22: Sharkovski's theorem and related questions in Graph Theory (continued on March 27)
  • Louigi Addario-Berry. 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

    • Instructor

  • Dmitry Jakobson
  • Office: BURN 1212. Phone: 398-3828. Email: jakobson@math
  • Office hours: Tuesday 11:30-12:30, Wednesday 11-12 or by appointment.

    • Texts (Recommended)

  • N. Biggs. Discrete Mathematics
  • R. Diestel. Graph Theory, electronic edition (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)

    • Outline

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

    • Grading

  • 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)
  • Chromatic polynomials
  • Polya's theorem
  • Knot theory
  • Subgraph recognition problems and applications in computer vision
  • Group Rings, Hall's Multiplier Theorem
  • Cayley graphs, see this link for definitions
  • 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)
  • Unclaimed topics:
  • Wiener index (mean distance) and Laplacians on trees
  • The N-queens problem
  • Young tableaux
  • Asymptotics for the partition number
  • Squared squares
  • 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)
  • Prufer coding
  • Graph addressing problems
  • Group-valued flows
  • Flow-colouring duality
  • The structure of 2-connected and 3-connected graphs
  • Edge-disjoint spanning trees
  • Graph reconstruction
  • Permanents
  • The Van der Waerden conjecture
  • Bruck-Ryser-Chowla theorem
  • De Bruijn graphs and sequences
  • Association schemes
  • Shannon capacity
  • Tait coloring
  • Ringel-Youngs theorem
  • Catalan numbers
  • Lattices and Mobius inversion
  • Baranyai's theorem
  • Hadamard product of matrices
  • If you want to speak about a topic that is not on the list, please let me know!

    • Problem sets

  • Problem set 1 (due Thursday, Jan. 18), covering Ch. 8, sections 8.1 - 8.5 of Biggs' book. Turn in: 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. Practice problems (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: postscript, pdf. Practice problems (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 Ka,b

  • 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. Additional problem: postscript, pdf. Practice problems (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. Practice problems (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. Practice problems (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. Practice problems will be added later.

  • Everybody is excused from two 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 Z/pZ; Linear Algebra - matrices, determinants, eigenvalues and eigenvectors, Cauchy-Binet theorem.
  • If you haven't seen graphs before, you can look at a nice online graph glossary, work through a few tutorials, and do some exercises at Mathmania. This site also has a nice introduction to knots and other things.
  • A previous site is very similar to the Mega-Math page at Los Alamos.
  • A nice online course in graph theory.
  • Online graph theory glossaries: 1, 2
  • Other nice online introductions to graph theory problems: The bridges of Königsberg; spanning trees; Three Houses, Three Utilities; Travelling Salesman

    • Web Links

  • 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. Titre: 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 at CRM
  • McGill, Dept. of Mathematics and Statistics
  • McGill, Dept. of Computer Science
  • LaCIM
  • CRM:L'Officiel
  • Univ. of Waterloo, Dept. of Combinatorics and Optimization
  • DIMACS
  • Centre for Discrete and Applicable Math, London School of Economics
  • Electronic Journal of Combinatorics, World Combinatorics Exchange
  • SIAM activity group on Discrete Mathematics
  • Combinatorics: UC Davis front end for Loas Alamos e-print archive
  • Combinatorics Net
  • Graph Theorists: White pages and another list
  • Google directories in Combinatorics and Graph Theory
  • Math Archives: Combinatorics
  • Erdös Number page
  • The Four Colour Theorem (proved in 1976 by Appel and Haken): history, and a new proof (by Robertson, Sanders, Seymour and Thomas).
  • Combinatorial Catalogues
  • Databases for Moore graphs, cages etc: M. Meringer, G. Royle, WCE page
  • The Hamiltonian page
  • The Steiner Tree page
  • Open problems: a list at DIMACS; Topological Graph Theory; Graph Coloring; an enlarged list of Bondy and Murty (by C. Locke); The Geometry Junkyard; Perfect Graphs; MathSoft list (general math).
  • Brendan McKay
  • "Can you hear the shape of the drum?" pages: short history, and a paper by Buser, Conway, Doyle and Semmler
  • Web applications (search engines): a paper by S. Brin and L. Page (founders of Google), and a later paper on web page reputations by D. Rafiei and A. Mendelzon.