Cover-free families on graphs

@misc{parida2026coverfree,
  title = {{Cover-free families on graphs}},
  author = {Prangya Parida and Lucia Moura},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2605.12634},
  eprint = {2605.12634},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.12634},
}

TY  - UNPB
TI  - Cover-free families on graphs
AU  - Prangya Parida
AU  - Lucia Moura
PY  - 2026
DA  - 2026/09/24
PB  - arXiv
DO  - 10.48550/arxiv.2605.12634
UR  - https://arxiv.org/abs/2605.12634
AB  - A family of subsets of a t-set is a \emph{d-cover-free family} or d-CFF if no subset in the family is contained in the union of any d other subsets. Let $t(d, n)$ denote the minimum t for which there exists a d-CFF on a t-set with n subsets. Since a $1$-CFF is the same as a Sperner family, using Sperner's theorem, we get t(1, n) ∼ log_2(n) as n grows. Erdös, Frankl, and Füredi (JCTA, 1982) proved that 3.106log_2(n) < t(2,n) < 5.512log_2(n). This paper focuses on generalizing $1$-CFF and $2$-CFF using a graph G where vertices correspond to subsets in the set system. A G-Sperner$(t, n)$ is a family of subsets of a t-set such that each edge of G specifies a pair of subsets not contained in each other, where as a G-CFF$(t, n)$ is a family of subsets of a t-set such that it is G-Sperner and the union of a pair of subsets corresponding to each edge of G does not contain any other subset in the family. Let t_s(G) and t(G) denote the minimum t for which there exist a G-Sperner$(t, n)$ and a G-CFF$(t, n)$, respectively. In this way, t_s(K_n) = t(1, n) and t(K_n) = t(2, n). Firstly, we prove t_s(G) = t(1, χ(G)) for any simple graph G and provide various upper and lower bounds for t(G). The \emph{trivial bound}, t(1, n) ≤ t(G) ≤ t(2, n) holds for any simple graph G with no isolated vertex, with the lower bound tight for an infinite family of star graphs and the upper bound tight for complete graphs. We study when these bounds can be improved and give better constructive upper bounds for families of graphs such as stars, paths, cycles, wheels, and windmill graphs. In particular, a construction based on mixed-radix Gray codes yields log_2(n) ≤ t(P_n) ≤ t(C_n) ≤ 1.893log_2(n) + 𝒪(1) where P_n and C_n are paths and cycles with n vertices.
ER  -