报告题目：Solution to the extremal problem for ordered trees

报告人： Jacques Verstraete  （Department of Mathematics, University of California, San Diego）

时间：12月24日（周一）下午 15:00-16:00

地点：1318

摘要：

An {\em ordered graph} is a graph together with a linear ordering of its vertices. For an ordered graph $F$, let $\ex_{\rightarrow}(n,F)$ denote the maximum number of edges in an $n$-vertex ordered graph that does not contain a copy of $F$. In this talk we show that there exists a family $\mathcal{T}$ of ordered trees such that for every ordered tree $T \in \mathcal{T}$ with $k$ edges and $n \geq k + 1$, 

\[ \ex_{\rightarrow}(n,T) = (k - 1)n - {k \choose 2} \] and for every ordered tree $T \not \in \mathcal{T}$, $\ex_{\rightarrow}(n,T) = \Omega(n\log n)$. This partially addresses questions of Bra{\ss} and Pach and Tardos.