Talk information

Date: Sunday, July 28, 2024
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Omri Marcus (Bar Ilan University)
Title: Intersection problems with a symmetry condition

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 (in this case, without success).

We are interested in a variant of the above problem proposed by T. Brown and answered by M. L. Livingston in 1997: A family F of elements of $[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 contains $1/k$ of all elements. In 2019, Eberhard et al. showed that for symmetric families a much smaller bound of $exp(-c \log n / k)$ can be achieved. Inspired by their work, we present a sharper bound of $exp(-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.