Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, January 30, 2001 - 4:30pm

Felix Lazebnik

University of Delaware

Location

University of Pennsylvania

DRL 4N30

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?