Constructions of Cover-free families on Paths and Cycles using a mixed-radix Gray code

Prangya Parida (University of Ottawa)

A family of subsets of a \(t\)-set is called a \emph{\(d\)-cover-free family} (\(d\)-CFF) if no subset in the family is contained in the union of any \(d\) other subsets. A \(2\)-CFF can be generalized by introducing a graph \(G\), where the vertices correspond to subsets in the family. A \emph{cover-free family on a graph \(G\)} is a set system such that, for each edge in \(G\), the corresponding pair of subsets are not contained in one another, and their union does not contain any other subset in the system. We denote by \(t(G)\) the minimum integer \(t\) for which such a family exists.

On the other hand, a \emph{binary Gray code} of length \(n\) is an ordered sequence of binary \(n\)-tuples in which successive codewords differ in exactly one digit. A \emph{mixed-radix Gray code} generalizes this concept by allowing each coordinate to take values from a different base, with successive entries differing in only one digit. Donald Knuth discusses \emph{reflected} and \emph{modular} mixed-radix Gray codes in The Art of Computer Programming, Volume 4A and presents loopless algorithms for their generation.

In this talk, we present two recursive constructions of mixed-radix modular Gray codes and show that they are the same objects generated by the Greedy Algorithm proposed by Williams. We further show how mixed-radix modular Gray codes can be used to construct CFFs on paths (\(P_n\)) and cycles (\(C_n\)) with \(n\) vertices. This leads to the upper bound in \(\log(n) \leq t(G) \leq 1.89 \log(n)\), where \(G\) is either \(P_n\) or \(C_n\).

This is joint work with Lucia Moura.

 Overview  Program