A survey on proper codes

The performance of a linear t-error correcting code over a q-ary symmetric memoryless channel with symbol error probability ε is characterized by the probability that a transmission error will remain undetected. This probability is a function of ε involving the code weight distribution and the weight distribution of the cosets of minimum weight at most t. When the undetectable error probability is an increasing function of ε, the code is called t-proper.

The paper presents sufficient conditions for t-properness and a list of codes known to be proper, many of which have been studied by these sufficient conditions. Special attention is paid to error detecting codes of interest in modern communication.     

Minimal polynomials of the modified de Bruijn sequences

It is well known that a de Bruijn sequence over has the minimal polynomial (x+1)^d, where 2^n-1+nd2ⁿ-1. We study the minimal polynomials of the modified de Bruijn sequences.     

Coding for a multiple access OR channel: A survey

The signature coding for M active users out of T total users over a multiple access OR channel is considered. The mathematical problem is equivalent to the M-cover-free problem of extremal set theory. We survey the upper and lower bounds on the minimal code word length n(T,M), and present some code constructions. According to the current state of the theory, for 1MT

so there is a huge gap between the upper and lower bounds. Moreover, there is no known construction approaching the upper bound.     

Searching with lies under error cost constraints

The Rényi–Berlekamp–Ulam game is a classical model for the problem of determining the minimum number of queries to find an unknown member in a finite set when up to a finite number of the answers may be erroneous. In the variant considered in this paper, questions with q many possible answers are allowed, further lies are constrained by a bipartite graph with edges weighted by 0,1,2,… (the “channel”). The channel Γ is an arbitrary assignment stipulating the cost of the different possible lies, i.e., of each answer j≠i when the correct answer is i by Γ(i,j). It is also assumed that a maximum cost e (sum of the cost of all wrong answers) can be afforded by the responder during the whole game. We provide tight asymptotic bounds for the number of questions needed to solve this problem. The appropriate searching strategies are actually provided. We also show that adaptiveness can be dramatically reduced when the channel satisfies certain symmetry constraints.     

Self-spanner graphs

We introduce the (k,ℓ)-self-spanners graphs to model non-reliable interconnection networks. Such networks can be informally characterized as follows: if at most ℓ edges have failed, as long as two vertices remain connected, the distance between these vertices in the faulty graph is at most k times the distance in the non-faulty graph. By fixing the values k and ℓ (called stretch factor and fault-tolerance, respectively), we obtain specific new graph classes. We first provide characterizational, structural, and computational results for these classes. Then, we study relationships between the introduced classes and special graphs classes (distance-hereditary graphs, cographs, and chordal graphs), and common network topologies (grids, tori, hypercubes, butterflies, and cube-connected cycles) as well.     

Limit shape of convex lattice polygons with minimal perimeter

Let n be a positive integer and · any norm in . Denote by B the unit ball of · and the class of convex lattice polygons with n vertices and least ·-perimeter. We prove that after suitable normalization, all members of tend to a fixed convex body, as n→∞.     

On periodic radical groups in which permutability is a transitive relation

A group G is said to be a -group if permutability is a transitive relation in the set of all subgroups of G. Our purpose in this paper is to study -groups in the class of periodic radical groups satisfying min-p for all primes p.     

Uniform asymptotic expansions of the Pollaczek polynomials

Two uniform asymptotic expansions are obtained for the Pollaczek polynomials P_n(cosθ;a,b). One is for , , in terms of elementary functions and in descending powers of . The other is for , in terms of a special function closely related to the modified parabolic cylinder functions, in descending powers of n. This interval contains a turning point and all possible zeros of P_n(cosθ) in θ(0,π/2].     

On partitioning two matroids into common independent subsets

Let M₁ and M₂ be two matroids on the same ground set S. We conjecture that if there do not exist disjoint subsets A₁,A₂,…,A_k+1 of S, such that _isp_M1(A_i)≠Ø, and similarly for M₂, then S is partitioned into k sets, each independent in both M₁ and M₂. This is a possible generalization of König's edge-coloring theorem. We prove the conjecture for the case k=2 and for a regular case, in which both matroids have the same rank d, and S consists of k·d elements. Finally, we prove another special case related to a conjecture of Rota.     

Discrete subspaces of countably tight compacta

