獨立代表系

獨立代表系(system of independent representatives)是代表系的一種，Rado推廣了相異代表系(SDR)的概念，建立了獨立代表系的理論。

基本介紹

• 中文名：獨立代表系
• 外文名：system of independent representatives
• 簡寫：SIR
• 所屬學科：數學
• 所屬問題：組合學(經典組合學)
• 相關概念：相異代表系(SDR)，Hall特性等

獨立關係的概念

設S是一個集，S的一個獨立關係是一個關係序列 ，其中 ( 是S的n次卡氏冪集，即S的n元序列，簡稱n塔，即 的集)，因而 是S 上的一個n元關係，滿足下面特性：

(i)若 ，則必有 ；

(ii)若 ，則必有 ，對{1，2，…，n}的任何置換 都成立。

(iii)若 ，則必存在 ，使

(iv)對於任何 ，必有 。

設 ，則 就叫做獨立的。否則，就是相關的。

由定義可知，一個獨立序列的子序列也是獨立的。獨立序列與序列的次序無關，而且，只要序列中含有相等元，則該序列就是相關的。

我們可以舉出獨立關係的例子。

把獨立關係解析為不等關係，則上述(i)一(iv)條件滿足，因為 均相異，則 必相異，滿足(i)。相異關係與元的次序無關，滿足(ii)。 相異，且 亦相異，則後者之中至少有一個y與 都相異，滿足(iii)。因為 ，所以 ，滿足(iv)。

又如，我們可以把S解析為一個向量空間，獨立關係解析為向量的線性獨立關係，即若向量 線性獨立，則 。反之，若 線性相關，則 ，這亦滿足(i)-(iv)條件。因為，若 線性無關，則 亦線性無關，滿足(i)。線性無關的特徵與向量的順序無關，滿足(ii)。若 ，即 線性無關，又若 ，即 亦線性無關，如果不存在 使y與 線性無關，即任一個都與相關，則 亦必線性相關，與所設矛盾，滿足(iii)。最後，向量x與自身線性相關，滿足(iv)。

集S的子集序列 叫做具有Hall特性(Hall條件的推廣)，如果對於每個 ，子集 中的任何k塔的並集必包含 使 。

獨立代表系的概念

設 是集S的子集序列， 叫做 的一個獨立代表系(簡稱為SIR)，如果 且 。

若把獨立關係解析為不等關係，則 相異，且 ，故 為子集族 的一個SDR，由此可見SIR是相異代表系(SDR)的一個推廣。

下面給出子集序列存在一個SIR的充要條件。

定理(Rado) 集s的非空子集序列 有一個獨立代表系(SIR)的充要條件是 具有Hall特性。