On hypergraphs without two edges intersecting in a given number of vertices |
| |
Authors: | P Frankl Z Füredi |
| |
Institution: | CNRS Paris, France;Mathematical Institute of the Academy, Budapest, Hungary |
| |
Abstract: | Let X be a finite set of n-melements and suppose t ? 0 is an integer. In 1975, P. Erdös asked for the determination of the maximum number of sets in a family = {F1,…, Fm}, Fi ? X, such that ∥Fi ∩ Fj∥ ≠ t for 1 ? i ≠ j ? m. This problem is solved for n ? n0(t). Let us mention that the case t = 0 is trivial, the answer being 2n ? 1. For t = 1 the problem was solved in 3]. For the proof a result of independent interest (Theorem 1.5) is used, which exhibits connections between linear algebra and extremal set theory. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|