𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Intersecting Balanced Families of Sets

✍ Scribed by Adam Idzik; Gyula O.H. Katona; Rajiv Vohra

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
117 KB
Volume
93
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

✦ Synopsis

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 asymptotically sharp.

πŸ“œ SIMILAR VOLUMES

Voting Fairly: Transitive Maximal Inters
Voting Fairly: Transitive Maximal Intersecting Families of Sets
✍ Daniel E. Loeb; Andrew R. Conway πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 431 KB

There are several applications of maximal intersecting families (MIFs) and different notions of fairness. We survey known results regarding the enumeration of MIFs, and we conclude the enumeration of the 207,650,662,008 maximal families of intersecting subsets of X whose group of symmetries is trans

Maximal s-Wise t-Intersecting Families o
Maximal s-Wise t-Intersecting Families of Sets: Kernels, Generating Sets, and Enumeration
✍ Lucia Moura πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 239 KB

For fixed s, n, k, and t, let I s (n, k, t) denote the set of all such families. A family A # I s (n, k, t) is said to be maximal if it is not properly contained in any other family in I s (n, k, t). We show that for fixed s, k, t, there is an integer n 0 =n 0 (k, s, t), for which the maximal famili

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

Intersection Statements for Systems of S
Intersection Statements for Systems of Sets
✍ W.A Deuber; P ErdΕ‘s; D.S Gunderson; A.V Kostochka; A.G Meyer πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 320 KB

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, an