Explicit construction of exponential sized families of k-independent sets

DOI10.1016/0012-365X(86)90161-5zbMath0588.05003MaRDI QIDQ1073031

Noga Alon

Publication date: 1986

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

collection of subsets

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial codes (94B25)

Related Items

On the upper bound of the size of the \(r\)-cover-free families ⋮ Perfect Hash Families: Constructions and Existence ⋮ Deterministic constructions of high-dimensional sets with small dispersion ⋮ Generalised cumulative arrays in secret sharing ⋮ Roux-type constructions for covering arrays of strengths three and four ⋮ Secret sharing schemes with partial broadcast channels ⋮ On the maximum number of qualitative independent partitions ⋮ Linear Time Constructions of Some $$d$$-Restriction Problems ⋮ Strengthening hash families and compressive sensing ⋮ A hierarchical framework for recovery in compressive sensing ⋮ Explicit constructions of centrally symmetric \(k\)-neighborly polytopes and large strictly antipodal sets ⋮ Unnamed Item ⋮ Applications of coding theory to communication combinatorial problems ⋮ Strong qualitative independence. ⋮ A polynomial algorithm for constructing families of k-independent sets ⋮ Coloring chains for compression with uncertain priors ⋮ Rényi 100, quantitative and qualitative (in)dependence ⋮ Orientations making \(k\)-cycles cyclic ⋮ \(t\)-CIS codes over \(\mathrm{GF}(p)\) and orthogonal arrays ⋮ A Graham-Sloane type construction for \(s\)-surjective matrices ⋮ Application of coding theory to interconnection networks ⋮ Some baby-step giant-step algorithms for the low hamming weight discrete logarithm problem ⋮ Explicit constructions of perfect hash families from algebraic curves over finite fields ⋮ New constructions for IPP codes ⋮ On the contact dimensions of graphs ⋮ Separable collusion-secure multimedia codes ⋮ Explicit constructions for perfect hash families ⋮ On the capacity of Boolean graph formulæ ⋮ Arrays for combinatorial interaction testing: a review on constructive approaches ⋮ Optimal linear perfect hash families ⋮ Tropical Complexity, Sidon Sets, and Dynamic Programming ⋮ Improving two recursive constructions for covering arrays ⋮ RESILIENT LKH: SECURE MULTICAST KEY DISTRIBUTION SCHEMES ⋮ Perfect hash families: Probabilistic methods and explicit constructions

Cites Work

• On qualitatively independent partitions and related problems
• Families of finite sets in which no set is covered by the union of \(r\) others
• Families of finite sets in which no set is covered by the union of two others
• Intersections of k-element sets
• Families of \(k\)-independent sets