{"id":"arxiv/2605.12634","url":"https://arxiv.org/abs/2605.12634","tags":["math.CO"],"score":0,"title":"Cover-free families on graphs","domain":"math.CO","source":"arxiv","authors":["Prangya Parida","Lucia Moura"],"reviews":0,"subject":"math.CO","summary":"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) \\sim \\log_{2}(n)$ as $n$ grows. Erdös, Frankl, and Füredi (JCTA, 1982) proved that $3.106\\log_{2}(n) < t(2,n) < 5.512\\log_{2}(n)$. This paper focuses on generalizing $1$-CFF and $2$-CFF using a graph $G$ where vertices correspond to subsets in the…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-12","reactions":{}}