Norm-graphs and multicolor Ramsey numbers

Tibor Szabo

University of Illinois at Urbana-Champaign

April 9,
refreshments at 3:45pm


Determining the maximum number of edges an $n$-vertex simple graph can have when it does NOT contain a fixed subgraph $H$ is one of the oldest and most-studied problems of Extremal Graph Theory. The value is called the {\it Tur\'an number} $ex(n;H)$. {\it Norm-graphs} were introduced in a paper by Koll\'ar, R\'onyai and the speaker to answer this question when $H$ is a complete bipartite graph with appropriate part-sizes. In this talk we define norm-graphs and discuss some variations and generalizations of them. We obtain new sharp bounds for the Tur\'an number of complete bipartite graphs. Applications in Discrepancy Theory and Ramsey Theory will also be presented. This talk presents joint work with Noga Alon and Lajos R\'onyai.

Speaker's Contact Info: tszabo(at-sign)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on March 29, 1999 at 12:32 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.