組合數學研討會
主講者: 1. 張惠蘭 教授 (國立高雄大學) 2. 黃喻培 博士 (義守大學)
講題: 1. Algorithmic Lovasz Local Lemma and its Applications to Group Testing 2. Nonexistence of a Class of Distance-regular Graphs
時間: 2014-05-30 (Fri.)  14:00 - 17:00
地點: 數學所 617 研討室 (台大院區)
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 $r$ others. We study a variation of cover-free family: A binary matrix is ${(r, w]-consecutive-disjunct}$ if for any $w$ cyclically consecutive columns $C_1,\cdots, C_w$ and another $r$ cyclically consecutive columns $C_{w+1},\cdots, C_{w+r}$, there exists one row intersecting $C_1, \cdots C_w$ but none of $C_{w+1},\cdots, C_{w+r}$. 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 $(r, w]$-consecutive-disjunct matrix of $n$ 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 $\Gamma$ denote a distance-regular graph with diameter $D \geq 3$ and intersection numbers $a_1=0, a_2 \neq 0$, and $c_2=1$. We show the connection between the $d$-bounded property and the nonexistence of parallelograms of any length up to $d+1$. Assume further that $\Gamma$ is with classical parameters $(D, b, \alpha, \beta)$, Pan and Weng $(2009)$ showed that $(b, \alpha, \beta)= (-2, -2, ((-2)^{D+1}-1)/3).$ Under the assumption $D \geq 4$, 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.
  || Close window ||