Testing Intersectingness of Uniform Families

A set family $$\mathcal {F}$$ is called intersecting if every two members of $$\mathcal {F}$$ intersect, and it is called uniform if all members of $$\mathcal {F}$$ share a common size. A uniform family $$\mathcal {F}\subseteq \left( {\begin{array}{c}[n]\\ k\end{array}}\right)$$ of k-subsets of [n] is $$\varepsilon$$ -far from intersecting if one has to remove more than $$\varepsilon \cdot \left( {\begin{array}{c}n\\ k\end{array}}\right)$$ of the sets of $$\mathcal {F}$$ to make it intersecting. We study the property testing problem that given query access to a uniform family $$\mathcal {F}\subseteq \left( {\begin{array}{c}[n]\\ k\end{array}}\right)$$ , asks to distinguish between the case that $$\mathcal {F}$$ is intersecting and the case that it is $$\varepsilon$$ -far from intersecting. We prove that for every fixed integer r, the problem admits a non-adaptive two-sided error tester with query complexity $$O(\frac{\ln n}{\varepsilon })$$ for $$\varepsilon \ge \Omega ( (\frac{k}{n})^r)$$ and a non-adaptive one-sided error tester with query complexity $$O(\frac{\ln k}{\varepsilon })$$ for $$\varepsilon \ge \Omega ( (\frac{k^2}{n})^r)$$ . The query complexities are optimal up to the logarithmic terms. For $$\varepsilon \ge \Omega ( (\frac{k^2}{n})^2)$$ , we further provide a non-adaptive one-sided error tester with optimal query complexity of $$O(\frac{1}{\varepsilon })$$ . Our findings show that the query complexity of the problem behaves differently from that of testing intersectingness of non-uniform families, studied recently by Chen et al. (2024).