Math 778: Large Networks and Graph Limits
Fall 2014 Topic Course Syllabus

Instructor:  Prof. Linyuan Lu

Office: LC 400I, Email: lu@math.sc.edu

Office hours: TTh 10:00am--11:30am and by appointment

Lecture time: T Th & 2:50PM- 4:05PM, LeConte College 303B

Credit Hours:  3

Textbook: Large Networks and Graph Limits Laszlo Lovasz, Colloquium Publications, 2012; 475 pp; hardcover Volume: 60, ISBN-10: 0-8218-9085-9, ISBN-13: 978-0-8218-9085-1.

Overview: The course will begin with a description of complex networks and models, and their background in extremal graph theory and statistical physics. We will learn an algebraic theory of graph homomorphisms and an analytic theory of convergence of graph sequences and their limits. The new theory allows the precise formulation of, and often the exact answer to, some very general questions concerning algorithms on large graphs and extremal graph theory. We will also cover Razborov's flag algebra methods, which has lead to the solution of several long-standing open problems in extremal graph theory.

Learning Outcomes: Students will learn basic theory of Graph Limits. They will be able to read research papers and present results in the class. They will combine methods learned from this course and practice them at new problems. Students will demonstrate their problem-solving skills through homework, an exam, and a final project.

Subject Material:   We shall cover the selected material presented in the textbook and other supplemental material from selected papers.

Assessment:   The assessment consists of homework assigments, a mid-exam and a final project. Homework will normally be assigned every other week.

Presentations: All enrolled students are required to make a 20-minute presentation in last two lectures (Dec. 4 and Dec. 6). Here are the list of possible papers.

  1. Alexander Razborov, On the Minimal Density of Triangles in Graphs, in Combinatorics, Probability and Computing, Vol. 17, No 4, 2008, pages 603-618.
  2. Alexander Razborov, On Turan's (3,4)-problem with forbidden configurations, Matematicheskie Zametki, Vol. 95, No 2, 2014, pages 271-281.
  3. R Baber, J Talbot, A solution to the 2/3 conjecture SIAM Journal on Discrete Mathematics 28 (2), 756-766.
  4. J. Balogh, P. Hu, B. Lidicky and H. Liu, Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube, European Journal of Combinatorics, 35 (2014), 75-85.
  5. Svante Janson, Vera T. Sos, More on quasi-random graphs, subgraph counts and graph limits , 2014 arxiv preprint.
  6. Hamed Hatami, Svante Janson, Balazs Szegedy, Graph properties, graph limits and entropy , 2013 arxiv preprint.
  7. Christian Borgs, Jennifer T. Chayes, Henry Cohn, Yufei Zhao, An Lp theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions , 2014 preprint.

Grading: The breakup grades are homework 50% and presentation 50%.