Asymptotic Existence of Resolvable Graph Designs
Asymptotic Existence of Resolvable Graph Designs
复制标题
可解析图设计的渐近存在性
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
A. Ling
中科院分区：
文献类型：
--
作者：
P. Dukes;A. Ling
摘要 设 $v,ge ,k,ge ,1$ 和 $lambda ,ge ,0$ 为整数。块设计 $ ext{BD}left( v,,k,,lambda
ight)$ 是 $v$ 集合 $X$ 的 $k$ 子集的 $mathcal{A}$ 集合，其中 $X$ 中的每个无序元素对都包含在 $mathcal{A}$ 的 $lambda $ 元素中。更一般地，对于固定的简单图 $G$ ，图设计 $ ext{GD}left( v,,G,,lambda
ight)$ 是与 $G$ 同构的图的集合 $mathcal{A}$，其顶点位于 $X$ 中，使得 $X$ 中的每个无序元素对恰好是 $mathcal{A}$ 的 $lambda $ 元素的边。 Wilson 的一个著名结果表明，对于固定的 $$ 和 $lambda $ ，存在 $ ext{GD}left( v,,G,,lambda
ight)$ 对于所有足够大的 $ $ 满足某些必要条件。如果 $mathcal{A}$ 可以划分为（顶点集划分的图） $X$ 的分区，则上述块（图）设计是可解析的。 Lu 证明了可解析的 $ ext{BD}left( v,,k,,lambda 的 $v$ 中渐近存在性
ight)$ ，但二十多年来，类似的问题可解决 $ ext{GD}left( v,,G,,lambda
ight)$ 仍然开放。在本文中，我们解决了可解析图设计的渐近存在性。
Abstract Let $v,ge ,k,ge ,1$ and $lambda ,ge ,0$ be integers. A block design $ ext{BD}left( v,,k,,lambda
ight)$ is a collection $mathcal{A}$ of $k$ -subsets of a $v$ -set $X$ in which every unordered pair of elements from $X$ is contained in exactly $lambda $ elements of $mathcal{A}$ . More generally, for a fixed simple graph $G$ , a graph design $ ext{GD}left( v,,G,,lambda
ight)$ is a collection $mathcal{A}$ of graphs isomorphic to $G$ with vertices in $X$ such that every unordered pair of elements from $X$ is an edge of exactly $lambda $ elements of $mathcal{A}$ . A famous result of Wilson says that for a fixed $ $ and $lambda $ , there exists a $ ext{GD}left( v,,G,,lambda
ight)$ for all sufficiently large $ $ satisfying certain necessary conditions. A block (graph) design as above is resolvable if $mathcal{A}$ can be partitioned into partitions of (graphs whose vertex sets partition) $X$ . Lu has shown asymptotic existence in $v$ of resolvable $ ext{BD}left( v,,k,,lambda
ight)$ , yet for over twenty years the analogous problem for resolvable $ ext{GD}left( v,,G,,lambda
ight)$ has remained open. In this paper, we settle asymptotic existence of resolvable graph designs.