群試設計，距離正則圖，圖譜理論及它們的關連

Abstract

群試設計有著篩檢 DNA 序列的應用。為因應尋找群試設計統一性的建構，群試空間出現在前人的研究中。群試空間是一個有秩偏序集滿足以下條件：每一元素上方元素導出的偏序子集均具原子性。我們發現在文獻中已被深入研究的幾何晶格結構也是群試空間，因此在同一架構下提供了許多的群試設計。根據相同的概念，我們也可以利用一個距離正則圖及其距離正則子圖來建構群試空間，因此我們研究如何在給定距離正則圖中建構出距離正則子圖。利用此結果我們解決一類距離正則圖的存在問題。距離正則圖常以等號情形出現在組合學或線性代數相關不等式中，如同我們在數列的算幾不等式中所見，等號情形發生在數列具某種規律的狀況。考慮給定圖對應的鄰接矩陣的最大特徵值，我們找到一些準確的上界，達到上界的圖也滿足一種特殊的規律性。

This dissertation contains three quite different subjects: posets, distance-regular graphs, and spectral graph theory. Motivated by the constructions of pooling designs, we study these three subjects through interesting links among them. A pooling space is a ranked poset P such that the subposet w+ induced by the elements above w is atomic for each element w of P. Pooling spaces were introduced in [Discrete Mathematics 282:163-169, 2004] for the purpose of giving a uniform way to construct pooling designs, which have applications to the screening of DNA sequences. We find that a geometric lattice, a well-studied structure in literature, is also a pooling space. This provides us many classes of pooling designs, some old and some new. Following the same concept, the poset constructed from a distance-regular graph with its distance-regular subgraphs is also a pooling space. For a special class of distance-regular graphs, we show the existence of their distance-regular subgraphs with any given diameter. The nonexistence of a class of distance-regular graphs follows from the line of study. Distance-regular graphs appear often in some extremal class of combinatorial or linear algebraic inequalities. As we can see from the inequality of arithmetic and geometric means of a sequence of positive real numbers, the equality occurs when the sequence has some regular patterns. We consider the maximum eigenvalues of the adjacency matrices of graphs and present sharp upper bounds of them. The graphs which attain the bounds also satisfy a special kind of regularity.