×

On splitting and splittable families. (English) Zbl 1490.05261

Summary: 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,\dots,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,\dots,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 \(\leq 4\)-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.

MSC:

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

References:

[1] N. Alon, E.xi E. Bergmann, D. Coppersmith and A. M. Odlyzko, Balancing sets of vectors,IEEE Trans. Inform. Theory34 (1) (1988), 128-130. · Zbl 0647.94018
[2] J. Beck,Combinatorial games, vol. 114 ofEncyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 2011; Tic-tac-toe theory, Paperback edition of the 2008 original. · Zbl 1351.91002
[3] P. Bernstein, C. Bortner, S. Coskey, S. Li and C. Simpson, The set splittability problem,Australas. J. Combin.75 (2019), 190-209. · Zbl 1429.05015
[4] M. Charikar, A. Newman and A. Nikolov, Tight hardness results for minimizing discrepancy, InProc. Twenty-Second Annual ACM-SIAM Symp. on Discrete Algorithms, pp. 1607-1614; SIAM, Philadelphia, PA, 2011. · Zbl 1373.68236
[5] B. Chazelle,The discrepancy method, Cambridge University Press, Cambridge, 2000; Randomness and complexity. · Zbl 0960.65149
[6] D. Condon, S. Coskey, L. Serafin and C. Stockdale, On generalizations of separating and splitting families,Electron. J. Combin.23 (3) (2016), #P3.36, 19 pp. · Zbl 1344.05143
[7] D. Deng, D. R. Stinson, P. C. Li, G. H. J. van Rees and R. Wei, Constructions and bounds for (m, t)-splitting systems,Discrete Math.307 (1) (2007), 18-37. · Zbl 1129.05052
[8] H. Enomoto, P. Frankl, N. Ito and K. Nomura, Codes with given distances, Graphs Combin.3 (1) (1987), 25-38. · Zbl 0629.94014
[9] J. D. Farmer and S. C. Leth, An asymptotic formula for powers of binomial coefficients,Math. Gazette89 (516) (2005), 385-391.
[10] W. Feller,An introduction to probability theory and its applications, Vol. I, Third ed., John Wiley & Sons, Inc., New York-London-Sydney, 1968. · Zbl 0155.23101
[11] B. Frederickson,Splitting families code, 2018,https://bitbucket.org/ brycefred/maximal-splitting-families/src/master/.
[12] X. Li and H. Shen,Constructions and bounds for splitting and separating systems,Ars Combin.123 (2015), 381-406. · Zbl 1374.05049
[13] Ai. C. H. Ling, P. C. Li and G. H. J. van Rees, Splitting systems and separating systems,Discrete Math.279 (1-3) (2004), 355-368. In honour of Zhu Lie. · Zbl 1195.05009
[14] D. R. Stinson,Some baby-step giant-step algorithms for the low Hamming weight discrete logarithm problem,Math. Comp.71 (237) (2002), 379-391 (electronic). · Zbl 0977.68040
[15] H.-T. Yan,Splittable families code, 2018,https://drive.google.com/ drive/folders/1-greIn1J6KMUz4S4PnoF0d0L2PbgSjFd?usp=sharing.
[16] C. Yost-Wolff, Personal communication, 2018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.