✦ LIBER ✦

Explicit construction of exponential sized families of k-independent sets

✍ Scribed by N Alon

Publisher: Elsevier Science
Year: 1986
Tongue: English
Weight: 184 KB
Volume: 58
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(86)90161-5

No coin nor oath required. For personal study only.

✦ Synopsis

Error correcting codes are used to describe explicit collections Fk of subsets of {1, 2,... n}, with IFkl > 2 ckn (ck > 0), such that for any selections A, B of kl and k 2 of members of Fk with kl + k2 = k, there are elements in all the members of A and not in the members of B. This settles a problem of Kleitman and Spencer and a similar problem of Kleitman, Shearer and Sturtevant.

📜 SIMILAR VOLUMES

A polynomial algorithm for constructing

A polynomial algorithm for constructing families of k-independent sets

✍ G. Freiman; E. Lipkin; L. Levitin 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 1003 KB

The present paper describes an algorithm for constructing families of k-independent subsets & of {1,2, . . . , n} with &I >2ck", where c, = d/(k -1)2& and d is a certain constant. The algorithm has a polynomial complexity with respect to the size of the family constructed.

A construction for large families of k-e

A construction for large families of k-element sets having the Erdös intersection property

✍ Richard Dean 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 77 KB

## Dedicated to E. Corominas Kleitman, Shearer et Sturtevant ont 6tudi6 le probl~me de trouver l'entier maximum m pour lequel il existe une famille de m ensembles A1,..., Am, tous ~ k 616ments, satisfaisant la propri6t6 d'intersection d'Erd6s: A v f3 Aq ¢ AT d~s que p, q, r sont distincts. Nous do