On resol vability of Steine r systems S( v = 2m, 4, 3) of rank r ≤ v − m + 1 o ve r $$\mathbb{F}_2 $$

Two new constructions of Steiner quadruple systems S(v, 4, 3) are given. Both preserve resolvability of the original Steiner system and make it possible to control the rank of the resulting system. It is proved that any Steiner system S(v = 2 ^m , 4, 3) of rank r ≤ v ? m + 1 over F₂ is resolvable and that all systems of this rank can be constructed in this way. Thus, we find the number of all different Steiner systems of rank r = v ? m + 1.     

Vasil’ev codes of length n = 2m and doubling of Steiner systems S(n, 4, 3) of a given rank

Extended binary perfect nonlinear Vasil’ev codes of length n = 2^m and Steiner systems S(n, 4, 3) of rank n-m over F ₂ are studied. The generalized concatenated construction of Vasil’ev codes induces a variant of the doubling construction for Steiner systems S(n, 4, 3) of an arbitrary rank r over F ₂. We prove that any Steiner system S(n = 2^m, 4, 3) of rank n-m can be obtained by this doubling construction and is formed by codewords of weight 4 of these Vasil’ev codes. The length 16 is studied in detail. Orders of the full automorphism groups of all 12 nonequivalent Vasil’ev codes of length 16 are found. There are exactly 15 nonisomorphic systems S(16, 4, 3) of rank 12 over F ₂, and they can be obtained from codewords of weight 4 of the extended Vasil’ev codes. Orders of the automorphism groups of all these Steiner systems are found.     

Tilings of nonorientable surfaces by Steiner triple systems

A Steiner triple system of order n (for short, STS(n)) is a system of three-element blocks (triples) of elements of an n-set such that each unordered pair of elements occurs in precisely one triple. Assign to each triple (i,j,k) ? STS(n) a topological triangle with vertices i, j, and k. Gluing together like sides of the triangles that correspond to a pair of disjoint STS(n) of a special form yields a black-and-white tiling of some closed surface. For each n ≡ 3 (mod 6) we prove that there exist nonisomorphic tilings of nonorientable surfaces by pairs of Steiner triple systems of order n. We also show that for half of the values n ≡ 1 (mod 6) there are nonisomorphic tilings of nonorientable closed surfaces.     

On weak isometries of Preparata codes

Two codes C ₁ and C ₂ are said to be weakly isometric if there exists a mapping J: C ₁ → C ₂ such that for all x, y in C ₁ the equality d(x, y) = d holds if and only if d(J(x), J(y)) = d, where d is the code distance of C ₁. We prove that Preparata codes of length n ≥ 2¹² are weakly isometric if and only if the codes are equivalent. A similar result is proved for punctured Preparata codes of length at least 2¹⁰ ? 1.     

MDS codes in Doob graphs

The Doob graph D(m, n), where m > 0, is a Cartesian product of m copies of the Shrikhande graph and n copies of the complete graph K ₄ on four vertices. The Doob graph D(m, n) is a distance-regular graph with the same parameters as the Hamming graph H(2m + n, 4). We give a characterization of MDS codes in Doob graphs D(m, n) with code distance at least 3. Up to equivalence, there are m ³/36+7m ²/24+11m/12+1?(m mod 2)/8?(m mod 3)/9 MDS codes with code distance 2m + n in D(m, n), two codes with distance 3 in each of D(2, 0) and D(2, 1) and with distance 4 in D(2, 1), and one code with distance 3 in each of D(1, 2) and D(1, 3) and with distance 4 in each of D(1, 3) and D(2, 2).     

Propelinear codes related to some classes of optimal codes

A code is said to be propelinear if its automorphism group contains a subgroup that acts regularly on codewords. We show propelinearity of complements of cyclic codes C _1,i , (i, 2 ^m ? 1) = 1, of length n = 2 ^m ? 1, including the primitive two-error-correcting BCH code, to the Hamming code; the Preparata code to the Hamming code; the Goethals code to the Preparata code; and the Z₄-linear Preparata code to the Z₄-linear perfect code.     

On transitive partitions of an <Emphasis Type="Italic">n</Emphasis>-cube into codes

We present methods to construct transitive partitions of the set E ⁿ of all binary vectors of length n into codes. In particular, we show that for all n = 2 ^k ? 1, k ≥ 3, there exist transitive partitions of E ⁿ into perfect transitive codes of length n.     

Conflict-avoiding codes and cyclic triple systems

