DIMACS Discrete Math/Theory of Computing Seminar


Extremal Graph Theory: Old problems and New Results


Felix Labeznik
University of Delaware


DIMACS Center, CoRE Building, Seminar Room 431
Rutgers University


4:30 PM
Tuesday, February 18, 1997

What is the greatest number of edges in a simple graph on $v$ vertices that contains no cycles of length smaller than $k$? What are extremal graphs in this case? This is an example of so-called degenerate extremal problem of Turan type.

In this talk I will

- present a short survey of old and new results on extremal problems of Turan type;

- discuss an algebraic method of constructing some best known examples of graphs with many edges and without certain small cycles;

- discuss some applications of the algebraic method to several problems of extremal graph theory (some of them have already been published but three are new).

Document last modified on February 11, 1997