Abstract:
A set-intersecting family is a family of subsets of [n] = {1, ..., n}, such that each pair of sets in the family has a non-empty intersection. It is clear that an intersecting family cannot include more than 1/2 of all the subsets of [n]. Natural tightness examples are the dictatorship families - the families of all sets that contain a fixed element. One may try to add a condition of symmetry in order to eliminate these degenerate examples and to achieve a smaller bound, but without success: the family {S \subseteq [n] | |S| > n/2} is set-intersecting, symmetric in any reasonable sense, and yet contains half of all the subsets of [n] when n is odd.
We are interested in a variant of the above problem proposed by T. Brown and answered by M. L. Livingston in 1997: A family of vectors F \subset [k]^n is intersecting if for every x, y in F, there exists a coordinate i in [n] such that x_i = y_i. What are the largest intersecting families of vectors? Livingston proved that for k > 2, any largest such family is of the form {x in [k]^n | x_i = b} for some i in [n] and b in [k], and thus, it contains 1/k of all elements.
In 2019, Eberhard et al. showed that for symmetric families a much smaller bound of e^{-c log n / k} can be achieved. Inspired by their work, we present a sharper bound of e^{-c k / log n} for all 2 log n < k < sqrt{n} \log n (namely, an improvement of a factor of (k / log n)^2 in the exponent).
While our results are combinatorial, the tools are analytic. We reduce the problem into the field of Analysis of Boolean Functions, and use methods from this field, such as the noise operator and its spectral decomposition, and globalness properties of Boolean functions.
Joint work with Nathan Keller and Noam Lifshitz.
