On locally balanced gray codes

We consider locally balanced Gray codes.We say that a Gray code is locally balanced if every “short” subword in its transition sequence contains all letters of the alphabet |1, 2,..., n~. The minimal length of these subwords is the window width of the code. We show that for each n ≥ 3 there exists a Gray code with window width at most n + 3?log n?.     

Distance domination of generalized de Bruijn and Kautz digraphs

Let G = (V,A) be a digraph and k ≥ 1 an integer. For u, v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γ _k (G), is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs G _B (n, d) and generalized Kautz digraphs G _K (n, d) are good candidates for interconnection networks. Denote Δ _k := (∑ _j=0 ^k d ^j )^?1. F. Tian and J. Xu showed that ?nΔ _k ? γ _k (G _B (n, d)) ≤?n/d ^k? and ?nΔ _k ? ≤ γ _k (G _K (n, d)) ≤ ?n/d ^k ?. In this paper, we prove that every generalized de Bruijn digraph G _B (n, d) has the distance k-domination number ?nΔ _k ? or ?nΔ _k ?+1, and the distance k-domination number of every generalized Kautz digraph G _K (n, d) bounded above by ?n/(d ^k?1+d ^k )?. Additionally, we present various sufficient conditions for γ _k (G _B (n, d)) = ?nΔ _k ? and γ _k (G _K (n, d)) = ?nΔ _k ?.     

Euclidean and Hermitian LCD MDS codes

Linear codes with complementary duals (abbreviated LCD) are linear codes whose intersection with their dual is trivial. When they are binary, they play an important role in armoring implementations against side-channel attacks and fault injection attacks. Non-binary LCD codes in characteristic 2 can be transformed into binary LCD codes by expansion. On the other hand, being optimal codes, maximum distance separable codes (abbreviated MDS) are of much interest from many viewpoints due to their theoretical and practical properties. However, little work has been done on LCD MDS codes. In particular, determining the existence of q-ary [n, k] LCD MDS codes for various lengths n and dimensions k is a basic and interesting problem. In this paper, we firstly study the problem of the existence of q-ary [n, k] LCD MDS codes and solve it for the Euclidean case. More specifically, we show that for \(q>3\) there exists a q-ary [n, k] Euclidean LCD MDS code, where \(0\le k \le n\le q+1\), or, \(q=2^{m}\), \(n=q+2\) and \(k= 3 \text { or } q-1\). Secondly, we investigate several constructions of new Euclidean and Hermitian LCD MDS codes. Our main techniques in constructing Euclidean and Hermitian LCD MDS codes use some linear codes with small dimension or codimension, self-orthogonal codes and generalized Reed-Solomon codes.     

An upper bound for the number of uniformly packed binary codes

Under study are the binary codes uniformly packed (in the wide sense) of length n with minimum distance d and covering radius ρ. It is shown that every code of this kind is uniquely determined by the set of its codewords of weights ?n/2? ? ρ, …, ?n/2? + ρ. For odd d, the number of distinct codes is at most

$2^{2^{n - \tfrac{3}{2}\log n + o(log n)} } $

.

     

Symmetric LDPC codes and local testing

Coding theoretic and complexity theoretic considerations naturally lead to the question of generating symmetric, sparse, redundant linear systems. This paper provides a new way of construction with better parameters and new lower bounds.Low Density Parity Check (LDPC) codes are linear codes defined by short constraints (a property essential for local testing of a code). Some of the best (theoretically and practically) used codes are LDPC. Symmetric codes are those in which all coordinates “look the same,” namely there is some transitive group acting on the coordinates which preserves the code. Some of the most commonly used locally testable codes (especially in PCPs and other proof systems), including all “low-degree” codes, are symmetric. Requiring that a symmetric binary code of length n has large (linear or near-linear) distance seems to suggest a “con ict” between 1/rate and density (constraint length). In known constructions, if one is constant, then the other is almost the worst possible - n/poly(logn).Our main positive result simultaneously achieves symmetric low density, constant rate codes generated by a single constraint. We present an explicit construction of a symmetric and transitive binary code of length n, near-linear distance n/(log logn)², of constant rate and with constraints of length (logn)⁴. The construction is in the spirit of Tanner codes, namely the codewords are indexed by the edges of a sparse regular expander graph. The main novelty is in our construction of a transitive (non Abelian!) group acting on these edges which preserves the code. Our construction is one instantiation of a framework we call Cayley Codes developed here, that may be viewed as extending zig-zag product to symmetric codes.Our main negative result is that the parameters obtained above cannot be significantly improved, as long as the acting group is solvable (like the one we use). More specifically, we show that in constant rate and linear distance codes (aka “good” codes) invariant under solvable groups, the density (length of generating constraints) cannot go down to a constant, and is bounded below by (log^(Ω(?)) n)(an Ω(?) iterated logarithm) if the group has a derived series of length ?. This negative result precludes natural local tests with constantly many queries for such solvable “good” codes.     