Our main result is that the following cardinal arithmetic assumption, which is a slight weakening of GCH, “2^κ is a finite successor of κ for every cardinal κ”, implies that in any countably tight compactum X there is a discrete subspace D with . This yields a (consistent) confirmation of Alan Dow’s Conjecture 2 from [A. Dow, Closures of discrete sets in compact spaces, Studia Math. Sci. Hung. 42 (2005) 227–234].     

On -differential graded algebras

We introduce the concept of N-differential graded algebras (N-dga), and study the moduli space of deformations of the differential of an N-dga. We prove that it is controlled by what we call the (M,N)-Maurer–Cartan equation.     

Countable choice and compactness

We work in set-theory without choice ZF. Denoting by the countable axiom of choice, we show in that the closed unit ball of a uniformly convex Banach space is compact in the convex topology (an alternative to the weak topology in ZF). We prove that this ball is (closely) convex-compact in the convex topology. Given a set I, a real number p1 (respectively p=0), and some closed subset F of [0,1]^I which is a bounded subset of ℓ^p(I), we show that (respectively DC, the axiom of Dependent Choices) implies the compactness of F.     

The PI index of product graphs

The Padmakar–Ivan index of a graph G is the sum over all edges uv of G of number of edges which are not equidistant from u and v. In this work, an exact expression for the PI index of the Cartesian product of bipartite graphs is computed. Using this formula, the PI indices of C₄ nanotubes and nanotori are computed.     

Coclass and cohomology

Recently, it was proved by Leedham-Green and others that with a finite number of exceptions, every p-group of coclass r is a quotient of one of only a finite number of p-adic uniserial space groups. In this paper we use that structure to demonstrate that there are only finitely many isomorphism classes of cohomology rings of 2-groups of coclass r with coefficients in any fixed field k of characteristic 2. In addition, there is experimental evidence indicating that in many cases successive quotients of the uniserial space groups have isomorphic cohomology rings.     

Mass formula for self-dual codes over Z

We give a mass formula for self-dual codes over Z_p², where p is an odd prime. Using the mass formula, we classify such codes of lengths up to n=8 over the ring Z₉, n=7 over Z₂₅ and n=6 over Z₄₉.     

Buchsbaum homogeneous algebras with minimal multiplicity

In this paper we first give a lower bound on multiplicities for Buchsbaum homogeneous k-algebras A in terms of the dimension d, the codimension c, the initial degree q, and the length of the local cohomology modules of A. Next, we introduce the notion of Buchsbaum k-algebras with minimal multiplicity of degree q, and give several characterizations for those rings. In particular, we will show that those algebras have linear free resolutions. Further, we will give many examples of those algebras.     

The total chromatic number of regular graphs of even order and high degree

The total chromatic number χ_T(G) of a graph G is the minimum number of colours needed to colour the edges and the vertices of G so that incident or adjacent elements have distinct colours. We show that if G is a regular graph of even order and , thenχ_T(G)Δ(G)+2.     

Covering point sets with two disjoint disks or squares

We study the following problem: Given a set of red points and a set of blue points on the plane, find two unit disks C_R and C_B with disjoint interiors such that the number of red points covered by C_R plus the number of blue points covered by C_B is maximized. We give an algorithm to solve this problem in O(n^8/3log²n) time, where n denotes the total number of points. We also show that the analogous problem of finding two axis-aligned unit squares S_R and S_B instead of unit disks can be solved in O(nlogn) time, which is optimal. If we do not restrict ourselves to axis-aligned squares, but require that both squares have a common orientation, we give a solution using O(n³logn) time.     

Proximity problems on line segments spanned by points

Finding the closest or farthest line segment (line) from a point are fundamental proximity problems. Given a set S of n points in the plane and another point q, we present optimal O(nlogn) time, O(n) space algorithms for finding the closest and farthest line segments (lines) from q among those spanned by the points in S. We further show how to apply our techniques to find the minimum (maximum) area triangle with a vertex at q and the other two vertices in S{q} in optimal O(nlogn) time and O(n) space. Finally, we give an O(nlogn) time, O(n) space algorithm to find the kth closest line from q and show how to find the k closest lines from q in O(nlogn+k) time and O(n+k) space.     

Fractal sets determined by dilation-stable processes

Let be a dilation-stable process on . We determine a Hausdorff measure function (a) such that the fractal set X[0,1]={X(t):0t1} has positive finite -measure. We also investigate the packing measure of X[0,1].