搜索:
 
 当前位置:>首页 -> 学术报告
12-24吴文俊数学重点实验室组合图论系列讲座之127【Jacques Verstraete】
报告题目: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.
  科大主页 | 国家数学与交叉科学中心(合肥) | 中科院吴文俊数学重点实验室 |
中科院数学与系统科学研究院 | 北京国际数学研究中心 | 安徽省数学会