(Extremal) Graph Theory and other extremal problems

Tibor Szabó

Institute of Mathematics
Freie Universität Berlin

Transversals and relaxed colorings of graphs with bounded degree
Norm-graphs and Zarankiewicz problem
Other extremal problems

Transversals and relaxed colorings of graphs with bounded degree

There are two related topics here; in both we are given a graph of bounded maximum degree.
I: An adversary picks a partition of the vertex set into classes of pre-described sizes and we must select a transversal (i.e. one vertex of each part) such that the subgraph induced on it has some "nice" structure. How large should the parts of the partitions be such that we succeed no matter what the adversary does? A basic example is a theorem of Haxell, which claims that if the part sizes are at least two times the maximum degree than one can select an independent transversal. Besides having several applications, the study of independent transversals inspired numerous completely different approaches utilizing not only combinatorial but probabilistic or topological ideas.
II: In the second line of problems one would like to color the graph such that each monochromatic component is small, i.e. its order is less than a constant (depending only on the maximum degree and not the graph!). This concept generalizes the usual concept of proper coloring.

Norm-graphs and the Zarankiewicz problem

The Turán number ex(n,H) of a graph H is the largest integer e such that there exists a graph on n vertices with e edges which does not contain H as a subgraph. The asymptotic behavior of ex(n,H) is well understood if the chromatic number of H is at least three. Our knowledge is very sparse though for bipartite H. A very old and notorious open problem is to determine the Turán number of complete bipartite graphs (a slightly different but very much related question is the so-called Zarankiewicz problem). The conjectured order of magnitude of ex(n, Kt,s) is n2-1/min{t,s}, coming from the fifty year old upper bound of Kővari, T. Sós and Turán.
The problem is open already for K4,4.

Other extremal problems

Valid HTML 4.0! Last modified: Sun Jun 30 22:36:47 CEST 2013