Testing Intersecting and Union-Closed Families

Inspired by the classic problem of Boolean function monotonicity testing, we investigate the testability of other well-studied properties of combinatorial finite set systems, specifically \emph{intersecting} families and \emph{union-closed} families. A function $f: \{0,1\}^n \to \{0,1\}$ is intersecting (respectively, union-closed) if its set of satisfying assignments corresponds to an intersecting family (respectively, a union-closed family) of subsets of $[n]$. Our main results are that -- in sharp contrast with the property of being a monotone set system -- the property of being an intersecting set system, and the property of being a union-closed set system, both turn out to be information-theoretically difficult to test. We show that: $\bullet$ For $ε\geq Ω(1/\sqrt{n})$, any non-adaptive two-sided $ε$-tester for intersectingness must make $2^{Ω(n^{1/4}/\sqrtε)}$ queries. We also give a $2^{Ω(\sqrt{n \log(1/ε)})}$-query lower bound for non-adaptive one-sided $ε$-testers for intersectingness. $\bullet$ For $ε\geq 1/2^{Ω(n^{0.49})}$, any non-adaptive two-sided $ε$-tester for union-closedness must make $n^{Ω(\log(1/ε))}$ queries. Thus, neither intersectingness nor union-closedness shares the $\mathrm{poly}(n,1/ε)$-query non-adaptive testability that is enjoyed by monotonicity. To complement our lower bounds, we also give a simple $\mathrm{poly}(n^{\sqrt{n\log(1/ε)}},1/ε)$-query, one-sided, non-adaptive algorithm for $ε$-testing each of these properties (intersectingness and union-closedness). We thus achieve nearly tight upper and lower bounds for two-sided testing of intersectingness when $ε= Θ(1/\sqrt{n})$, and for one-sided testing of intersectingness when $ε=Θ(1).$