Some results on linear codes over the ring $$\mathbb {Z}_4+u\mathbb {Z}_4+v\mathbb {Z}_4+uv\mathbb {Z}_4$$

In this paper, we mainly study the theory of linear codes over the ring \(R =\mathbb {Z}_4+u\mathbb {Z}_4+v\mathbb {Z}_4+uv\mathbb {Z}_4\). By using the Chinese Remainder Theorem, we prove that R is isomorphic to a direct sum of four rings. We define a Gray map \(\Phi \) from \(R^{n}\) to \(\mathbb {Z}_4^{4n}\), which is a distance preserving map. The Gray image of a cyclic code over R is a linear code over \(\mathbb {Z}_4\). We also discuss some properties of MDS codes over R. Furthermore, we study the MacWilliams identities of linear codes over R and give the generator polynomials of cyclic codes over R.     

Some variations on Tverberg’s theorem

Define T(d, r) = (d + 1)(r - 1) + 1. A well known theorem of Tverberg states that if n ≥ T(d, r), then one can partition any set of n points in R^d into r pairwise disjoint subsets whose convex hulls have a common point. The numbers T(d, r) are known as Tverberg numbers. Reay added another parameter k (2 ≤ k ≤ r) and asked: what is the smallest number n, such that every set of n points in R^d admits an r-partition, in such a way that each k of the convex hulls of the r parts meet. Call this number T(d, r, k). Reay conjectured that T(d, r, k) = T(d, r) for all d, r and k. In this paper we prove Reay’s conjecture in the following cases: when k ≥ [d+3/2], and also when d < rk/r-k - 1. The conjecture also holds for the specific values d = 3, r = 4, k = 2 and d = 5, r = 3, k = 2.     

Multiset combinatorial batch codes

Batch codes, first introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai, mimic a distributed storage of a set of n data items on m servers, in such a way that any batch of k data items can be retrieved by reading at most some t symbols from each server. Combinatorial batch codes, are replication-based batch codes in which each server stores a subset of the data items. In this paper, we propose a generalization of combinatorial batch codes, called multiset combinatorial batch codes (MCBC), in which n data items are stored in m servers, such that any multiset request of k items, where any item is requested at most r times, can be retrieved by reading at most t items from each server. The setup of this new family of codes is motivated by recent work on codes which enable high availability and parallel reads in distributed storage systems. The main problem under this paradigm is to minimize the number of items stored in the servers, given the values of n, m, k, r, t, which is denoted by N(n, k, m, t; r). We first give a necessary and sufficient condition for the existence of MCBCs. Then, we present several bounds on N(n, k, m, t; r) and constructions of MCBCs. In particular, we determine the value of N(n, k, m, 1; r) for any \(n\ge \left\lfloor \frac{k-1}{r}\right\rfloor {m\atopwithdelims ()k-1}-(m-k+1)A(m,4,k-2)\), where \(A(m,4,k-2)\) is the maximum size of a binary constant weight code of length m, distance four and weight \(k-2\). We also determine the exact value of N(n, k, m, 1; r) when \(r\in \{k,k-1\}\) or \(k=m\).     

On Trees of Bounded Degree with Maximal Number of Greatest Independent Sets

Given n and d, we describe the structure of trees with the maximal possible number of greatest independent sets in the class of n-vertex trees of vertex degree at most d.We show that the extremal tree is unique for all even n but uniqueness may fail for odd n; moreover, for d = 3 and every odd n ≥ 7, there are exactly ?(n ? 3)/4? + 1 extremal trees. In the paper, the problem of searching for extremal (n, d)-trees is also considered for the 2-caterpillars; i.e., the trees in which every vertex lies at distance at most 2 from some simple path. Given n and d ∈ {3, 4}, we completely reveal all extremal 2-caterpillars on n vertices each of which has degree at most d.     

On Ranks of Polynomials

Let V be a vector space over a field k, P : V → k, d ≥?3. We show the existence of a function C(r, d) such that rank(P) ≤ C(r, d) for any field k, char(k) > d, a finite-dimensional k-vector space V and a polynomial P : V → k of degree d such that rank(?P/?t) ≤ r for all t ∈ V ??0. Our proof of this theorem is based on the application of results on Gowers norms for finite fields k. We don’t know a direct proof even in the case when k = ?.     

