Constructions of optimal variable-weight OOCs via quadratic residues

Variable-weight optical orthogonal code (OOC) was introduced by G. C. Yang [IEEE Trans. Commun., 1996, 44: 47–55] for multimedia optical CDMA systems with multiple quality of service (QoS) requirements. In this paper, seven new infinite classes of optimal (v, {3, 4, 6}, 1,Q)-OOCs are constructed.     

单纯正交表OA$_\lambda(3, 5, v)$的存在性

An orthogonal array of strength t,degree k,order v and index λ,denoted by OAλ(t,k,v),is a λvt× k array on a v symbol set such that each λvt× t subarray contains each t-tuple exactly λ times.An OAλ(t,k,v) is called simple and denoted by SOAλ(t,k,v)if it contains no repeated rows.In this paper,it is proved that the necessary conditions for the existence of an SOAλ(3,5,v) with λ≥ 2 are also sufficient with possible exceptions where v = 6 and λ∈ {3,7,11,13,15,17,19,21,23,25,29,33}.     

码重为3和7的最优光正交码的具体构造

对光正交码(OOC)构造的关注源于它在光码分多址网络中有许多应用.截至目前,对于码重为W∈{{3,4},{3,5},{3,6},{4,5},{4,6]}的变重量光正交码的构造已经取得许多结果.然而,对于码重为W={3,7}的变重量光正交码的具体构造非常的少.给出一系列新的最优变重量光正交码(33p,{3,7},1,{4/5,1/5})-OOC的具体构造,对于任何素数p≡3(mod 4)且p≥7.     

Coding‐theoretic constructions for (t,m,s)‐nets and ordered orthogonal arrays

(t,m,s)‐nets are point sets in Euclidean s‐space satisfying certain uniformity conditions, for use in numerical integration. They can be equivalently described in terms of ordered orthogonal arrays, a class of finite geometrical structures generalizing orthogonal arrays. This establishes a link between quasi‐Monte Carlo methods and coding theory. The ambient space is a metric space generalizing the Hamming space of coding theory. We denote it by NRT space (named after Niederreiter, Rosenbloom and Tsfasman). Our main results are generalizations of coding‐theoretic constructions from Hamming space to NRT space. These comprise a version of the Gilbert‐Varshamov bound, the (u,u+υ)‐construction and concatenation. We present a table of the best known parameters of q‐ary (t,m,s)‐nets for qε{2,3,4,5} and dimension m≤50. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 403–418, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10015     

Construction of Asymmetric Orthogonal Arrays of Strength Three via a Replacement Method

A replacement procedure to construct orthogonal arrays of strength three was proposed by Suen et al. [7]. This method was later extended by Suen and Dey [8]. In this paper, we further explore the replacement procedure to obtain some new families of orthogonal arrays of strength three.     

On the existence of total dominating subgraphs with a prescribed additive hereditary property

Recently, Bacsó and Tuza gave a full characterization of the graphs for which every connected induced subgraph has a connected dominating subgraph satisfying an arbitrary prescribed hereditary property. Using their result, we derive a similar characterization of the graphs for which any isolate-free induced subgraph has a total dominating subgraph that satisfies a prescribed additive hereditary property. In particular, we give a characterization for the case where the total dominating subgraphs are a disjoint union of complete graphs. This yields a characterization of the graphs for which every isolate-free induced subgraph has a vertex-dominating induced matching, a so-called induced paired-dominating set.     

The spectrum of 2‐idempotent 3‐quasigroups with conjugate invariant subgroups

A ternary quasigroup (or 3‐quasigroup) is a pair (N, q) where N is an n‐set and q(x, y, z) is a ternary operation on N with unique solvability. A 3‐quasigroup is called 2‐idempotent if it satisfies the generalized idempotent law: q(x, x, y) = q(x, y, x) = q(y, x, x)=y. A conjugation of a 3‐quasigroup, considered as an OA(3, 4, n), $({{N}},{\mathcal{B}})$, is a permutation of the coordinate positions applied to the 4‐tuples of ${\mathcal{B}}$. The subgroup of conjugations under which $({{N}},{\mathcal{B}})$ is invariant is called the conjugate invariant subgroup of $({{N}},{\mathcal{B}})$. In this article, we determined the existence of 2‐idempotent 3‐quasigroups of order n, n≡7 or 11 (mod 12) and n≥11, with conjugate invariant subgroup consisting of a single cycle of length three. This result completely determined the spectrum of 2‐idempotent 3‐quasigroups with conjugate invariant subgroups. As a corollary, we proved that an overlarge set of Mendelsohn triple system of order n exists if and only if n≡0, 1 (mod 3) and n≠6. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 292–304, 2010     

A class of stochastic games with ordered field property

It is shown that discounted general-sum stochastic games with two players, two states, and one player controlling the rewards have the ordered field property. For the zero-sum case, this result implies that, when starting with rational data, also the value is rational and that the extreme optimal stationary strategies are composed of rational components.     

一类二元叠加码的构作及其d界

首先介绍了一种具有参数d,r的二元叠加(d,n,r)-码及偶特征正交空间上子空间的一些包含性质,然后利用这些性质及相关知识构作了二元叠加(d,n,r)-码并给出了其参数d的界.     

A combinatorial proof of a fixed point property

A class of finite simplicial complexes, called pseudo cones, is developed that has a number of useful combinatorial properties. A partially ordered set is a pseudo cone if its order complex is a pseudo cone. Pseudo cones can be constructed from other pseudo cones in a number of ways. Pseudo cone ordered sets include finite dismantlable ordered sets and finite truncated noncomplemented lattices. The main result of the paper is a combinatorial proof of the fixed simplex property for finite pseudo cones in which a combinatorial structure is constructed that relates fixed simplices to one another. This gives combinatorial proofs of some well known non-constructive results in the fixed point theory of finite partially ordered sets.     

