Asymmetric Binary Covering Codes

An asymmetric binary covering code of length n and radius R is a subset of the n-cube Q_n such that every vector xQ_n can be obtained from some vector c by changing at most R 1's of c to 0's, where R is as small as possible. K⁺(n,R) is defined as the smallest size of such a code. We show K⁺(n,R)Θ(2ⁿ/n^R) for constant R, using an asymmetric sphere-covering bound and probabilistic methods. We show K⁺(n,n− )= +1 for constant coradius iff n ( +1)/2. These two results are extended to near-constant R and , respectively. Various bounds on K⁺ are given in terms of the total number of 0's or 1's in a minimal code. The dimension of a minimal asymmetric linear binary code ([n,R]⁺-code) is determined to be min{0,n−R}. We conclude by discussing open problems and techniques to compute explicit values for K⁺, giving a table of best-known bounds.     

Optimal holey packings OHP4(2, 4, n ,3)'s

An optimal holey packing OHP_d(2, k, n, g) is equivalent to a maximal (g + 1)‐ary (n, k, d) constant weight code. In this paper, we provide some recursive constructions for OHP_d(2, k, n, g)'s and use them to investigate the existence of an OHP₄(2, 4, n, 3) for n ≡ 2, 3 (mod 4). Combining this with Wu's result ( 18 ), we prove that the necessary condition for the existence of an OHP₄(2, 4, n, 3), namely, n ≥ 5 is also sufficient, except for n ∈ {6, 7} and except possibly for n = 26. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 111–123, 2006     

Cocycle Twisting of E(n)-Module Algebras and Applications to the Brauer Group