An approximation scheme for a problem of search for a vector subset

We consider the following clustering problem: Given a vector set, find a subset of cardinality k and minimum square deviation from its mean. The distance between the vectors is defined by the Euclideanmetric. We present an approximation scheme (PTAS) that allows us to solve this problem with an arbitrary relative error ? in time O(n ^2/?+1(9/?)^3/? d), where n is the number of vectors of the input set and d denotes the dimension of the space.     

Depth and Stanley depth of the facet ideals of some classes of simplicial complexes

Let Δ _n,d (resp. Δ′ _n,d ) be the simplicial complex and the facet ideal I _n,d = (x ₁... x _d, x d?k+1... x _2d?k ,..., x _n?d+1... x _n ) (resp. J _n,d = (x ₁... x _d , x _d?k+1... x _2d?k ,..., x n?2d+2k+1... x _n?d+2k , x n?d+k+1... x n x ₁... x _k)). When d ≥ 2k + 1, we give the exact formulas to compute the depth and Stanley depth of quotient rings S/J _n,d and S/I _n,d ^t for all t ≥ 1. When d = 2k, we compute the depth and Stanley depth of quotient rings S/Jn,d and S/I _n,d , and give lower bounds for the depth and Stanley depth of quotient rings S/I _n,d ^t for all t ≥ 1.     

The program iteration method in a game problem of guidance

Let a sequence of d-dimensional vectors n _k = (n _k ¹ , n _k ² ,..., n _k ^d ) with positive integer coordinates satisfy the condition n _k ^j = α _j m _k +O(1), k ∈ ?, 1 ≤ j ≤ d, where α ₁ > 0,..., α _d > 0 and {m _k } _k=1 ^∞ is an increasing sequence of positive integers. Under some conditions on a function φ: [0,+∞) → [0,+∞), it is proved that, if the sequence of Fourier sums \({S_{{m_k}}}\) (g, x) converges almost everywhere for any function g ∈ φ(L)([0, 2π)), then, for any d ∈ ? and f ∈ φ(L)(ln⁺ L) ^d?1([0, 2π) ^d ), the sequence \({S_{{n_k}}}\) (f, x) of rectangular partial sums of the multiple trigonometric Fourier series of the function f and the corresponding sequences of partial sums of all conjugate series converge almost everywhere.     

Semidefinite bounds for nonbinary codes based on quadruples

