中国科大学位与研究生教育
课程名称: 教师:
当前位置:
 >> 
 >> 
Solution to the extremal problem for ordered trees
Solution to the extremal problem for ordered trees
教师介绍

本讲教师:Jacques Verstraete
所属学科:理科
人  气:316

课程介绍
摘要: 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(nlog n)$. This partially addresses questions of Bra{ss} and Pach and Tardos.

评论

针对该课程没有任何评论,谈谈您对该课程的看法吧?
  • 用户名: 密 码:
致谢:本课件的制作和发布均为公益目的,免费提供给公众学习和研究。对于本课件制作传播过程中可能涉及的作品或作品部分内容的著作权人以及相关权利人谨致谢意!
课件总访问人次:19438902
中国科学技术大学研究生网络课堂试运行版,版权属于中国科学技术大学研究生院。
本网站所有内容属于中国科学技术大学,未经允许不得下载传播。
地址:安徽省合肥市金寨路96号;邮编:230026。TEL:+86-551-63602929;E-mail:wlkt@ustc.edu.cn。