On disjointly representable sets |
| |
Authors: | Peter Frankl János Pach |
| |
Affiliation: | (1) CNRS, 15 Quai Anatole France, 75007 Paris, France;(2) Mathematical Institute of the, Hungarian Academy of Sciences, Pf. 428, H-1395 Budapest, Hungary |
| |
Abstract: | A system of setsE 1,E 2, ...,E k ⊂X is said to be disjointly representable if there existx 1,x 2, ...,x k teX such thatx i teE j ⇔i=j. Letf(r, k) denote the maximal size of anr-uniform set-system containing nok disjointly representable members. In the first section the exact value off(r, 3) is determined and (asymptotically sharp) bounds onf(r, k),k>3 are established. The last two sections contain some generalizations, in particular we prove an analogue of Sauer’ theorem [16] for uniform set-systems. Dedicated to Paul Erdős on his seventieth birthday |
| |
Keywords: | 05 C 35 05 C 65 05 A 05 |
本文献已被 SpringerLink 等数据库收录! |
|