Skip to content

区组设计

Block design

使每个小子集在固定数量区组中出现的均衡有限集合族。

条目类型
定义

形式陈述

取整数 1tkvλ1t-(v,k,λ) 区组设计是二元组 (X,B)X 是含 v 个点的有限集B(Xk) 是一族 k 元子集(称为区组),使得 X 的每个 t 元子集恰好包含在 λ 个区组中。本页默认采用简单设计约定,即 B 中区组互不重复。双计数"t 元子集与包含它的区组"的配对,得区组总数

b=λ(vt)(kt);

更一般地,对 0st,每个 s 元子集所处的区组数与该子集的选取无关,为

λs=λ(vsts)(ksts).

由于这些量都是计数,参数 (t,v,k,λ) 必须使所有 λs 为整数,这称为可除性(整除)条件。

直觉

区组设计的出发点是"公平"。设想要用若干次小规模试验比较 v 种处理,每次试验只能容纳 k 种:若某两种处理同场出现的次数比别的组合多,它们之间的比较就占了更多数据,结论会有偏。要求每个 t 元组恰好共同出现 λ 次,就是把这种偏差在设计层面归零——统计学家 Fisher 与 Yates 在农业试验中正是为此引入了均衡不完全区组设计。从组合角度看,它把"每对对象共同出现同样多次"(t=2)推广为任意阶的局部均衡;而 λs 公式表明高阶均衡自动蕴含所有低阶均衡:一个 t-设计同时也是 s-设计(s<t)。这种"处处一样"的强对称要求,正是设计比一般集合族稀有得多、又有用得多的原因。

例子与边界

Fano 平面是最小的非平凡例子:以七个点、七条"直线"(每线三点)构成 2-(7,3,1) 设计,任意两点恰在一条直线上。代入公式验证:b=1(72)/(32)=21/3=7,每点处于 r=λ1=6/2=3 条线上,与图形一致。它同时是有限域 F2 上的射影平面,展示了设计与有限几何的联系。Steiner 三元系是 2-(v,3,1) 设计;Kirkman 证明了它存在当且仅当 v1,3(mod6)

整除条件只是必要条件,并不保证设计存在,这是初学者最易忽略的边界。经典反例是 2-(43,7,1):其参数使 b=43r=7 均为整数,但该设计(即六阶射影平面)被 Bruck–Ryser 定理排除,根本不存在。另一处约定性边界是重复区组:允许同一区组多次出现时,应把 B 改为多重集并按重数计入"包含次数",称为多重设计;本页默认简单设计。最后,区组设计不同于一般 k 一致超图——超图对子集的出现次数没有任何均衡要求,设计则要求精确均衡,因此可视为超图中高度正则的特殊类。

推论与应用

t=2 的情形即均衡不完全区组设计(BIBD)。Fisher 不等式断言非平凡 2-设计(v>k)必有 bv,等号成立的对称设计(如射影平面)同时是有限几何的核心对象。在统计实验中,BIBD 把处理分配在容量受限的区组内,以控制区组间异质性;数据分析可写成含区组与处理项的线性模型,并由方差分析比较相应平方和。组合上的出现次数平衡并不自动提供随机化、误差独立、同方差或因果解释,这些条件必须由实验方案另行给出。

在编码理论中,设计与好码可以互相生成:完备码的固定重量码字支撑集构成 Steiner 系统,反过来,设计也可用来构造并分析线性码的重量分布。相同的覆盖均衡思想还用于抽样方案、软件成对测试覆盖与密钥分配,但每个场景对区组、重复和容错的解释并不相同。

存在性理论关心满足参数方程的组合对象是否真的存在。Keevash 于 2014 年证明:对任意固定的 t,k,λ,只要 v 充分大且满足全部整除条件,t-(v,k,λ) 设计必然存在,从而把长期悬而未决的一般存在性问题化归为有限多个小参数例外。

参考资料
  • J. H. van Lint and R. M. Wilson, A Course in Combinatorics, 2nd ed., Cambridge University Press, 2001,Ch. 19, t-designs, BIBDs, and parameter equations。
  • Douglas R. Stinson, Combinatorial Designs: Constructions and Analysis, Springer, 2004,Chs. 1 and 9, BIBDs, t-designs, parameter identities, and examples。
  • Peter Keevash, “The Existence of Designs,” Annals of Mathematics 177(3), 2014,general existence theorem under divisibility conditions for sufficiently large parameters。
关系图谱7 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
分类位置

上位 / 更一般

下位 / 直接特例

暂未标注直接特例。