On splitting and splittable families

zbMATH Open1490.05261arXiv1811.12896MaRDI QIDQ5080923FDOQ5080923

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

Publication date: 31 May 2022

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.

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

Recommendations

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

zbMATH Keywords

splitting familysplitting gamesplittable families

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Splitting systems and separating systems.
• Some baby-step giant-step algorithms for the low Hamming weight discrete logarithm problem
• On generalizations of separating and splitting families
• Constructions and bounds for \((m,t)\)-splitting systems
• Combinatorial Games
• Title not available (Why is that?)
• Tight hardness results for minimizing discrepancy
• Codes with given distances
• Balancing sets of vectors
• The set splittability problem
• Constructions and bounds for splitting and separating systems.

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)