DIMACS Discrete Math/Theory of Computing Seminar


Title:

Extremal Graph Theory: Old problems and New Results

Speaker:

Felix Labeznik
University of Delaware

Place:

DIMACS Center, CoRE Building, Seminar Room 431
Rutgers University

Time:

4:30 PM
Tuesday, February 18, 1997
Abstract:

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