拉丁方陣的橫截問題及其應用

Abstract

一個ｋ×ｎ拉丁長方陣（LATIN RECTANGLE ）是一個數字陣列，使得每一刻均為｛１ ，２，…，ｎ｝的置換，而且每一行的數字均相異。假如ｋ＝ｎ則我們稱此陣列為拉 丁方陣（LATIN SQUARE）。在一個ｎ階（ｎ≧ｋ）拉丁方陣中長度為ｋ的部份橫截（ PARTIAL TRANSVERSLA ）是由ｋ個不同元素組成的一個集合，使得在集中入元素皆在 不同列不同行。兩個部份橫截被稱互斥（DISJOINT）如果其元素皆來自不同位置。有 關橫截的最大長度為ｎ，否則為ｎ－１。但目前仍然未解決，而我們有興趣的是在拉 丁方陣的所有分解中決定最少數目的互斥部份橫截。 一個由ERDOS, FABER, LOVASZ所提的臆測：給ｎ個集合Ａ1，Ａ2 ，每一集合Ａi包含 ｎ個元素１≦ｉ≦ｎ，而且任二個集中至多只有一個共同元素，然後我們用ｎ種顏色 去塗所有集合聯集中的元素使得每一個集合Ａi 中的元素都具有不同的塗色。我們可 將此問題用方塊設計（BLOCK DESIGN）的觀點來看。即是否可將此ＰＢＤ（｜Ｓ｜＝ ｎ，λ＝１）分成ｎ組部分平行族（PARTIAL PARALLEL CLASSES）文中我們針對史坦 納三元系ＳＴＳ（Ｖ）來探討。史坦納三元系（ＳＴＳ（Ｖ））指的是Ｖ元集Ｓ中的 ３－子集（ TRIPLE） 組成的一個子集族ｔ，使得Ｖ中的每一對元素恰出現在子集族 ｔ中一次。對於ＳＴＳ（Ｖ）Ｖ≦１５這個臆測是對的，但至目前沒有更進一步的結 果。在本文首先探討拉丁方陣互斥部份橫截（ＤＰＴ）數目，然後利用此數目去找史 坦納三元系ＳＴＳ（３Ｖ）部份平行族數目，此ＳＴＳ（３Ｖ）包含三組彼此互斥的 Ｖ元素史坦納三元系。