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

DOI10.1016/0012-365X(85)90128-1MaRDI QIDQ1065799zbMATH OpenOpenAlexFDO

Authors Richard A. Dean

Publication date 1985

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(85)90128-1

zbMATH Keywords

set intersection

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Review text

It is known that the largest collection of k-element sets with the property that no one contains the intersection of two others, has, for large k, size \(c^ k\) with \((1+\sqrt{2})/2<C<27/16\), but no explicit construction is known for collections near this size for large k. This paper contains description of a simple construction that produces a collection whose size is on the order of \(2^{\sqrt{2k}}\) (actually it can be improved slightly to roughly \(2^{2\sqrt{k}}).\) The construction is based on the idea that given such a collection of size m for a given set size k, one can construct one of size 2m and set size \(k+u\) whenever the binomial coefficient C(2u,u)\(\geq 2m\), by adding to each of the m original k-sets a unique u-element subset of 2u new elements, and also adding the complement of this set in the 2u elements to it.

Recommendations

• Explicit construction of exponential sized families of k-independent sets
• scientific article; zbMATH DE number 15500
• Around the complete intersection theorem
• The maximum size of intersecting and union families of sets
• A general 2-part Erdős-Ko-Rado theorem

Cites work

• Intersections of k-element sets

Cited in

(2)

• Explicit construction of exponential sized families of k-independent sets
• EKR sets for large \(n\) and \(r\)

This page was built for publication: A construction for large families of k-element sets having the Erdős intersection property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1065799)