𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Intersection Statements for Systems of Sets

✍ Scribed by W.A Deuber; P Erdős; D.S Gunderson; A.V Kostochka; A.G Meyer

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
320 KB
Volume
79
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

✦ Synopsis

A family of r sets is called a 2-system if any two sets have the same intersection. Denote by F(n, r) the most number of subsets of an n-element set which do not contain a 2-system consisting of r sets. Constructive new lower bounds for F(n, r) are given which improve known probabilistic results, and a new upper bound is given by employing an argument due to Erdo s and Szemere di. Another construction is given which shows that for certain n, F(n, 3) 1.551 n&2 . We also show a relationship between the upper bound for F(n, 3) and the Erdo s Rado conjecture on the largest uniform family of sets not containing a 2-system.

1997 Academic Press

1. Introduction

A family F of sets is called k-uniform if for every F # F, |F| =k holds. A family of sets is called a 2-system if any two sets have the same intersection.

📜 SIMILAR VOLUMES

An intersection theorem for systems of s
An intersection theorem for systems of sets
✍ A. V. Kostochka 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 346 KB 👁 2 views

Erdos and Rado defined a A-system, as a family in which every two members have the same intersection. Here we obtain a new upper bound on the maximum cardinality q ( n , q ) of an n-uniform family not containing any A-system of cardinality q. Namely, we prove that, for any a > 1 and q , there exists

Set Systems with Restricted Intersection
Set Systems with Restricted Intersections modulo Prime Powers
✍ László Babai; Péter Frankl; Samuel Kutin; Daniel Štefankovič 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 236 KB

We study set systems satisfying Frankl Wilson-type conditions modulo prime powers. We prove that the size of such set systems is polynomially bounded, in contrast with V. Grolmusz's recent result that for non-prime-power moduli, no polynomial bound exists. More precisely we prove the following resul

Intersecting Balanced Families of Sets
Intersecting Balanced Families of Sets
✍ Adam Idzik; Gyula O.H. Katona; Rajiv Vohra 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 117 KB

Suppose that any t members (t 2) of a regular family on an n element set have at least k common elements. It is proved that the largest member of the family has at least k 1Ât n 1&1Ât elements. The same holds for balanced families, which is a generalization of the regularity. The estimate is asympto

Set intersection representations for alm
Set intersection representations for almost all graphs
✍ Eaton, Nancy; Grable, David A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 581 KB

Two variations of set intersection representation are investigated and upper and lower bounds on the minimum number of labels with which a graph may be represented are found that hold for almost all graphs. Specifically, if &(G) is defined to be the minimum number of labels with which G may be repre

On set intersection representations of g
On set intersection representations of graphs
✍ Stasys Jukna 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 193 KB 👁 1 views

## Abstract The intersection dimension of a bipartite graph with respect to a type __L__ is the smallest number __t__ for which it is possible to assign sets __A__~__x__~⊆{1, …, __t__} of labels to vertices __x__ so that any two vertices __x__ and __y__ from different parts are adjacent if and only