The paper deals with the problem of constructing a code of the maximum possible cardinality consisting of binary vectors of length n and Hamming weight 3 and having the following property: any 3 × n matrix whose rows are cyclic shifts of three different code vectors contains a 3 × 3 permutation matrix as a submatrix. This property (in the special case w = 3) characterizes conflict-avoiding codes of length n for w active users, introduced in [1]. Using such codes in channels with asynchronous multiple access allows each of w active users to transmit a data packet successfully in one of w attempts during n time slots without collisions with other active users. An upper bound on the maximum cardinality of a conflict-avoiding code of length n with w = 3 is proved, and constructions of optimal codes achieving this bound are given. In particular, there are found conflict-avoiding codes for w = 3 which have much more vectors than codes of the same length obtained from cyclic Steiner triple systems by choosing a representative in each cyclic class.     

On the symmetry group of the Mollard code

We study the symmetry group of a binary perfect Mollard code M(C,D) of length tm + t + m containing as its subcodes the codes C ¹ and D ² formed from perfect codes C and D of lengths t and m, respectively, by adding an appropriate number of zeros. For the Mollard codes, we generalize the result obtained in [1] for the symmetry group of Vasil’ev codes; namely, we describe the stabilizer

$$Sta{b_{{D^2}}}$$

Sym(M(C,D)) of the subcode D ² in the symmetry group of the code M(C,D) (with the trivial function). Thus we obtain a new lower bound on the order of the symmetry group of the Mollard code. A similar result is established for the automorphism group of Steiner triple systems obtained by the Mollard construction but not necessarily associated with perfect codes. To obtain this result, we essentially use the notions of “linearity” of coordinate positions (points) of a nonlinear perfect code and a nonprojective Steiner triple system.

     

The Outer-connected Domination Number of Sierpiński-like Graphs

An outer-connected dominating set in a graph G = (V, E) is a set of vertices D ? V satisfying the condition that, for each vertex v ? D, vertex v is adjacent to some vertex in D and the subgraph induced by V?D is connected. The outer-connected dominating set problem is to find an outer-connected dominating set with the minimum number of vertices which is denoted by \(\tilde {\gamma }_{c}(G)\). In this paper, we determine \(\tilde {\gamma }_{c}(S(n,k))\), \(\tilde {\gamma }_{c}(S^{+}(n,k))\), \(\tilde {\gamma }_{c}(S^{++}(n,k))\), and \(\tilde {\gamma }_{c}(S_{n})\), where S(n, k), S ⁺(n, k), S ⁺⁺(n, k), and S _n are Sierpi\(\acute {\mathrm {n}}\)ski-like graphs.     

Construction of quantum caps in projective space <Emphasis Type="Italic">PG</Emphasis>(<Emphasis Type="Italic">r</Emphasis>, 4) and quantum codes of distance 4

Constructions of quantum caps in projective space PG(r, 4) by recursive methods and computer search are discussed. For each even n satisfying \(n\ge 282\) and each odd z satisfying \(z\ge 275\), a quantum n-cap and a quantum z-cap in \(PG(k-1, 4)\) with suitable k are constructed, and \([[n,n-2k,4]]\) and \([[z,z-2k,4]]\) quantum codes are derived from the constructed quantum n-cap and z-cap, respectively. For \(n\ge 282\) and \(n\ne 286\), 756 and 5040, or \(z\ge 275\), the results on the sizes of quantum caps and quantum codes are new, and all the obtained quantum codes are optimal codes according to the quantum Hamming bound. While constructing quantum caps, we also obtain many large caps in PG(r, 4) for \(r\ge 11\). These results concerning large caps provide improved lower bounds on the maximal sizes of caps in PG(r, 4) for \(r\ge 11\).     

List decoding of the first-order binary Reed-Muller codes

A list decoding algorithm is designed for the first-order binary Reed-Muller codes of length n that reconstructs all codewords located within the ball of radius n/2(1 ? ?) about the received vector and has the complexity of O(n ln²(min{? ^?2, n})) binary operations.     

On Fixed Cost k-Flow Problems

In the Fixed Cost k-Flow problem, we are given a graph G = (V, E) with edge-capacities {u _e ∣e ∈ E} and edge-costs {c _e ∣e ∈ E}, source-sink pair s, t ∈ V, and an integer k. The goal is to find a minimum cost subgraph H of G such that the minimum capacity of an st-cut in H is at least k. By an approximation-preserving reduction from Group Steiner Tree problem to Fixed Cost k-Flow, we obtain the first polylogarithmic lower bound for the problem; this also implies the first non-constant lower bounds for the Capacitated Steiner Network and Capacitated Multicommodity Flow problems. We then consider two special cases of Fixed Cost k-Flow. In the Bipartite Fixed-Cost k-Flow problem, we are given a bipartite graph G = (A ∪ B, E) and an integer k > 0. The goal is to find a node subset S ? A ∪ B of minimum size |S| such G has k pairwise edge-disjoint paths between S ∩ A and S ∩ B. We give an \(O(\sqrt {k\log k})\) approximation for this problem. We also show that we can compute a solution of optimum size with Ω(k/polylog(n)) paths, where n = |A| + |B|. In the Generalized-P2P problem we are given an undirected graph G = (V, E) with edge-costs and integer charges {b _v : v ∈ V}. The goal is to find a minimum-cost spanning subgraph H of G such that every connected component of H has non-negative charge. This problem originated in a practical project for shift design [11]. Besides that, it generalizes many problems such as Steiner Forest, k-Steiner Tree, and Point to Point Connection. We give a logarithmic approximation algorithm for this problem. Finally, we consider a related problem called Connected Rent or Buy Multicommodity Flow and give a log^3+?? n approximation scheme for it using Group Steiner Tree techniques.     