We classify the orbits of coquasi-triangular structures for the Hopf algebra E(n) under the action of lazy cocycles and the Hopf automorphism group. This is applied to detect subgroups of the Brauer group BQ(k,E(n)) of E(n) that are isomorphic. For any triangular structure R on E(n) we prove that the subgroup BM(k,E(n),R) of BQ(k,E(n)) arising from R is isomorphic to a direct product of BW(k), the Brauer-Wall group of the ground field k, and Sym_n(k), the group of n × n symmetric matrices under addition. For a general quasi-triangular structure R on E(n) we construct a split short exact sequence having BM(k,E(n),R⁾ as a middle term and as kernel a central extension of the group of symmetric matrices of order r < n (r depending on R). We finally describe how the image of the Hopf automorphism group inside BQ(k,E(n)) acts on Sym_n (k).     

Classifying Subspaces of Hamming Spaces

A linear code in F ⁿ _q with dimension k and minimum distance at least d is called an [n, k, d] _q code. We here consider the problem of classifying all [n, k, d] _q codes given n, k, d, and q. In other words, given the Hamming space F ⁿ _q and a dimension k, we classify all k-dimensional subspaces of the Hamming space with minimum distance at least d. Our classification is an iterative procedure where equivalent codes are identified by mapping the code equivalence problem into the graph isomorphism problem, which is solved using the program nauty. For d = 3, the classification is explicitly carried out for binary codes of length n 14, ternary codes of length n 11, and quaternary codes of length n 10.     

A result about determinantal divisors

Let Rbe a principal ideal ringR_n the ring of n× nmatrices over R, and d_k (A) the kth determinantal divisor of Afor 1 ? k? n, where Ais any element of R_n , It is shown that if A,BεR_n , det(A) det(B:) ≠ 0, then d_k (AB) ≡ 0 mod d_k (A) d_k (B). If in addition (det(A), det(B)) = 1, then it is also shown that d_k (AB) = d_k (A) d_k (B). This provides a new proof of the multiplicativity of the Smith normal form for matrices with relatively prime determinants.     

Bounds for Covering Codes over Large Alphabets

Let K_q(n,R) denote the minimum number of codewords in any q-ary code of length n and covering radius R. We collect lower and upper bounds for K_q(n,R) where 6 ≤ q ≤ 21 and R ≤ 3. For q ≤ 10, we consider lengths n ≤ 10, and for q ≥ 11, we consider n ≤ 8. This extends earlier results, which have been tabulated for 2 ≤ q ≤ 5. We survey known bounds and obtain some new results as well, also for s-surjective codes, which are closely related to covering codes and utilized in some of the constructions.AMS Classification: 94B75, 94B25, 94B65Gerzson Kéri - Supported in part by the Hungarian National Research Fund, Grant No. OTKA-T029572.Patric R. J. Östergård - Supported in part by the Academy of Finland, Grants No. 100500 and No. 202315.     

A constructive approach for the lower bounds on the Ramsey numbers R (s,t)

Graph G is a (k, p)‐graph if G does not contain a complete graph on k vertices K_k, nor an independent set of order p. Given a (k, p)‐graph G and a (k, q)‐graph H, such that G and H contain an induced subgraph isomorphic to some K_k?1‐free graph M, we construct a (k, p + q ? 1)‐graph on n(G) + n(H) + n(M) vertices. This implies that R (k, p + q ? 1) ≥ R (k, p) + R (k, q) + n(M) ? 1, where R (s, t) is the classical two‐color Ramsey number. By applying this construction, and some its generalizations, we improve on 22 lower bounds for R (s, t), for various specific values of s and t. In particular, we obtain the following new lower bounds: R (4, 15) ≥ 153, R (6, 7) ≥ 111, R (6, 11) ≥ 253, R (7, 12) ≥ 416, and R (8, 13) ≥ 635. Most of the results did not require any use of computer algorithms. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 231–239, 2004     

Optimal binary covering codes of length 2j

The minimum size of a binary covering code of length n and covering radius r is denoted by K(n,r), and codes of this length are called optimal. For j > 0 and n = 2^j, it is known that K(n,1) = 2 · K(n?1,1) = 2^{n ? j}. Say that two binary words of length n form a duo if the Hamming distance between them is 1 or 2. In this paper, it is shown that each optimal binary covering code of length n = 2^j, j > 0, and covering radius 1 is the union of duos in just one way, and that the closed neighborhoods of the duos form a tiling of the set of binary words of length n. Methods of constructing such optimal codes from optimal covering codes of length n ? 1 (that is, perfect single‐error‐correcting codes) are discussed. The paper ends with the construction of an optimal covering code of length 16 that does not contain an extension of any optimal covering code of length 15. © 2005 Wiley Periodicals, Inc. J Combin Designs     

On the minimum size of binary codes with length 2<Emphasis Type="Italic">R</Emphasis> + 4 and covering radius <Emphasis Type="Italic">R</Emphasis>

The minimum size of a binary code with length n and covering radius R is denoted by K(n, R). For arbitrary R, the value of K(n, R) is known when n ≤  2R +  3, and the corresponding optimal codes have been classified up to equivalence. By combining combinatorial and computational methods, several results for the first open case, K(2R +  4, R), are here obtained, including a proof that K(10, 3) =  12 with 11481 inequivalent optimal codes and a proof that if K(2R +  4, R) <  12 for some R then this inequality cannot be established by the existence of a corresponding self-complementary code.     

A Combinatorial Proof of the Log-Concavity of the Numbers of Permutations with k Runs

We combinatorially prove that the number R(n, k) of permutations of length n having k runs is a log-concave sequence in k, for all n. We also give a new combinatorial proof for the log-concavity of the Eulerian numbers.     

Asymptotic Determination of the Last Packing Number of Quadruples

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     

Binomial Coefficients and Zero-Sum Ramsey Numbers

A counting argument is developed and divisibility properties of the binomial coefficients are combined to prove, among other results, that[formula]whereK_n, resp.K^k_n, is the complete, resp. completek-uniform, hypergaph andR(K_n, Z_p),R(K^k_n, Z₂) are the corresponding zero-sum Ramsey numbers.     

On subgroups of the general linear group that contain a maximal nonsplit torus

The paper deals with the structure of intermediate subgroups of the general linear group GL(n, k) of degree n over a field k of odd characteristic that contain a nonsplit maximal torus related to a radical extension of degree n of the ground field k. The structure of ideal nets over a ring that determine the structure of intermediate subgroups containinga transvection is given. Let K = k( ⁿ?{d} ) K = k\left( {\sqrt[n]{d}} \right) be a radical degree-n extension of a field k of odd characteristic, and let T =(d) be a nonsplit maximal torus, which is the image of the multiplicative group of the field K under the regular embedding in G =GL(n, k). In the paper, the structure of intermediate subgroups H, T ≤ H ≤ G, that contain a transvection is studied. The elements of the matrices in the torus T = T (d) generate a subring R(d) in the field k.Let R be an intermediate subring, R(d) ⊆ R ⊆ k, d ∈ R. Let σ_R denote the net in which the ideal dR stands on the principal diagonal and above it and all entries of which beneath the principal diagonal are equal to R. Let σ^R denote the net in which all positions on the principal diagonal and beneath it are occupied by R and all entries above the principal diagonal are equal to dR. Let E(σ_R) be the subgroup generated by all transvections from the net group G(σ_R). In the paper it is proved that the product TE(σ_R) is a group (and thus an intermediate subgroup). If the net σ associated with an intermediate subgroup H coincides with σ_R,then TE(σ_R) ≤ H ≤ N(σ_R),where N(σ_R) is the normalizer of the elementary net group E(σ_R) in G. For the normalizer N(σ_R),the formula N(σ_R)= TG(σ^R) holds. In particular, this result enables one to describe the maximal intermediate subgroups. Bibliography: 13 titles.     

Concerning the order of approximation of periodic continuous functions by trigonometric interpolation polynomials

Letx _kn=2θk/n,k=0,1 …n−1 (n odd positive integer). LetR _n(x) be the unique trigonometric polynomial of order 2n satisfying the interpolatory conditions:R _n(x_kn)=f(x_kn),R _n ^(j)(x_kn)=0,j=1,2,4,k=0,1…,n−1. We setw ₂(t,f) as the second modulus of continuity off(x). Then we prove that |R _n(x)-f(x)|=0(nw₂(1/nf)). We also examine the question of lower estimate of ‖R _n-f‖. This generalizes an earlier work of the author.     

A note on properties of locally finitely convergent sequences with respect to median filter

Let F_k be a mapping from R^Z to R^Z, satisfying that for x∈R^Z and n∈Z, F_k(x)(n) is the (k+1)th largest value (median value) of the 2k+1 numbers x(n−k),…,x(n),…,x(n+k). In [3] [W.Z. Ye, L. Wang, L.G. Xu, Properties of locally convergent sequences with respect to median filter, Discrete Mathematics 309 (2009) 2775–2781], we conjectured that for k∈{2,3}, if there exists n₀∈Z such that x is locally finitely convergent with respect to F_k on {n₀,…,n₀+k−1}, then x is finitely convergent with respect to F_k. In this paper, we obtain some sufficient conditions for a sequence finitely converging with respect to median filters. Based on these results, we prove that the conjecture is true.     

Gray code enumeration of families of integer partitions

In this paper we show that the elements of certain families of integer partitions can be listed in a minimal change, or Gray code, order. In particular, we construct Gray code listings for the classes P_δ(n, k) and D(n, k) of partitions of n into parts of size at most k in which, for P_δ(n, k), the parts are congruent to one modulo δ and, for D(n, k), the parts are distinct. It is shown that the elements of these classes can be listed so that the only change between successive partitions is the increase of one part by δ (or the addition of δ ones) and the decrease of one part by δ (or the removal of δ ones), where, in the case of D(n, k), δ = 1.     

A reversal index for tournament matrices *

Given a tournament matrix T, its reversal indexi_R (T), is the minimum k such that the reversal of the orientation of k arcs in the directed graph associated with T results in a reducible matrix. We give a formula for i_R (T) in terms of the score vector of T which generalizes a simple criterion for a tournament matrix to be irreducible. We show that i_R (T)≤[(n?1)/2] for any tournament matrix T of order n, with equality holding if and only if T is regular or almost regular, according as n is odd or even. We construct, for each k between 1 and [(n?1)/2], a tournament matrix of order n whose reversal index is k. Finally, we suggest a few problems.     

Intersection of Isomorphic Linear Codes

Given an (n, k) linear code over GF(q), the intersection of with a codeπ( ), whereπS_n, is an (n, k₁) code, where max{0, 2k−n}k₁k. The intersection problem is to determine which integers in this range are attainable for a given code . We show that, depending on the structure of the generator matrix of the code, some of the values in this range are attainable. As a consequence we give a complete solution to the intersection problem for most of the interesting linear codes, e.g. cyclic codes, Reed–Muller codes, and most MDS codes.     

Bichromatic and Equichromatic Lines in ℂ2 and ℝ2

Let G and R each be a finite set of green and red points, respectively, such that |G|=n, |R|=n−k, G∩R=∅, and the points of G∪R are not all collinear. Let t be the total number of lines determined by G∪R. The number of equichromatic lines (a subset of bichromatic) is at least (t+2n+3−k(k+1))/4. A slightly weaker lower bound exists for bichromatic lines determined by points in ℂ². For sufficiently large point sets, a proof of a conjecture by Kleitman and Pinchasi is provided. A lower bound of (2t+14n−k(3k+7))/14 is demonstrated for bichromatic lines passing through at most six points. Lower bounds are also established for equichromatic lines passing through at most four, five, or six points.