有向Kirkman填充设计的谱

§ 1　IntroductionLet X be a set of v points.A packing(directed packing) of X is a collection of subsets(ordered subsets) of X(called blocks) such that any pair(ordered pair) of distinct pointsfrom X occur together in atmostone block in the collection.A packing(directed packing)is called resolvable ifitsblock setadmitsa partition into parallel classes,each parallel classbeing a partition of the pointset X.A Kirkman triple system KTS(v) is a collection Tof3 -subsets of X(triples) suchthat …     

Kirkman packing and covering designs with spanned holes of size 2

A Kirkman holey packing (resp. covering) design, denoted by KHPD(g^u) (resp. KHCD(g^u)), is a resolvable (gu, 3, 1) packing (resp. covering) design of pairs with u disjoint holes of size g, which has the maximum (resp. minimum) possible number of parallel classes. Each parallel class contains one block of size δ, while other blocks have size 3. Here δ is equal to 2, 3, and 4 when gu ≡ 2, 3, and 4 (mod 3) in turn. In this paper, the existence problem of a KHPD(2^u) and a KHCD(2^u) is solved with one possible exception of a KHPD(2⁸). © 2004 Wiley Periodicals, Inc.     

Existence of incomplete canonical Kirkman packing designs

For $u,v$ positive integers with $u\equiv v\equiv 4\left(mod6\right)$, let ICKPD$(u,v)$ denote a canonical Kirkman packing of order $u$ missing one of order $v$. In this paper, it is shown that the necessary condition for existence of an ICKPD$(u,v)$, namely $u\ge 3v+4$, is sufficient with a definite exception $(u,v)=(16,4)$, and except possibly when $v>76$, $v\equiv 4\left(mod12\right)$ and $u\in \{3v+4,3v+10\}$.     

Constructions of optimal packing designs

Let v and k be positive integers. A (v, k, 1)-packing design is an ordered pair (V, B) where V is a v-set and B is a collection of k-subsets of V (called blocks) such that every 2-subset of V occurs in at most one block of B. The packing problem is mainly to determine the packing number P(k, v), that is, the maximum number of blocks in such a packing design. It is well known that P(k, v) ≤ ⌊v⌊(v − 1)/(k − 1)⌋/k⌋ = J(k, v) where ⌊×⌋ denotes the greatest integer y such that y ≤ x. A (v, k, 1)-packing design having J(k, v) blocks is said to be optimal. In this article, we develop some general constructions to obtain optimal packing designs. As an application, we show that P(5, v) = J(5, v) if v ≡ 7, 11 or 15 (mod 20), with the exception of v ∈ {11, 15} and the possible exception of v ∈ {27, 47, 51, 67, 87, 135, 187, 231, 251, 291}. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 245–260, 1998     

Existence of resolvable optimal strong partially balanced designs

We shall refer to a strong partially balanced design SPBD(v,b,k;λ,0) whose b is the maximum number of blocks in all SPBD(v,b,k;λ,0), as an optimal strong partially balanced design, briefly OSPBD(v,k,λ). Resolvable strong partially balanced design was first formulated by Wang, Safavi-Naini and Pei [Combinatorial characterization of l-optimal authentication codes with arbitration, J. Combin. Math. Combin. Comput. 37 (2001) 205-224] in investigation of l-optimal authentication codes. This article investigates the existence of resolvable optimal strong partially balanced design ROSPBD(v,3,1). We show that there exists an ROSPBD(v,3,1) for any v?3 except v=6,12.     

On the existence of nearly Kirkman triple systems with subsystems

It is proved in this paper that the necessary and sufficient conditions for the existence of an incomplete nearly Kirkman triple system INKTS(u, v) are u ≡ v ≡ 0 (mod 6), u ≥ 3v. As a consequence, we obtain a complete solution to the embedding problem for nearly Kirkman triple systems.      

Using block designs in crossing number bounds

The crossing number $\mathrm{\text{CR}}\left(G\right)$ of a graph $G=\left(V,E\right)$ is the smallest number of edge crossings over all drawings of $G$ in the plane. For any $k\ge 1$, the $k$‐planar crossing number of $G,{\mathrm{\text{CR}}}_k\left(G\right)$, is defined as the minimum of $\text{CR}\left(G_1\right)+\text{CR}\left(G_2\right)+?+\text{CR}\left(G_k\right)$ over all graphs $G_1,G_2,\dots ,G_k$ with ${\cup }_{i=1}^k{G}_i=G$. Pach et al [Comput. Geom.: Theory Appl. 68 (2018), pp. 2–6] showed that for every $k\ge 1$, we have ${\text{CR}}_k\left(G\right)\le (2/k^2?1/k^3)\text{CR}\left(G\right)$ and that this bound does not remain true if we replace the constant $2/k^2?1/k^3$ by any number smaller than $1/k^2$. We improve the upper bound to $(1/k^2)\left(1+o\left(1\right)\right)$ as $k\to \infty$. For the class of bipartite graphs, we show that the best constant is exactly $1/k^2$ for every $k$. The results extend to the rectilinear variant of the $k$‐planar crossing number.     

A two-stage variable selection strategy for supersaturated designs with multiple responses

