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.
Grading: The breakup grades are homework 50% and presentation 50%.