Testing Intersectingness of Uniform Families

A set family F is called intersecting if every two members of F intersect, and it is called uniform if all members of F share a common size. A uniform family F ⊆ [n]k of k-subsets of $[n]$ is ε-far from intersecting if one has to remove more than ε · nk of the sets of F to make it intersecting. We study the property testing problem that given query access to a uniform family F ⊆ [n]k, asks to distinguish between the case that F is intersecting and the case that it is ε-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(ln n/ε) for ε ≥ Ω( (k/n)ʳ) and a non-adaptive one-sided error tester with query complexity O(ln k/ε) for ε ≥ Ω( (k²/n)ʳ). The query complexities are optimal up to the logarithmic terms. For ε ≥ Ω( (k²/n)²), we further provide a non-adaptive one-sided error tester with optimal query complexity of O(1/ε). Our findings show that the query complexity of the problem differs substantially from that of testing intersectingness of non-uniform families, studied recently by Chen, De, Li, Nadimpalli, and Servedio (ITCS, 2024).