A supersaturated design (SSD), whose run size is not enough for estimating all the main effects, is commonly used in screening experiments. It offers a potential useful tool to investigate a large number of factors with only a few experimental runs. The associated analysis methods have been proposed by many authors to identify active effects in situations where only one response is considered. However, there are often situations where two or more responses are observed simultaneously in one screening experiment, and the analysis of SSDs with multiple responses is thus needed. In this paper, we propose a two-stage variable selection strategy, called the multivariate partial least squares-stepwise regression (MPLS-SR) method, which uses the multivariate partial least squares regression in conjunction with the stepwise regression procedure to select true active effects in SSDs with multiple responses. Simulation studies show that the MPLS-SR method performs pretty good and is easy to understand and implement.     

Expected wasted space of optimal simple rectangle packing

A simple packing of a collection of rectangles contained in [0,1]² is a disjoint subcollection such that each vertical line meets at most one rectangle of the packing. The wasted space of the packing is the surface of the area of the part of [0,1]² not covered by the packing. We prove that for a certain number L, for all N2, the wasted space W_N in an optimal simple packing of N independent uniformly distributed rectangles satisfiesWork partially supported by an N.S.F. grant.Mathematics Subject Classification (2000): 60D05     

Construction of optimal ternary constant weight codes via Bhaskar Rao designs

In this note, we consider a construction for optimal ternary constant weight codes (CWCs) via Bhaskar Rao designs (BRDs). The known existence results for BRDs are employed to generate many new optimal nonlinear ternary CWCs with constant weight 4 and minimum Hamming distance 5.     

Convergence of optimal stochastic bin packing

Consider independent identically distributed random variables (X_i) valued in [0,1]. Let B(n) be the optimal (minimum) number of unit size bins needed to pack n items of size X₁, X₂,…,X_n. We prove that there exists a numerical constant C such that for t > 0,

$\text{Pr(∣B(n)?E(B(n))∣>t}\text{n}\text{)≤ C exp(? t).}$

The constant C does not depend on the distribution of X.     

Construction of supersaturated design with large number of factors by the complementary design method

Supersaturated designs (SSDs) have been widely used in factor screening experiments. The present paper aims to prove that the maximal balanced designs are a kind of special optimal SSDs under the E(f _NOD) criterion. We also propose a new method, called the complementary design method, for constructing E(f _NOD) optimal SSDs. The basic principle of this method is that for any existing E(f _NOD) optimal SSD whose E(fNOD) value reaches its lower bound, its complementary design in the corresponding maximal balanced design is also E(f _NOD) optimal. This method applies to both symmetrical and asymmetrical (mixed-level) cases. It provides a convenient and efficient way to construct many new designs with relatively large numbers of factors. Some newly constructed designs are given as examples.     

一种构造多水平超饱和设计的新方法

超饱和设计在搜索试验中有重要应用.自上世纪九十年代迄今, 超饱和设计的研究取得了丰硕成果,研究的设计从二水平发展到多水平, 进而到混合水平;构造方法从巧妙的构思到利用组合理论进行系统构造,进而到各种算法的开发; 对于超饱和设计的评优准则也有更深入的认识.本文介绍一种构造多水平超饱和设计的新方法. 这种方法简单易行,很容易构造出具有优良性质的多水平超饱和设计, 有很强的实用性.     

Kirkman triple systems of order 21 with nontrivial automorphism group

There are 50,024 Kirkman triple systems of order 21 admitting an automorphism of order 2. There are 13,280 Kirkman triple systems of order 21 admitting an automorphism of order 3. Together with the 192 known systems and some simple exchange operations, this leads to a collection of 63,745 nonisomorphic Kirkman triple systems of order 21. This includes all KTS(21)s having a nontrivial automorphism group. None of these is doubly resolvable. Four are quadrilateral-free, providing the first examples of such a KTS(21).

     

On large sets of disjoint Kirkman triple systems

In this paper, we introduce LR(u) designs and use these designs together with large sets of Kirkman triple systems (LKTS) and transitive KTS (TKTS) of order v to construct an LKTS(uv). Our main result is that there exists an LKTS(v) for v∈{3nm(2·13k+1)t;n?1,k?1,t=0,1,m∈{1,5,11,17,25,35,43}}.     

Existence of non‐resolvable Steiner triple systems

We consider two well‐known constructions for Steiner triple systems. The first construction is recursive and uses an STS(v) to produce a non‐resolvable STS(2v + 1), for v ≡ 1 (mod 6). The other construction is the Wilson construction that we specify to give a non‐resolvable STS(v), for v ≡ 3 (mod 6), v > 9. © 2004 Wiley Periodicals, Inc. J Combin Designs 13: 16–24, 2005.     

A new exact method for the two-dimensional orthogonal packing problem

The two-dimensional orthogonal packing problem (2OPP) consists in determining if a set of rectangles (items) can be packed into one rectangle of fixed size (bin). In this paper we propose two exact algorithms for solving this problem. The first algorithm is an improvement on a classical branch&bound method, whereas the second algorithm is based on a new relaxation of the problem. We also describe reduction procedures and lower bounds which can be used within enumerative methods. We report computational experiments for randomly generated benchmarks which demonstrate the efficiency of both methods: the second method is competitive compared to the best previous methods. It can be seen that our new relaxation allows an efficient detection of non-feasible instances.