MATH 470, Topics in Graph Theory: Graph Colouring and Graph Convergence

This page is under construction

Meetings

  • Organizational meeting: Wednesday, December 9, 16:00, Burnside 1234.
  • Tuesday, 13:30-14:30, Burnside 1234
  • Thursday, 13:30-14:30, Burnside 719A [not on February 28]
  • There will be NO lecture on Thursday, February 28.
    • Course web page: http://www.math.mcgill.ca/jakobson/courses/math470-19-graphs.html
    Instructor: D. Jakobson
    Office: BH1220
    Office Hours: TBA
    Tel: 398-3828
    E-mail: dmitry.jakobson AT mcgill.ca
    Web Page: www.math.mcgill.ca/jakobson

    Texts

  • N. Biggs. Algebraic Graph Theory
  • J. Bondy and U. Murty. Graph Theory with Applications

    • Texts (recommended)

  • R. Diestel. Graph Theory, electronic edition (you can download the pdf file anonymously from that site).
  • B. Bollobas. Graph Theory: an introductory course

    • Outline

  • The course will focus on the following topics: graph colouring, planarity, chromatic and dichromatic polynomials, graph convergence, asymptotic behaviour of graph polynomials. Additional topics will be considered as time permits

    • Grading

  • Class lectures and a short report.

    • 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.
  • Fractional colouring and applications
  • Chromatic polynomials for digraphs
  • Ising model, Potts model on graphs (a lot of material here!)
  • Knot polynomials
  • Bollobas-Riordan polynomials
  • Krushkal-Renardi polynomials
  • Ribbon graphs
  • Subgraph recognition problems
  • Expander graphs, their constructions and applications; Ramanujan graphs
  • Cayley graphs
  • convergence for "dense" graphs (e.g. graphon convergence)
  • Erdos-Renyi graphs
  • Rank and Tutte polynomials: transformation formulas
  • Convergence of "harmonic moments"
  • Graph algorithms: colouring, depth-first and breadth-first searches; labelling algorithm for network flows; applications of expanders in sorting etc (there may be several talks)
  • Wiener index (mean distance) and Laplacians on trees
  • Young tableaux
  • Colin de Verdiere's graph invariant
  • Various constructions of expanders (there may be several talks related to different constructions)
  • Flow-colouring duality
  • The structure of 2-connected and 3-connected graphs
  • Edge-disjoint spanning trees
  • Graph reconstruction
  • Shannon capacity
  • Tait coloring
  • TO BE CONTINUED!
  • If you want to speak about a topic that is not on the list, please let me know!

    • Web Links

  • Benjamini-Schramm convergence in group theory and dynamics: L. Bowen's talk at Princeton
  • Benjamini-Schramm convergence of graphs: google scholar search.
  • 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.
    • HELPDESK and their email: helpdesk@math.mcgill.ca
    NOTICE: McGill University values academic integrity. Therefore, all students must understand the meaning and consequences of cheating, plagiarism and other academic offences under the Code of Student Conduct and Disciplinary Procedures (see McGill web page on Academic Integrity for more information).
    NOTICE: In accord with McGill University's Charter of Student Rights, students in this course have the right to submit in English or in French any work that is to be graded.
    NOTICE: In the event of extraordinary circumstances beyond the University's control, the content and/or evaluation scheme in this course is subject to change