Cover-free Families on Graphs and Hypergraphs

Abstract

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\H{o}s, Frankl, and Füredi (JCTA 1982) proved that $3.106\log_{2}(n) < t(2,n) < 5.512\log_{2}(n)$. This thesis focuses on generalizing $d$-CFF using a graph and hypergraph where vertices correspond to subsets in the set system. The main contributions of this thesis are in three main topics. First, we focus on generalizing $1$-CFF and $2$-CFF using a graph $G = ([1, n], E)$ where a subset in the family corresponds to a vertex of $G$. 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 that must not be contained in each other, while a $G$-CFF$(t, n)$ is a family of subsets of a $t$-set such that it is $G$-Sperner and the union of each pair of subsets corresponding to an 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, \chi(G))$ for any simple graph $G$ with no isolated vertices, and provide various upper and lower bounds for $t(G)$. The \emph{trivial bound}, $t(1, n) \leq t(G) \leq 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) \leq t(P_n) \leq t(C_n) \leq 1.893\log_{2}(n) + \O(1)$ where $P_n$ and $C_n$ are paths and cycles with $n$ vertices. Second, we study a generalization of $d$-CFF for $d \geq 2$ using a hypergraph $H$ of rank $d$ and $n$ vertices. An $H$-CFF$(t, n)$ is a family of $n$ subsets of a $t$-set such that the union of the subsets corresponding to the vertices in a subset of a hyperedge does not contain any other subset in the family. Let $t(H)$ denote the minimum $t$ for which there exists an $H$-CFF$(t, n)$. In this way, $t(H) = t(d, n)$ if $H$ is a complete $d$-uniform hypergraph on $n$ vertices, but can be much smaller for hypergraphs in general. We study the connection between $H$-CFFs and other generalized set systems used in group testing, such as $H$-separable set systems, investigate their characterizations through directed hypergraph homomorphisms, and explore bounds on $t(H)$ using tools from hypergraph theory. Furthermore, we study CFFs on graph and hypergraph products. We provide an upper bound for CFFs on the Cartesian product of (hyper)graphs and investigate families of graphs that attain the upper bound, as well as families for which the upper bound is close to the trivial lower bound. Moreover, we generalize some well-known constructions of $d$-CFFs through the lens of CFFs on the strong product of (hyper)graphs. Finally, we focus on the classical mixed-radix \emph{reflected} and \emph{modular} Gray codes by providing their recursive constructions, which are necessary for proving a result concerning cover-free families on paths and cycles. Their respective loopless algorithms can be found as Algorithm H and Exercise 77 in Section 7.2.1.1 of The Art of Computer Programming Vol. 4A by Knuth. Furthermore, we study their generation through the lens of their change sequences. We observe that both of these Gray codes, built on a mixed-radix base, are guided by the same change sequence, called the \emph{ruler sequence}. We show how the generation of the reflected and modular Gray codes can be fully parallelized, generating each new codeword in constant time. We also show that modular Gray codes can be generated using a greedy cyclic increment approach. Furthermore, we present a new family of modular Gray codes starting from any tuple $w$ that can be constructed using the same greedy cyclic increment approach to generate the next word that is lexicographically greater than or equal to $w$. We show that although this order is not a suffix of the original modular Gray code, its change sequence is a suffix of the latter.