We survey some basic problems and results, concentrating mostly on the so-called Turan - type problems. Simple examples of the latter include: What is the greatest number of edges a simple graph on n vertices can have if it (i) does not contain a triangle (cycle of length 3) as a subgraph? (ii) does not contain K_4 (complete graph on four vertices) as a subgraph? (iii) does not contain a path of length k as a subgraph?
Probability and Combinatorics
Tuesday, January 30, 2001 - 4:30pm
Felix Lazebnik
University of Delaware