The characterization of binary constant weight codes meeting the bound of Fu and Shen

Fu and Shen gave an upper bound on binary constant weight codes. In this paper, we present a new proof for the bound of Fu and Shen and characterize binary constant weight codes meeting this bound. It is shown that binary constant weight codes meet the bound of Fu and Shen if and only if they are generated from certain symmetric designs and quasi-symmetric designs in combinatorial design theory. In particular, it turns out that the existence of binary codes with even length meeting the Grey–Rankin bound is equivalent to the existence of certain binary constant weight codes meeting the bound of Fu and Shen. Furthermore, some examples are listed to illustrate these results. Finally, we obtain a new upper bound on binary constant weight codes which improves on the bound of Fu and Shen in certain case. This research is supported in part by the DSTA research grant R-394-000-025-422 and the National Natural Science Foundation of China under the Grant 60402031, and the NSFC-GDSF joint fund under the Grant U0675001     

Dispersion effects in unreplicated factorial designs

Methods for estimation of dispersion effects in two‐level unreplicated factorial designs are studied. The consequences of non‐constant variance are discussed. A natural assumption concerning the form of the covariance of location effects leads to a particular normal model. Some linear combinations of the response variables are constructed in order to make a simple structure for inference. The precision of point estimators of dispersion effects, where one is based on experiments with replicates, are compared. A numerical example is given as an illustration of a test. Finally, estimations in fractional designs are described and discussed. Copyright © 2002 John Wiley & Sons, Ltd.     

Existence of frame SOLS of type ab

An SOLS (self-orthogonal latin square) of order v with n_i missing sub-SOLS (holes) of order h_i (1ik), which are disjoint and spanning (i.e. ∑_i=1^k n_ih_i=v), is called a frame SOLS and denoted by FSOLS(h₁^n₁h₂^n₂ h_k^n_k). It has been proved that for b2 and n odd, an FSOLS(aⁿb¹) exists if and only if n4 and n1+2b/a. In this paper, we show the existence of FSOLS(aⁿb¹) for n even and FSOLS(aⁿ1¹) for n odd.     

Hill‐climbing to Pasch valleys

Exhaustive enumeration of Steiner Triple Systems is not feasible, due to the combinatorial explosion of instances. The next‐best hope is to quickly find a sample that is representative of isomorphism classes. Stinson's Hill‐Climbing algorithm [ 20 ] is widely used to produce random Steiner Triple Systems, and certainly finds a sample of systems quickly, but the sample is not uniformly distributed with respect to the isomorphism classes of STS with ν ≤ 19, and, in particular, we find that isomorphism classes with a large number of Pasch configurations are under‐represented. No analysis of the non‐uniformity of the distribution with respect to isomorphism classes or the intractability of obtaining a representative sample for ν > 19 is known. We also exhibit a modification to hill‐climbing that makes the sample if finds closer to the uniform distribution over isomorphism classes in return for a modest increase in running time. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 405–419, 2007     

Super-simple (ν, 5, 5) Designs

Super-simple designs are useful in constructing codes and designs such as superimposed codes and perfect hash families. In this article, we investigate the existence of a super-simple (ν, 5, 5) balanced incomplete block design and show that such a design exists if and only if ν ≡ 1 (mod 4) and ν ≥ 17 except possibly when ν = 21. Applications of the results to optical orthogonal codes are also mentioned. Research supported by NSERC grant 239135-01.     

Low rank matrix recovery from rank one measurements

We study the recovery of Hermitian low rank matrices $X\in {\mathbb{C}}^{n\times n}$ from undersampled measurements via nuclear norm minimization. We consider the particular scenario where the measurements are Frobenius inner products with random rank-one matrices of the form $a_j{a}_j^{?}$ for some measurement vectors $a_1,\dots ,a_m$, i.e., the measurements are given by $b_j=\mathrm{tr}(X{a}_j{a}_j^{?})$. The case where the matrix $X=x{x}^{?}$ to be recovered is of rank one reduces to the problem of phaseless estimation (from measurements $b_j=|〈x,a_j〉{|}^2$) via the PhaseLift approach, which has been introduced recently. We derive bounds for the number m of measurements that guarantee successful uniform recovery of Hermitian rank r matrices, either for the vectors $a_j$, $j=1,\dots ,m$, being chosen independently at random according to a standard Gaussian distribution, or $a_j$ being sampled independently from an (approximate) complex projective t-design with $t=4$. In the Gaussian case, we require $m\ge Crn$ measurements, while in the case of 4-designs we need $m\ge \mathit{Cr}n\log ?(n)$. Our results are uniform in the sense that one random choice of the measurement vectors $a_j$ guarantees recovery of all rank r-matrices simultaneously with high probability. Moreover, we prove robustness of recovery under perturbation of the measurements by noise. The result for approximate 4-designs generalizes and improves a recent bound on phase retrieval due to Gross, Krahmer and Kueng. In addition, it has applications in quantum state tomography. Our proofs employ the so-called bowling scheme which is based on recent ideas by Mendelson and Koltchinskii.     

8×4×2~n设计纯净两因子交互作用成分最大数的界

混水平部分因析设计在各类试验中有广泛应用.纯净效应准则是用于选取最优部分因析设计的重要准则之一.本文考虑含有一个八水平因子、一个四水平因子和若干二水平因子的8×4×2~n混水平设计,给出了分辨度为Ⅲ和Ⅳ的该类混水平设计包含纯净两因子交互作用成分最大数的上界和下界.下界通过构造特定设计而得到.     

Research problems from the BCC22

Open problems from the problem session at the 22nd British Combinatorial Conference at St Andrews, on 10 July 2009.