On the trace of finite sets |
| |
Authors: | Peter Frankl |
| |
Affiliation: | CNRS, Paris, France and TATA Institute, Bombay, India |
| |
Abstract: | For a family of subsets of an n-set X we define the trace of it on a subset Y of X by T(Y) = {F∩Y:F?}. We say that (m,n) → (r,s) if for every with | we can find a Y?X|Y| = s such that |T(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 , which generalizes Turán's theorem on the maximum number of edges in a graph not containing a triangle. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|