Speaker : 1. Prof. Hui-Lan Chang (National University of Kaohsiung) 2. Dr. Yu-Pei Hunag (I-Shouo University)
Title : 1. Algorithmic Lovasz Local Lemma and its Applications to Group Testing 2. Nonexistence of a Class of Distance-regular Graphs
Time : 2014-05-30 (Fri) 14:00 - 17:00
Place : Seminar Room 617, Institute of Mathematics (NTU Campus)
Abstract: 1. A cover-free family (introduced by Kautz and Singleton (1964)) is a family of subsets of a finite set in which no one is covered by the union of others. We study a variation of cover-free family: A binary matrix is if for any cyclically consecutive columns and another cyclically consecutive columns , there exists one row intersecting but none of . In this talk, I will present how we apply the algorithmic Lovasz Local Lemma to obtain an upper bound of the minimum number of rows in an -consecutive-disjunct matrix of columns. In group testing, our goal is to determine a small subset of positive items in a large population by group tests. In this talk, I will also introduce how we exploit consecutive-disjunct matrices to solve threshold group testing of consecutive positives (introduced by Chang and Tsai (2013)). This is a joint work with Yi-Chang Chiu and Yi-Lin Tsai. 2. Let denote a distance-regular graph with diameter and intersection numbers , and . We show the connection between the -bounded property and the nonexistence of parallelograms of any length up to . Assume further that is with classical parameters , Pan and Weng showed that Under the assumption , we exclude this class of graphs by an application of the above connection. This is a joint work with Yeh-jong Pan and Chih-wen Weng.