The Turan-type extremal theory asks for the maximal number of edges in
an n vertex simple graph avoiding a (few) fix forbidden subgraph(s). It
originates from the exact results of Mantel and Turan about forbidden
complete graphs. By adding a linear order on either the vertices or the
edges of the graphs considered we can extend the theory by forbidding a
subgraph in one given order. This yields the extremal theories of vertex
ordered and edge ordered graphs.
The most general result in the Turan-type extremal graph theory is the
Erdos-Stone-Simonovits theorem stating that the maximum number of edges
in a n vertex graph avoiding the forbidden subgraph H is asymptotically
1-1/r fraction of the number of edges of the complete graph, where r+1
is the chromatic number of H. This gives the asymptotically tight result
whenever H is not bipartite.
With Janos Pach we generalized this result to vertex ordered graphs. The
same statement holds there with *interval chromatic number* replacing
the ordinary chromatic number. This notion is (algorithmically) much
simpler than the original chromatic number.
With Daniel Gerbner, Abhishek Methuku, Daniel Nagy, Domotor Palvolgyi
and Mate Vizer we managed to find the generalization to edge ordered
graphs too, but the correct variant of the chromatic number, the *order
chromatic number*, turns out to be much more complicated. The talk will
focus on showing some interesting properties of the order chromatic
number, including that
- the order chromatic number of an edge ordered graph can be infinite or
finite but much larger than the size of the graph,
- in case we have more than one forbidden edge ordered graph, the
asymptotics of the extremal number is *not* determined by the smallest
of the order chromatic numbers of the forbidden subgraphs (as it is the
case in the classic and the vertex ordered theories), but has to
determined for the forbidden family.
On the next seminar (April 11) Dani Gerbner will speak about the
extremal functions of forbidden edge ordered graphs of order chromatic
number 2 - just as in the classical extremal graph theory the
Erdos-Stone-Simonovits theorem gives very little information in this
case.
VENUE: Rényi Institute, Nagyterem