首页 | 本学科首页   官方微博 | 高级检索  
     


On the trace of finite sets
Authors:Peter Frankl
Affiliation:CNRS, Paris, France and TATA Institute, Bombay, India
Abstract:For a family T of subsets of an n-set X we define the trace of it on a subset Y of X by TT(Y) = {F∩Y:F?T}. We say that (m,n) → (r,s) if for every T with |T| ?m we can find a Y?X|Y| = s such that |TT(Y)| ? r. We give a unified proof for results of Bollobàs, Bondy, and Sauer concerning this arrow function, and we prove a conjecture of Bondy and Lovász saying (?n24? + n + 2,n)→ (3,7), which generalizes Turán's theorem on the maximum number of edges in a graph not containing a triangle.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号