Decompositions of edge-colored complete graphs (Q1971615)

In this paper finite edge-\(r\)-colored directed graphs are considered. For a vertex \(x\) of an edge-\(r\)-colored digraph \(G\), the degree-vector of \(x\) is defined as the \(2r\)-vector \[ \tau (x)=(in_{1}(x),out_{1}(x),\ldots ,in_{r}(x),out_{r}(x)) \] where \(in_{j}(x)\) and \(out_{j}(x)\) denote, respectively, the indegree and outdegree of vertex \(x\) in the spanning subgraph of \(G\) determined by the edges of color \(j\), \(1\leq j\leq r\). Let \(\alpha (G)\) be the greatest common divisor of the integers \(t\) such that the \(2r\)-vector \((t,\ldots ,t)\) is an integral linear combination of the vectors \(\tau (x)\) as \(x\) ranges over \(V(G)\). A very general asymptotic existence theorem for decompositions of edge-colored complete graphs into prespecified edge-colored subgraphs is proved. A special case of this theorem is the following one: Let \(G\) be a simple edge-\(r\)-colored digraph with \(m\) edges each of \(r\) different colors. There exists a constant \(n_{0}=n_{0}(G)\) such that the complete edge-\(r\)-colored digraph with \(rn(n-1)\) edges \(K_{n}^{(r)}\) admits a \(G\)-decomposition for all integers \(n\geq n_{0}\) that satisfy the following conditions: \(n(n-1)\equiv 0\pmod m\) and \(n-1\equiv 0\pmod{\alpha (G)}\). Since many combinatorial design problems fall within this framework, this provides new proofs of the asymptotic existence of resolvable designs, near resolvable designs, group divisible designs, and grid designs. This important paper concludes with two further applications: the asymptotic existence of skew Room \(d\)-cubes and the asymptotic existence of \((v,k,1)\)-BIBDs with any group of order \(k-1\) as an automorphism group.