The asymptotic efficiency of randomized nets for quadrature

An -type discrepancy arises in the average- and worst-case error analyses for multidimensional quadrature rules. This discrepancy is uniquely defined by , which serves as the covariance kernel for the space of random functions in the average-case analysis and a reproducing kernel for the space of functions in the worst-case analysis. This article investigates the asymptotic order of the root mean square discrepancy for randomized -nets in base . For moderately smooth the discrepancy is , and for with greater smoothness the discrepancy is , where is the number of points in the net. Numerical experiments indicate that the -nets of Faure, Niederreiter and Sobol' do not necessarily attain the higher order of decay for sufficiently smooth kernels. However, Niederreiter nets may attain the higher order for kernels corresponding to spaces of periodic functions.

     

广义正交表方差分析的矩阵计算形式

广义正交表是一种类似于正交表的新设计.它是正交表的推广,可以像正交表一样进行试验设计和数据分析,但试验次数大幅减少.方差分析是统计推断的内容之一,本文从自由模型出发考虑方差分析,采用矩阵象技术,给出了广义正交表方差分析的矩阵计算形式,借助SAS软件可以方便快速的实现.     

变系数偏微分方程组一般解的构造

求解偏微分方程不仅有理论意义,而且有实用价值.本文利用共轭算子的性质给出构造偏微分方程组一般解的方法.     

Free product actions with relative property (T) and trivial outer automorphism groups

We show that every non-amenable free product of groups admits free ergodic probability measure preserving actions which have relative property (T) in the sense of S. Popa (2006) [Pop06, Def. 4.1]. There are continuum many such actions up to orbit equivalence and von Neumann equivalence, and they may be chosen to be conjugate to any prescribed action when restricted to the free factors. We exhibit also, for every non-amenable free product of groups, free ergodic probability measure preserving actions whose associated equivalence relation has trivial outer automorphisms group. This gives, in particular, the first examples of such actions for the free group on 2 generators.     

On a superadditivity property of Gram’s determinant

Summary Some superadditivity properties are given for Gram determinants involving inner products on a linear space.     

Applications of Hajós‐Type Constructions to the Hedetniemi Conjecture

Hedetniemi conjectured in 1966 that if G and H are finite graphs with chromatic number n, then the chromatic number of the direct product of G and H is also n. We mention two well‐known results pertaining to this conjecture and offer an improvement of the one, which partially proves the other. The first of these two results is due to Burr et al. (Ars Combin 1 (1976), 167–190), who showed that when every vertex of a graph G with is contained in an n‐clique, then whenever . The second, by Duffus et al. (J Graph Theory 9 (1985), 487–495), and, obtained independently by Welzl (J Combin Theory Ser B 37 (1984), 235–244), states that the same is true when G and H are connected graphs each with clique number n. Our main result reads as follows: If G is a graph with and has the property that the subgraph of G induced by those vertices of G that are not contained in an n‐clique is homomorphic to an ‐critical graph H, then . This result is an improvement of the result by the first authors. In addition we will show that our main result implies a special case of the result by the second set of authors. Our approach will employ a construction of a graph F, with chromatic number , that is homomorphic to G and H.     

Enhancing RLT relaxations via a new class of semidefinite cuts

In this paper, we propose a mechanism to tighten Reformulation-Linearization Technique (RLT) based relaxations for solving nonconvex programming problems by importing concepts from semidefinite programming (SDP), leading to a new class of semidefinite cutting planes. Given an RLT relaxation, the usual nonnegativity restrictions on the matrix of RLT product variables is replaced by a suitable positive semidefinite constraint. Instead of relying on specific SDP solvers, the positive semidefinite stipulation is re-written to develop a semi-infinite linear programming representation of the problem, and an approach is developed that can be implemented using traditional optimization software. Specifically, the infinite set of constraints is relaxed, and members of this set are generated as needed via a separation routine in polynomial time. In essence, this process yields an RLT relaxation that is augmented with valid inequalities, which are themselves classes of RLT constraints that we call semidefinite cuts. These semidefinite cuts comprise a relaxation of the underlying semidefinite constraint. We illustrate this strategy by applying it to the case of optimizing a nonconvex quadratic objective function over a simplex. The algorithm has been implemented in C++, using CPLEX callable routines, and two types of semidefinite restrictions are explored along with several implementation strategies. Several of the most promising lower bounding strategies have been implemented within a branch-and-bound framework. Computational results indicate that the cutting plane algorithm provides a significant tightening of the lower bound obtained by using RLT alone. Moreover, when used within a branch-and-bound framework, the proposed lower bound significantly reduces the effort required to obtain globally optimal solutions.     

Direct constructions of additive codes

A code is q^m‐ary q‐linear if its alphabet forms an m‐dimensional vector space over ??_q and the code is linear over ??_q. These additive codes form a natural generalization of linear codes. Our main results are direct constructions of certain families of additive codes. These comprise the additive generalization of the Kasami codes, an additive generalization of the Bose‐Bush construction of orthogonal arrays of strength 2 as well as a class of additive codes which are being used for deep space communication. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 207–216, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.20000     

New Algorithms of Distance-Increasing Mappings from Binary Vectors to Permutations by Swaps

Mappings from the set of binary vectors of a fixed length to the set of permutations of the same length that strictly increase Hamming distances are useful for the construction of permutation codes (permutation arrays). In this paper, we propose new simpler algorithms of distance-increasing mappings. These algorithms do not need any table lookup operations, and they are built up with fewer swap perations. In the comparison of our new algorithms with other DIMs, we also give some numerical results to illustrate that the distance expansion distributions of our new mappings are not bad.