报告题目：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.