Extremal and Probabilistic Graph Theory, 2016 Spring, USTC

Instructor:

  • Âí½Ü, Email: jiema@ustc.edu.cn, Office: 1603, School of Math

  • Lecture Outline:

    Lecture 1

    Definitions on Turan problems

    Lecture 2

    Kovari-Sos-Turan Theorem, Turan density for blowups of complete k-partite k-graphs.

    Lecture 3

    Supersaturation Lemma, Turan density on blowups

    Lecture 4

    Kovari-Sos-Turan Theorem for Hypergraphs, Counting the number of blowups of complete k-partite k-graphs.

    Lecture 5

    Turan's Theorem, Erdos-Stone-Simonovits Theorem

    Lecture 6

    A quantitative bound of Erdos-Stone-Simonovits Theorem, Moon-Moser inequalities

    Lecture 7

    An upper bound on Turan numbers of complete hypergraphs (De-Caen's Theorem)

    Lecture 8

    A lower bound on Turan numbers of complete hypergraphs

    Lecture 9

    Simonovits' stability Theorem, Furedi's new proof on the stability of ex(n,K_r)

    Lecture 10

    Turan numbers of edge-critical graphs - an application of the stability method, definition of decomposition family

    Lecture 11

    Andrasfai-Erdos-Sos Theorem, Chromatic threshold

    Lecture 12

    Erdos-Sos conjecture on the Turan numbers of trees, Path lengths in graphs, Posa's rotation, Closure, Hamiltonian properties.

    Lecture 13

    Cycle lengths in 2-connected graphs, A theorem of Erdos-Gallai on cycles.

    Lecture 14

    Counting the number of walks.

    Lecture 15

    Counting the number of non-backtracting walks, and Moore Bound.

    Lecture 16-18

    Hoffman-Singleton Theorem, Bondy-Simonovits Theorem on the upper bound of ex(n,C_{2k}).

    Lecture 19

    Number of consecutive even cycles in graphs with large average degree and large girth; dependent random choice I

    Lecture 20

    Dependent random choice II

    Lecture 21

    Dependent random choice III; the general bounds on Turan numbers of bipartite graphs.

    Lecture 22-23

    Szemeredi's regularity lemma