For nonnegative integers q, n, d, let \(A_q(n,d)\) denote the maximum cardinality of a code of length n over an alphabet [q] with q letters and with minimum distance at least d. We consider the following upper bound on \(A_q(n,d)\). For any k, let \(\mathcal{C}_k\) be the collection of codes of cardinality at most k. Then \(A_q(n,d)\) is at most the maximum value of \(\sum _{v\in [q]^n}x(\{v\})\), where x is a function \(\mathcal{C}_4\rightarrow {\mathbb {R}}_+\) such that \(x(\emptyset )=1\) and \(x(C)=\!0\) if C has minimum distance less than d, and such that the \(\mathcal{C}_2\times \mathcal{C}_2\) matrix \((x(C\cup C'))_{C,C'\in \mathcal{C}_2}\) is positive semidefinite. By the symmetry of the problem, we can apply representation theory to reduce the problem to a semidefinite programming problem with order bounded by a polynomial in n. It yields the new upper bounds \(A_4(6,3)\le 176\), \(A_4(7,3)\le 596\), \(A_4(7,4)\le 155\), \(A_5(7,4)\le 489\), and \(A_5(7,5)\le 87\).     

Disjoint cliques in claw-free graphs

A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K_1,3. Let s and k be two integers with 0 ≤ s ≤ k and let G be a claw-free graph of order n. In this paper, we investigate clique partition problems in claw-free graphs. It is proved that if n ≥ 3s+4(k?s) and d(x)+d(y) ≥ n?2s+2k+1 for any pair of non-adjacent vertices x, y of G, then G contains s disjoint K₃s and k ? s disjoint K₄s such that all of them are disjoint. Moreover, the degree condition is sharp in some cases.     

New bounds of permutation codes under Hamming metric and Kendall’s $$\tau $$-metric

Permutation codes are widely studied objects due to their numerous applications in various areas, such as power line communications, block ciphers, and the rank modulation scheme for flash memories. Several kinds of metrics are considered for permutation codes according to their specific applications. This paper concerns some improvements on the bounds of permutation codes under Hamming metric and Kendall’s \(\tau \)-metric respectively, using mainly a graph coloring approach. Specifically, under Hamming metric, we improve the Gilbert–Varshamov bound asymptotically by a factor n, when the minimum Hamming distance d is fixed and the code length n goes to infinity. Under Kendall’s \(\tau \)-metric, we narrow the gap between the known lower bounds and upper bounds. Besides, we also obtain some sporadic results under Kendall’s \(\tau \)-metric for small parameters.     

Degree sequences and edge connectivity

For each positive integer k, we give a finite list C(k) of Bondy–Chvátal type conditions on a nondecreasing sequence \(d=(d_1,\dots ,d_n)\) of nonnegative integers such that every graph on n vertices with degree sequence at least d is k-edge-connected. These conditions are best possible in the sense that whenever one of them fails for d then there is a graph on n vertices with degree sequence at least d which is not k-edge-connected. We prove that C(k) is and must be large by showing that it contains p(k) many logically irredundant conditions, where p(k) is the number of partitions of k. Since, in the corresponding classic result on vertex connectivity, one needs just one such condition, this is one of the rare statements where the edge connectivity version is much more difficult than the vertex connectivity version. Furthermore, we demonstrate how to handle other types of edge-connectivity, such as, for example, essential k-edge-connectivity. We prove that any sublist equivalent to C(k) has length at least p(k), where p(k) is the number of partitions of k, which is in contrast to the corresponding classic result on vertex connectivity where one needs just one such condition. Furthermore, we demonstrate how to handle other types of edge-connectivity, such as, for example, essential k-edge-connectivity. Finally, we informally describe a simple and fast procedure which generates the list C(k). Specialized to \(k=3\), this verifies a conjecture of Bauer, Hakimi, Kahl, and Schmeichel, and for \(k=2\) we obtain an alternative proof for their result on bridgeless connected graphs. The explicit list for \(k=4\) is given, too.     

Bent functions with stronger nonlinear properties: K-bent functions

We introduce the notion of k-bent function, i.e., a Boolean functionwith evennumber m of variables υ ₁, …, υ _m which can be approximated with all functions of the form 〈u, v〉 _j ⊕ a in the equally poor manner, where u ∈ ? ₂ ^m , a ∈ ?₂, and 1 ? j ? k. Here 〈·, ·〉 _j is an analog of the inner product of vectors; k changes from 1 to m/2. The operations 〈·, ·〉 _k , 1 ? k ? m/2, are defined by using the special series of binary Hadamard-like codes A _m ^k of length 2 ^m . Namely, the vectors of values for the functions 〈u, v〉 _k ⊕ a are codewords of the code A _m ^k . The codes A _m ^k are constructed using subcodes of the ?₄-linear Hadamard-like codes of length 2 ^m+1, which were classified by D. S. Krotov (2001). At that the code A _m ¹ is linear and A _m ¹ , …, A _m ^m/2 are pairwise nonequivalent. On the codewords of a code A _m ^k , we define a group operation ? coordinated with the Hamming metric. That is why we can consider k-bent functions as functions that are maximal nonlinear in k distinct senses of linearity at the same time. Bent functions in usual sense coincide with 1-bent functions. For k > ? ? 1, the class of k-bent functions is a proper subclass of the class of ?-bent functions. In the paper, we give methods for constructing k-bent functions and study their properties. It is shown that there exist k-bent functions with an arbitrary algebraic degree d, where 2 ? d ? max {2, m/2 ? k + 1}. Given an arbitrary k, we define the subset \(\mathfrak{F}_m^k \mathcal{F}_m^k \) of the set \(\mathfrak{F}_m^k \mathcal{F}_m^k \) \(\mathcal{A}_m^k \mathcal{B}_m^k \) of all Boolean functions in m variables with the following property: on this subset k-bent functions and 1-bent functions coincide.     

On critical exponents of Dowling matroids

The critical problem in matroid theory is the problem to determine the critical exponent of a given representable matroid over a finite field. In this paper, we study the critical exponents of a class of representable matroids over finite fields, called Dowling matroids. Then the critical problem for a Dowling matroid is corresponding to the classical problem in coding theory to determine the maximum dimension k such that there exists an \([n,k,d]_q\) code for given n, d and q. We give a necessary and sufficient condition on the critical exponents of Dowling matroids by using a coding theoretical approach.     

Deviation of elements of a Banach space from a system of subspaces

We prove that if X is a real Banach space, Y ₁ ? Y ₂ ? ... is a sequence of strictly embedded closed linear subspaces of X, and d ₁ ≥ d ₂ ≥ ... is a nonincreasing sequence converging to zero, then there exists an element x ∈ X such that the distance ρ(x, Y _n ) from x to Y _n satisfies the inequalities d _n ≤ ρ(x, Y _n ) ≤ 8d _n for n = 1, 2, ....