均匀拟阵(uniform matroid)是一种特殊的拟阵,设n≥r≥0是两个整数,E是一个含有n个元素的集合。如果I={X⊆E:|X|≤r},则称(E,I)是一个均匀拟阵, 记为Ur,n。
均匀拟阵是只以
有限集E的子集I中包含元素的数目多少决定其独立性的
拟阵Uk,n,其中n=|E|,E的子集B为拟阵的基,当且仅当B由k个元素组成。类似地,C为拟阵的圈,当且仅当C为k+1个元素组成。H为拟阵的
超平面,当且仅当H由k-1个元素组成。例如,U2,3中的E视为欧氏空间里一条直线上的3点,每一个单点构成U2,3的超平面,每两点构成该拟阵的一个基,而全部三个点是它的惟一的圈。
定理1 设E 是一个有限集,B⊆E,m≤|B|,则令J( m,B,E) = { A∈2E||A∩B|≤m}∈(E) ,称J(m,B,E)是E上的关于集合B的m拟阵独立集系( 简称广义均匀拟阵独立集系) ,且称( E,J(m,B,E) ) 为关于集合B的带独立集系的m拟阵( 简称广义均匀拟阵) ,E 上的广义均匀拟阵的全体记为 。
下面证明J(m,B,E) 满足I3,若A1,A2∈J(m,B,E) ,且|A1|<|A2|,下面证明存在e∈A2-A1使得|(A1∪{e})∩B|≤m,从而J(m,B,E) 满足I3。
情形一: 若|A1∩B||A2∩B|=m,存在e∈A2-B且e∈A2-A1,若不然有任意的e∈A2-B都有e∉A2-A1,即e∈A1,此时有|A1|=|A1∩B|+|A2-B|= m+|A2-B|=|A2∩B|+|A2-B|=|A2|,与|A1|<|A2|矛盾。 此时有|(A1∪{e}) ∩B|=m≤m成立。
情形二: 若|A1∩B|
情形三: 若|A1∩B|>|A2∩B|,则一定存在e∈A2-A1,且有e∉B,此时有|(A1∪{e})∩B|=|A1∩B|≤m。
例1 取E = { 1,2,3,4,5} ,B = { 1,3,5} ( 本题中Jm,B= {I∈2B||I|≤m} ) ,则
J( 0,B)= {∅,{2} ,{4} ,E-B}=2E-B⊕J0,B,
J(1,B) = {∅,{1,2,4} ,{1,4} ,{1,2} ,{1} ,{2,3,4} ,{2,3} ,{3,4} ,{3} ,{2,4,5} ,{2,5} ,{4,5} ,{5} ,{2} ,{4} ,{2,4} } = 2E-B⊕J1,B,
J(2,B) = {∅,{1,2,4} ,{1,4} ,{1,2} ,{1} ,{2,3,4} ,{2,3} ,{3,4} ,{3} ,{2,4,5} ,{2,5} ,{4,5} ,{5} ,{2} ,{4} ,{2,4} ,{1,2,3,4} ,{1,2,3} ,{1,3,4} ,{1,3} ,{1,2,4,5} ,{1,2,5} ,{1,4,5} ,{1,5} ,{2,3,4,5} ,{2,3,5} ,{3,4,5} ,{3,5} }= 2E-B⊕J2,B,
类似的通过计算,可以得到
J(3,B) =2E-B⊕J3,B.
基于例1 可以发现并证明下面的广义均匀拟阵的构造定理:
定理2 设E是一个有限集,B⊆E,m≤|B| ,则
J(m,B,E) = 2E-B⊕Jm,B.