Generating all subsets of a finite set with disjoint unions

DOI10.1016/J.JCTA.2011.06.003zbMATH Open1232.05223arXiv1010.4877OpenAlexW2149006854MaRDI QIDQ640845FDOQ640845

Authors: David Ellis, Benny Sudakov 

Publication date: 21 October 2011

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: If X is an n-element set, we call a family G of subsets of X a k-generator for X if every subset of X can be expressed as a union of at most k disjoint sets in G. Frein, Leveque and Sebo conjectured that for n > 2k, the smallest k-generators for X are obtained by taking a partition of X into classes of sizes as equal as possible, and taking the union of the power-sets of the classes. We prove this conjecture for all sufficiently large n when k = 2, and for n a sufficiently large multiple of k when k > 2.

Full work available at URL: https://arxiv.org/abs/1010.4877

Recommendations

• Note on generating all subsets of a finite set with disjoint unions
• Generating All Sets With Bounded Unions
• scientific article; zbMATH DE number 822743
• scientific article; zbMATH DE number 559036
• Recursive generation of all \(k\)-element partitions of a finite set
• Publication:4863420
• Generating combinatorial sets with given properties
• Constructing union-free pairs of \(k\)-element subsets
• scientific article; zbMATH DE number 553907
• Generating countable groups by discrete subsets

zbMATH Keywords

generatorextremal set theorydisjoint unions

Mathematics Subject Classification ID

Extremal set theory (05D05)

Cites Work

• Some intersection theorems for ordered sets and graphs
• Title not available (Why is that?)
• Supersaturated graphs and hypergraphs
• Extremal Graphs without Large Forbidden Subgraphs
• The maximum number of disjoint pairs in a family of subsets
• 2-Bases of Quadruples
• Generating All Sets With Bounded Unions
• Testing \(k\)-colorability
• Note on generating all subsets of a finite set with disjoint unions

Cited In (4)

• Quadratic reformulations of nonlinear binary optimization problems
• Generating All Sets With Bounded Unions
• Comparable pairs in families of sets
• Note on generating all subsets of a finite set with disjoint unions

This page was built for publication: Generating all subsets of a finite set with disjoint unions

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