Optimal size of (1,r)-cover-free families
Problem 5.1 (cover-free families) · arXiv:2404.03472
Status open high confidence
Problem 5.1 from arXiv:2404.03472 asks whether $(1,r)$-cover-free families achieving $t\in\mathcal{O}(r^2\log|\mathcal{F}|/\log r)$ exist, which would close the longstanding gap $\Omega(r^2\log n/\log r)\leq t(n,1,r)\leq\mathcal{O}(r^2\log n)$ that has been open since the 1990s. A related ITCS 2025 follow-up paper on graph reconstruction via MIS queries addresses the algorithmic bounds from the same source paper but does not resolve this combinatorial problem about cover-free families. No post-2024 paper closing the $(\log r)$-factor gap for $(1,r)$-cover-free families was found in the indexed literature.
Reviewer notes. The gap between the lower bound Omega(r^2 log n / log r) and upper bound O(r^2 log n) for t(n,1,r) has been known since the 1990s (cf. Electronic Journal of Combinatorics v23i2p45 for a survey of lower bounds). The ITCS 2025 paper 'Graph Reconstruction via MIS Queries' (LIPIcs ITCS 2025, doi:10.4230/LIPIcs.ITCS.2025.66) is a direct algorithmic follow-up to the source paper but does not address Problem 5.1. No construction achieving the conjectured O(r^2 log n / log r) bound was found.
Context
The paper's lower bound for deterministic non-adaptive reconstruction ($\Omega(\Delta^{3}\log n/\log\Delta)$) is tied to a longstanding gap for cover-free families: $\Omega(r^{w+1}\log n/\log r)\leq t(n,w,r)\leq\mathcal{O}(r^{w+1}\log n)$. Closing this gap for $(1,r)$-cover-free families would directly improve the graph-reconstruction bounds.
Notes. Parser assigned the label 'Problem 5.0' to all three problems in Section 5; this is likely Problem 5.1 or the first of several unnumbered problems.
Source paper
Lower bounds for graph reconstruction with maximal independent set queries
Lukas Michel, Alex Scott · 2024-04-04
https://arxiv.org/abs/2404.03472