Monday, October 27, 2025 11:30 am
-
12:30 pm
EDT (GMT -04:00)
itle: Cover-free Families on Graphs
| Speaker: | Prangya Parida |
| Affiliation: |
University of Ottawa |
| Location: | Please contact Sabrina Lato for Zoom link. |
Abstract: A family of subsets of a t-set is a 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 of a t-set with n subsets. t(1, n) is determined using Sperner’s theorem. For d ≥ 2, we rely on bounds for t(d, n). Erdős, Frankl, and Füredi proved 3.106 log(n) < t(2, n) < 5.512 log(n).
A 2-CFF can be generalized by using a graph G with vertices corresponding to subsets in the set system. A G-CFF is a set system such that each edge of G specifies a pair of subsets not contained in each other and whose union must not contain any other subset. Let t(G) denote the minimum t for which there exists a G-CFF. Thus, t(K_n) = t(2, n).
In this talk, we discuss some classic results on cover-free families, along with general constructions of G-CFFs and specific constructions for certain families of graphs. We show that for a graph G with n vertices (no isolated vertices), t(1, n) ≤ t(G) ≤ t(2, n), and that for an infinite family of star graphs S_n with n vertices, t(S_n) = t(1, n). Interestingly, we show how we can use a mixed-radix Gray code to construct CFFs on paths (P_n) and cycles (C_n) with n vertices. This leads to the bound log(n) ≤ t(G) ≤ 1.89 log(n), where G is either P_n or C_n.
This is joint work with Lucia Moura.