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.     

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.     

Large convex cones in hypercubes

A family of subsets of [n] is positive linear combination free if the characteristic vector of neither member is the positive linear combination of the characteristic vectors of some other ones. We construct a positive linear combination free family which contains (1-o(1))2ⁿ subsets of [n] and we give tight bounds on the o(1)2ⁿ term. The problem was posed by Ahlswede and Khachatrian [Cone dependence—a basic combinatorial concept, Preprint 00-117, Diskrete Strukturen in der Mathematik SFB 343, Universität Bielefeld, 2000] and the result has geometric consequences.     

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.     

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].     

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.     

General preservers of invariant subspace lattices

Let be the space of all bounded linear operators on a Banach space X and let LatA be the lattice of invariant subspaces of the operator . We characterize some maps with one of the following preserving properties: Lat(Φ(A)+Φ(B))=Lat(A+B), or Lat(Φ(A)Φ(B))=Lat(AB), or Lat(Φ(A)Φ(B)+Φ(B)Φ(A))=Lat(AB+BA), or Lat(Φ(A)Φ(B)Φ(A))=Lat(ABA), or Lat([Φ(A),Φ(B)])=Lat([A,B]).     

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.     

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.     

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].     

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.     

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.     

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.     

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₄₉.     

Global stability of a rational difference equation

In this paper, we study the global stability of the difference equation , where the parameters a,a_i(0,∞) for i=0,…,k, x_-k,…, x_-1[0,∞) and x₀(0,∞). We prove that the unique positive equilibrium is globally asymptotically stable if and only if it is locally asymptotically. Also we provide sufficient condition for it to be globally asymptotically stable and our results solve the open problem proposed by Kulenović and Ladas (Dynamics of Second Order Rational Difference Equations with Open Problems and Conjectures, Chapman & Hall/CRC, Boca Raton, 2002).     

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.     

On the consistency strength of the Milner–Sauer conjecture

In their paper from 1981, Milner and Sauer conjectured that for any poset P,≤, if , then P must contain an antichain of cardinality κ. The conjecture is consistent and known to follow from GCH-type assumptions.

We prove that the conjecture has large cardinals consistency strength in the sense that its negation implies, for example, the existence of a measurable cardinal in an inner model. We also prove that the conjecture follows from Martin’s Maximum and holds for all singular λ above the first strongly compact cardinal.     

Jumps in cohomology and free group actions

A discrete group G has periodic cohomology over R if there is an element in a cohomology group cup product with which it induces an isomorphism in cohomology after a certain dimension. Adem and Smith showed that if , then this condition is equivalent to the existence of a finite dimensional free-G-CW-complex homotopy equivalent to a sphere. It has been conjectured by Olympia Talelli, that if G is also torsion-free then it must have finite cohomological dimension. In this paper we use the implied condition of jump cohomology over R to prove the conjecture for -groups and solvable groups. We also find necessary conditions for free and proper group actions on finite dimensional complexes homotopy equivalent to closed, orientable manifolds.