On splitting and splittable families

MaRDI QIDQ5080923zbMATH OpenFDO

Authors Samuel Coskey, Bryce Frederickson, Samuel Mathers, Hao-Tong Yan

Publication date 31 May 2022

Full work available at URL https://arxiv.org/abs/1811.12896, http://ajc.maths.uq.edu.au/pdf/82/ajc_v82_p268.pdf

zbMATH Keywords

splitting familysplitting gamesplittable families

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Extremal set theory (05D05)

Abstract: A set $A$ is said to split a finite set $B$ if exactly half the elements of $B$ (up to rounding) are contained in $A$. We study the dual notions: (1) splitting family, which is a collection of sets such that any subset of $1,ldots,k$ is split by a set in the family, and (2) splittable family, which is a collection of sets such that there is a single set $A$ that splits each set in the family. We study the minimum size of a splitting family on $1,ldots,k$, as well as the structure of splitting families of minimum size. We use a mixture of computational and theoretical techniques. We additionally study the related notions of $mathordleq4$-splitting families and $4$-splitting families, and we provide lower bounds on the minimum size of such families. Next we investigate splittable families that are just on the edge of unsplittability in several senses. First, we study splittable families that have the fewest number of splitters. We give a complete characterization in the case of two sets, and computational results in the case of three sets. Second, we define a splitting game, and study splittable families for which a splitter cannot be found under adversarial conditions.

Recommendations

• On generalizations of separating and splitting families
• The set splittability problem
• Splittings
• Analytic countably splitting families
• Splitting number

Cites work

• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• Balancing sets of vectors
• Codes with given distances
• Combinatorial Games
• Constructions and bounds for \((m,t)\)-splitting systems
• Constructions and bounds for splitting and separating systems.
• On generalizations of separating and splitting families
• Some baby-step giant-step algorithms for the low Hamming weight discrete logarithm problem
• Splitting systems and separating systems.
• The set splittability problem
• Tight hardness results for minimizing discrepancy

Cited in

(6)

• Bisecting and \(D\)-secting families for set systems
• The set splittability problem
• On generalizations of separating and splitting families
• Principles of Distributed Systems
• Analytic countably splitting families
• On separating families of bipartitions

This page was built for publication: On splitting and splittable families

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