共查询到20条相似文献,搜索用时 62 毫秒
1.
Let n and k be positive integers. Let Cq be a cyclic group of order q. A cyclic difference packing (covering) array, or a CDPA(k, n; q) (CDCA(k, n; q)), is a k × n array (aij) with entries aij (0 ≤ i ≤ k−1, 0 ≤ j ≤ n−1) from Cq such that, for any two rows t and h (0 ≤ t < h ≤ k−1), every element of Cq occurs in the difference list
at most (at least) once. When q is even, then n ≤ q−1 if a CDPA(k, n; q) with k ≥ 3 exists, and n ≥ q+1 if a CDCA(k, n; q) with k ≥ 3 exists. It is proved that a CDCA(4, q+1; q) exists for any even positive integers, and so does a CDPA(4, q−1; q) or a CDPA(4, q−2; q). The result is established, for the most part, by means of a result on cyclic difference matrices with one hole, which is of interest in its own right. 相似文献
2.
Covering arrays have applications in software, network and circuit testing. In this article, we consider a generalization of covering arrays that allows mixed alphabet sizes as well as a graph structure that specifies the pairwise interactions that need to be tested. Let k and n be positive integers, and let G be a graph with k vertices v1,v2,…, vk with respective vertex weights g1 ≤ g2 ≤ … ≤ gk. A mixed covering array on G, denoted by , is an n × k array such that column i corresponds to vi, cells in column i are filled with elements from ?gi and every pair of columns i,j corresponding to an edge vi,vj in G has every possible pair from ?gi × ?gj appearing in some row. The number of rows in such array is called its size. Given a weighted graph G, a mixed covering array on G with minimum size is called optimal. In this article, we give upper and lower bounds on the size of mixed covering arrays on graphs based on graph homomorphisms. We provide constructions for covering arrays on graphs based on basic graph operations. In particular, we construct optimal mixed covering arrays on trees, cycles and bipartite graphs; the constructed optimal objects have the additional property of being nearly point balanced. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 393–404, 2007 相似文献
3.
L. V. Shabunin 《Algebra and Logic》2001,40(3):194-204
Let m and n be fixed integers, with 1 m < n. A Cantor variety C
m,n is a variety of algebras with m
n-ary and n
m-ary basic operations which is defined in a signature ={g1,...,gm,f1,...,fn} by the identities fig1x1,...,xn),...,gmx1,...,xn) = xi, i=1,...,n, gjf1x1,...,xm),...,fnx1,...,xm)) = xj, j=1,...,m. We prove the following: (a) every partial C
m,n-algebra A is isomorphically embeddable in the algebra G= A; S(A) of C
m,n; (b) for every finitely presented algebra G= A; S in C
m,n, the word problem is decidable; (c) for finitely presented algebras in C
m, the occurrence problem is decidable; (d) C
m,n has a hereditarily undecidable elementary theory. 相似文献
4.
A De Bruijn torus is a periodicd-dimensionalk-ary array such that eachn
1 × ... ×n
d
k-ary array appears exactly once with the same period. We describe two new methods of constructing such arrays. The first is a type of product that constructs ak
1
k
2
-ary torus from ak
1
-ary torus and ak
2
-ary torus. The second uses a decomposition of ad-dimensional torus to produce ad+1 dimensional torus. Both constructions will produce two dimensionalk-ary tori for which the period is not a power ofk. In particular, for
and for all natural numbers (n
1
, n
2
), we construct 2-dimensionalk-ary De Bruijn tori with order n
1
, n
2
and period
where
.Dedicated to the memory of Tony BrewsterPartially supported by NSF grant DMS-9201467Partially supported by a grant from the Reidler Foundation 相似文献
5.
The notion of a grid holey packing (GHP) was first proposed for the construction of constant composite codes. For a GHP (k, 1; n × g) of type [w
1, . . . , w
g
], where , the fundamental problem is to determine the packing number N([w
1, . . . , w
g
], 1; n × g), that is, the maximum number of blocks in such a GHP. In this paper we determine completely the values of N([w
1, . . . , w
g
], 1; n × g) in the case of block size .
相似文献
6.
Arthur H. Busch Michael J. Ferrara Stephen G. Hartke Michael S. Jacobson Hemanshu Kaul Douglas B. West 《Journal of Graph Theory》2012,70(1):29-39
An n‐tuple π (not necessarily monotone) is graphic if there is a simple graph G with vertex set {v1, …, vn} in which the degree of vi is the ith entry of π. Graphic n‐tuples (d, …, d) and (d, …, d) pack if there are edge‐disjoint n‐vertex graphs G1 and G2 such that d(vi) = d and d(vi) = d for all i. We prove that graphic n‐tuples π1 and π2 pack if , where Δand δdenote the largest and smallest entries in π1 + π2 (strict inequality when δ = 1); also, the bound is sharp. Kundu and Lovász independently proved that a graphic n‐tuple π is realized by a graph with a k‐factor if the n‐tuple obtained by subtracting k from each entry of π is graphic; for even n we conjecture that in fact some realization has k edge‐disjoint 1‐factors. We prove the conjecture in the case where the largest entry of π is at most n/2 + 1 and also when k?3. © 2011 Wiley Periodicals, Inc. J Graph Theory 相似文献
7.
J. L. Hayden 《Designs, Codes and Cryptography》1997,12(1):69-73
The paper studies a generalized Hadamard matrix H = (g
i
j) of order n with entries gi
j from a group G of order n. We assume that H satisfies: (i) For m k, G = {g
m
i
g
k
i
-1 i = 1,...., n} (ii) g
1i = g
i1 = 1 for each i; (iii) g
ij
-1 = g
ji for all i, j. Conditions (i) and (ii) occur whenever G is a(P, L) -transitivity for a projective plane of order n. Condition (iii) holds in the case that H affords a symmetric incidence matrix for the plane. The paper proves that G must be a 2-group and extends previous work to the case that n is a square. 相似文献
8.
é. M. Galeev 《Mathematical Notes》1978,23(2):109-117
An ordered estimate is obtained for the approximation by Fourier sums, in the metric ofd=(d
1
, ...,d
n
), 1<dj<,j=1, ...,n of classes of periodic functions of several variables with zero means with respect to all their arguments, having m mixed derivatives of order a1..., am., ai rn. which are bounded in the metrics ofp
i
=p
1
i
, ..., p
n
i
, i
j i <,i=i, ...,n, j=1, ...,n by the constants 1, ., m, respectively.Translated from Matematicheskie Zametki, Vol. 23, No. 2, pp. 197–212, February, 1978. 相似文献
9.
The grid graph is the graph on [k]
n
={0,...,k–1}
n
in whichx=(x
i
)
1
n
is joined toy=(y
i
)
1
n
if for somei we have |x
i
–y
i
|=1 andx
j
=y
j
for allji. In this paper we give a lower bound for the number of edges between a subset of [k]
n
of given cardinality and its complement. The bound we obtain is essentially best possible. In particular, we show that ifA[k]
n
satisfiesk
n
/4|A|3k
n
/4 then there are at leastk
n–1
edges betweenA and its complement.Our result is apparently the first example of an isoperimetric inequality for which the extremal sets do not form a nested family.We also give a best possible upper bound for the number of edges spanned by a subset of [k]
n
of given cardinality. In particular, forr=1,...,k we show that ifA[k]
n
satisfies |A|r
n
then the subgraph of [k]
n
induced byA has average degree at most 2n(1–1/r).Research partially supported by NSF Grant DMS-8806097 相似文献
10.
L. Ji 《Designs, Codes and Cryptography》2006,38(1):83-95
A 3-(n,4,1) packing design consists of an n-element set X and a collection of 4-element subsets of X, called blocks, such that every 3-element subset of X is contained in at most one block. The packing number of quadruples d(3,4,n) denotes the number of blocks in a maximum 3-(n,4,1) packing design, which is also the maximum number A(n,4,4) of codewords in a code of length n, constant weight 4, and minimum Hamming distance 4. In this paper the last packing number A(n,4,4) for n≡ 5(mod 6) is shown to be equal to Johnson bound
with 21 undecided values n=6k+5, k∈{m: m is odd , 3≤ m≤ 35, m≠ 17,21}∪ {45,47,75,77,79,159}.
AMS Classification:05B40, 94B25 相似文献
11.
P. D. Seymour 《Combinatorica》1982,2(1):91-97
De Bruijn and Erdős proved that ifA
1, ...,A
k
are distinct subsets of a set of cardinalityn, and |A
i
∩A
j
|≦1 for 1≦i<j ≦k, andk>n, then some two ofA
1, ...,A
k
have empty intersection. We prove a strengthening, that at leastk /n ofA
1, ...,A
k
are pairwise disjoint. This is motivated by a well-known conjecture of Erdőds, Faber and Lovász of which it is a corollary.
Partially supported by N. S. F. grant No. MCS—8103440 相似文献
12.
Let A={a1,a2,…}(a1<a2<) be an infinite sequence of nonnegative integers, let k≥2 be a fixed integer and denote by rk(A,n) the number of solutions of ai1+ai2++aik≤n. Montgomery and Vaughan proved that r2(A,n)=cn+o(n1/4) cannot hold for any constant c>0. In this paper, we extend this result to k>2. 相似文献
13.
M. Szegedy 《Combinatorica》1986,6(1):67-71
The following conjecture of R. L. Graham is verified: Ifn≧n
0, wheren
0 is an explicitly computable constant, then for anyn distinct positive integersa
1,a
2, ...,a
n
we have
a
i
/(a
i
,a
j
) ≧ ≧n, and equality holds only in two trivial cases. Here (a
i
,a
j
) stands for the greatest cnmmon divisor ofa
i
anda
j
. 相似文献
14.
Márk Horváth 《Discrete Mathematics》2008,308(19):4378-4388
An (n,a,b)-perfect double cube is a b×b×b sized n-ary periodic array containing all possible a×a×a sized n-ary array exactly once as subarray. A growing cube is an array whose cj×cj×cj sized prefix is an (nj,a,cj)-perfect double cube for , where and n1<n2<?. We construct the smallest possible perfect double cube (a 256×256×256 sized 8-ary array) and growing cubes for any a. 相似文献
15.
A very special case of one of the theorems of the authors states as follows: Let 1a
1a
2... be an infinite sequence of integers for which all the sumsa
i
+a
j
, 1ij, are distinct. Then there are infinitely many integersk for which 2k can be represented in the forma
i
+a
j
but 2k+1 cannot be represented in this form. Several unsolved problems are stated.Dedicated to our friend Professor E. Hlawka on the occasion of his seventieth birthday 相似文献
16.
Given a sequence A = (a 1, …, a n ) of real numbers, a block B of A is either a set B = {a i , a i+1, …, a j } where i ≤ j or the empty set. The size b of a block B is the sum of its elements. We show that when each a i ∈ [0, 1] and k is a positive integer, there is a partition of A into k blocks B 1, …, B k with |b i ?b j | ≤ 1 for every i, j. We extend this result in several directions. 相似文献
17.
Pavel Valtr† 《Combinatorica》2003,23(1):151-184
In this paper we study labeled–tree analogues of
(generalized) Davenport–Schinzel sequences.We say that two sequences a
1 ...
a
k
, b
1 ...
b
k
of equal length
k are isomorphic, if
a
i
= a
j
i
b
i
= b
j
(for all
i, j). For example, the sequences 11232,
33141 are isomorphic. We investigate the maximum size of a
labeled (rooted) tree with each vertex labeled by one of
n labels in such a way that,
besides some technical conditions, the sequence of labels along
any path (starting from the root) contains no subsequence
isomorphic to a fixed forbidden sequence
u.We study two models of such labeled trees. Each of the
models is known to be essentially equivalent also to other
models. The labeled paths in a special case of one of our models
correspond to classical Davenport–Schinzel sequences.We investigate, in particular, for which sequences
u the labeled tree has at
most O(n) vertices. In both models, we answer
this question for any forbidden sequence u over a two-element alphabet and also
for a large class of other sequences u.* This research was partially supported by Charles
University grants No. 99/158 and 99/159 and by Czech Republic
Grant GAR 201/99/0242. Supported by project LN00A056 of The Ministry of
Education of the Czech Republic. 相似文献
18.
For a string A=a1…an, a reversalρ(i,j), 1?i?j?n, transforms the string A into a string A′=a1…ai-1ajaj-1…aiaj+1…an, that is, the reversal ρ(i,j) reverses the order of symbols in the substring ai…aj of A. In the case of signed strings, where each symbol is given a sign + or -, the reversal operation also flips the sign of each symbol in the reversed substring. Given two strings, A and B, signed or unsigned, sorting by reversals (SBR) is the problem of finding the minimum number of reversals that transform the string A into the string B.Traditionally, the problem was studied for permutations, that is, for strings in which every symbol appears exactly once. We consider a generalization of the problem, k-SBR, and allow each symbol to appear at most k times in each string, for some k?1. The main result of the paper is an O(k2)-approximation algorithm running in time O(n). For instances with , this is the best known approximation algorithm for k-SBR and, moreover, it is faster than the previous best approximation algorithm. 相似文献
19.
A (0, 1)-matrix contains anS
0(k) if it has 0-cells (i, j
1), (i + 1,j
2),..., (i + k – 1,j
k) for somei andj
1 < ... < jk, and it contains anS
1(k) if it has 1-cells (i
1,j), (i
2,j + 1),...,(i
k
,j + k – 1) for somej andi
1 < ... <i
k
. We prove that ifM is anm × n rectangular (0, 1)-matrix with 1 m n whose largestk for anS
0(k) isk
0 m, thenM must have anS
1(k) withk m/(k
0 + 1). Similarly, ifM is anm × m lower-triangular matrix whose largestk for anS
0(k) (in the cells on or below the main diagonal) isk
0 m, thenM has anS
1(k) withk m/(k
0 + 1). Moreover, these results are best-possible. 相似文献
20.
Kwan-Hung Ho 《Journal of Number Theory》2006,120(1):33-46
Let k?2 and ai,bi(1?i?k) be integers such that ai>0 and ∏1?i<j?k(aibj−ajbi)≠0. Let Ω(m) denote the total number of prime factors of m. Suppose has no fixed prime divisors. Results of the form where rk is asymptotic to klogk have been obtained by using sieve methods, in particular weighted sieves. In this paper, we use another kind of weighted sieve due to Selberg to obtain improved admissible values for rk. 相似文献