Math776 Graph Theory, Fall 2005

Math 777 Graph Theory (II), Spring 2006

Under construction.

Instructor: Prof. Lincoln Lu EMAIL: lu@math.sc.edu Time: T Th 2:00p.m.--3:15p.m. Classroom: LC 310 Office Hours: LC 418B T 1p.m.-2p.m. Th 1p.m.-2p.m. or by appointment.	Reference books: Complex graphs and networks, F.~Chung and L.~Lu, in preparation, some chapters are available here. Introduction to Graph Theory, second edition, by Douglas B. West, 2001. Graph Theory with Applications by J. A. Bondy and U. S. R. Murty, 1976. Graph Theory by R. Diestel., 2001. Grading Policy: Homeworks 30% Midterm 35% Final project 35%

Week 1-2: homework 1, lecture note 1.
Contents: Planar graphs, dual graphs, Euler formular, Kuratowski's theorem, Five Color theorem, and crossing numbers.
Week 3-5 homework 2, lecture note 2.
Contents: Discrete probability space, expected value, Ramsey number R(n,n), deletion method, Markov's inequality, theorem of Caro and Wei, Erdos-Renyi random graphs, Lovasz local lemma, Ramsy number R(3,n).
Week 6-9 homework 3 is now due to March 14. Read Chapter 2.
Contents: Binomial distribution, normal distribution, Poisson distribution, variance, deviation inequalities for the sum of independent variables, Chernoff's inequality, margtingales, Azuma's inequality, and various inqualities for sub-martingales and super-martingales.
We will have the midterm on March 21, Tuesday. The problems are similar to those in homeworks. Here is the solution of homework 3.