2026-07-21T23:18:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21028 2024-09-16T06:02:38Z ddc:004 open_access

Testing Intersectingness of Uniform Families Haviv, Ishay Parnas, Michal Intersecting family Uniform family Property testing 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 ⊆ binom([n],k) of k-subsets of [n] is ε-far from intersecting if one has to remove more than ε ⋅ binom(n,k) of the sets of F to make it intersecting. We study the property testing problem that given query access to a uniform family F ⊆ binom([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)^r) and a non-adaptive one-sided error tester with query complexity O((ln k)/ε) for ε ≥ Ω((k²/n)^r). 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 behaves differently from that of testing intersectingness of non-uniform families, studied recently by Chen, De, Li, Nadimpalli, and Servedio (ITCS, 2024). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ishay Haviv and Michal Parnas 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.35 urn:nbn:de:0030-drops-210288 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.35 eng https://creativecommons.org/licenses/by/4.0/legalcode