Speakers: Prangya Parida, U. Ottawa, and Kiara McDonald, U. Victoria
—————————————————
Prangya Parida:
Title: Cover-free families on graphs
Abstract: A family of subsets of a t-set is called a d-cover-free family if no subset is contained in the union of any d other subsets. We denote by t(d, n) the minimum t for which there exists a d-cover-free family of a t-set with n subsets. Cover-free families (CFF) have wide applications in combinatorial group testing, where a d-CFF(t, n) can be used to identify d defective items in a group of n items with t tests. It is well-known that t(1, n) can be obtained by applying the famous Sperner’s Theorem. For d \geq 2, we rely on bounds for t(d, n). Erdös, Frankl, and Füredi provided bounds for t(2, n) using the probabilistic method, given by 3.106 \log(n) < t(2, n) < 5.512 \log(n). Using a derandomization technique, Porat and Rothschild presented a deterministic polynomial-time algorithm to construct d-CFFs that achieves t = O(d^2 \log(n)). Some upper bounds on t(2, n) (in some cases exact bounds) for small values of n are provided by Li, van Rees, and Wei in 2006.
In this talk, we extend the definition of a cover-free family to include a graph G, which we denote as \overline{G}-CFF, where the edges of the graph specify the pair of subsets whose union must not cover any other subset. We denote by t(G) the minimum t for which there exists a \overline{G}-CFF. The traditional 2-CFF(t, n) is a special case of \overline{G}-CFF when G is a complete graph of n vertices. This generalization of cover-free families provides a richer combinatorial structure that lies between being a 1-CFF and a 2-CFF.
We will discuss some classical results on cover-free families, along with general constructions of \overline{G}-CFFs, as well as specific constructions for certain families of graphs. We prove that for a graph G with n vertices, t(1, n) \leq t(G) \leq t(2, n) and show that for an infinite family of Star graphs S_n with n vertices, t(S_n) = t(1, n). Interestingly, we also give a construction of CFFs on a Path (P_n) or Cycle (C_n) with n vertices using a mixed-radix Gray code. This yields an upper bound for t(P_n) and t(C_n) that is smaller than the lower bound of t(2, n) mentioned above.
This is joint work with Lucia Moura.
——————————————————
Kiara McDonald:
Title: Broadcast Independence in Trees
Abstract: In the area of Graph Theory, the well-known problems of domination, packing and independence are generalized by broadcast domination, broadcast packing and broadcast independence. As an analogy and application, consider a city, where one wants to place cell towers of different signal strengths subject to certain conditions. If every building in the city hears the signal from at least (respectively at most) one tower, then the broadcast is dominating (respectively packing). If no tower hears the signal from another tower, the broadcast is independent. The sum of the tower signal strengths is called the cost of the broadcast. The total cost of a maximum independent broadcast is called the broadcast independence number.
Our research was focused on determining explicit formulas and polynomial time algorithms for the broadcast independence number of various types of graphs. This parameter is difficult to compute for graphs in general, so we restrict the problem to specific classes of graphs to make use of their special structural properties to solve the problem. For a graph from a given class, we constructed a new graph, called the broadcast ball intersection graph. We were able to show that if the broadcast ball intersection graph is weakly chordal, then broadcast independence is polynomial time solvable for the given class of graphs. In this talk, we will focus on the broadcast ball intersection graph of trees. This talk is based on joint work with Richard Brewster (TRU) and Jing Huang (UVic).
