String quartets in binary (Q2709843)

Let \(M(n,A)\) be the maximum possible cardinality of a family of binary strings of length \(n\) such that for every four distinct members of the family there is a coordinate in which exactly two of them have a 1. Similarly, let \(M(n,C)\) denote the analogous number where ``two'' is replaced by ``one''. Explicit exponential upper and lower bounds are given for \(M(n,A)\) and \(M(n,C)\). While the lower bounds are derived by probabilistic arguments, the upper bounds rely on a lemma due to Sauer, Shelah-Perles, and Vapnik-Chervonenkis, respectively on the bounding technique based on subadditivity of graph entropy due to the second author.