Polar Codes with Higher-Order Memory

We introduce a construction of a set of code sequences {C_n^(m) : n ≥ 1, m ≥ 1} with memory order m and code length N(n). {C_n^(m)} is a generalization of polar codes presented by Ar?kan in [1], where the encoder mapping with length N(n) is obtained recursively from the encoder mappings with lengths N(n ? 1) and N(n ? m), and {C_n^(m)} coincides with the original polar codes when m = 1. We show that {C_n^(m)} achieves the symmetric capacity I(W) of an arbitrary binary-input, discrete-output memoryless channel W for any fixed m. We also obtain an upper bound on the probability of block-decoding error P_e of {C_n^(m)} and show that \({P_e} = O({2^{ - {N^\beta }}})\) is achievable for β < 1/[1+m(? ? 1)], where ? ∈ (1, 2] is the largest real root of the polynomial F(m, ρ) = ρ^m ? ρ^{m ? 1} ? 1. The encoding and decoding complexities of {C_n^(m)} decrease with increasing m, which proves the existence of new polar coding schemes that have lower complexity than Ar?kan’s construction.     

A novel weighting scheme for random k-SAT关于随机 k-SAT 的新加权方法

Consider a random k-conjunctive normal form F_k(n, rn) with n variables and rn clauses. We prove that if the probability that the formula F_k(n, rn) is satisfiable tends to 0 as n→∞, then r ? 2.83, 8.09, 18.91, 40.81, and 84.87, for k = 3, 4, 5, 6, and 7, respectively.     

On <Emphasis Type="Italic">m</Emphasis>-Near-Resolvable Block Designs and <Emphasis Type="Italic">q</Emphasis>-ary Constant-Weight Codes

We introduce m-near-resolvable block designs. We establish a correspondence between such block designs and a subclass of (optimal equidistant) q-ary constant-weight codes meeting the Johnson bound. We present constructions of m-near-resolvable block designs, in particular based on Steiner systems and super-simple t-designs.     

Independence Numbers of Random Subgraphs of Some Distance Graph

The distance graph G(n, 2, 1) is a graph where vertices are identified with twoelement subsets of {1, 2,..., n}, and two vertices are connected by an edge whenever the corresponding subsets have exactly one common element. A random subgraph G _p (n, 2, 1) in the Erd?os–Rényi model is obtained by selecting each edge of G(n, 2, 1) with probability p independently of other edges. We find a lower bound on the independence number of the random subgraph G_1/2(n, 2, 1).     

Clique Numbers of Random Subgraphs of Some Distance Graphs

We consider a class of graphs G(n, r, s) = (V (n, r),E(n, r, s)) defined as follows:

$$V(n,r) = \{ x = ({x_{1,}},{x_2}...{x_n}):{x_i} \in \{ 0,1\} ,{x_{1,}} + {x_2} + ... + {x_n} = r\} ,E(n,r,s) = \{ \{ x,y\} :(x,y) = s\} $$

where (x, y) is the Euclidean scalar product. We study random subgraphs G(G(n, r, s), p) with edges independently chosen from the set E(n, r, s) with probability p each. We find nontrivial lower and upper bounds on the clique number of such graphs.

     

Complexity of ideals in finite semigroups and finite-state machines

# _G (S) denotes the complexity of a finite semigroup as introduced by Krohn and Rhodes. IfI is a maximal ideal or maximal left ideal of a semigroupS, then# _G (I) ? # _G (S) ? # _G (I) + 1. Thus, ifV is an ideal ofS with# _G (S) = n ? k = # _G (V), then there is a chain of ideals ofS

$$V = V_k \subset V_{k + 1} \subset ... \subset V_n \subseteq S$$     

The pursuit-evasion game on the 1-skeleton graph of a regular polyhedron. I

We consider a game between a group of n pursuers and one evader moving with the same maximum velocity along the 1-skeleton graph of a regular polyhedron. The goal of the paper is finding, for each regular polyhedron M, a number N(M) with the following properties: if n ≥ N(M), the group of pursuers wins, while if n < N(M), the evader wins. Part I of the paper is devoted to the case of polyhedra in ?³; Part II will be devoted to the case of ? ^d , d ≥ 5; and Part III, to the case of ?⁴.