๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Families of k-independent sets

โœ Scribed by Daniel J. Kleitman; Joel Spencer

Publisher
Elsevier Science
Year
1973
Tongue
English
Weight
618 KB
Volume
6
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Explicit construction of exponential siz
Explicit construction of exponential sized families of k-independent sets
โœ N Alon ๐Ÿ“‚ Article ๐Ÿ“… 1986 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 184 KB

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 proble

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.

Linearly independent set families
Linearly independent set families
โœ Friedhelm Eicker; Guenter Ewald ๐Ÿ“‚ Article ๐Ÿ“… 2004 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 253 KB
The independent sets of rank k of a matr
The independent sets of rank k of a matroid
โœ G. Purdy ๐Ÿ“‚ Article ๐Ÿ“… 1982 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 466 KB

We determine the minimum num>er of independent sets of arbitrary fixed rank contained in a matroid M as M varies over all simple (respectively loopless) matroids of fixed rank and cardinality.