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.     

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.     

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.     

Nonlinear maps preserving Lie products on factor von Neumann algebras

In this paper, we prove that every bijective map preserving Lie products from a factor von Neumann algebra into another factor von Neumann algebra is of the form A→ψ(A)+ξ(A), where is an additive isomorphism or the negative of an additive anti-isomorphism and is a map with ξ(AB-BA)=0 for all .     

On relations between 1-lines of Adams–Novikov spectral sequences modulo invariant prime ideals

We have a ring homomorphism Θ from the cohomology of the extended Morava stabilizer group G_n with coefficients in F[w^±1] to the cohomology of G_n+1 with coefficients in the graded field F((u_n))[u^±1]. In this note we study the behavior of Θ on H¹. Then it is shown that Θ is injective on H¹ for n1 and for all primes p.     

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

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.     

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.     

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

Sparse geometric graphs with small dilation

Given a set S of n points in , and an integer k such that 0k<n, we show that a geometric graph with vertex set S, at most n−1+k edges, maximum degree five, and dilation O(n/(k+1)) can be computed in time O(nlogn). For any k, we also construct planar n-point sets for which any geometric graph with n−1+k edges has dilation Ω(n/(k+1)); a slightly weaker statement holds if the points of S are required to be in convex position.     

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.     

Nonexistence of a code for

In this paper, we shall prove that there is no [3q⁴-q³-q²-3q-1,5,3q⁴-4q³-2q+1]_q code over the finite field for q11. Thus, we conclude the nonexistence of a [g_q(5,d),5,d]_q code for 3q⁴-4q³-2q+1d3q⁴-4q³-q.     

On distinct unit fractions whose sum equals 1

Questions, partial and complete answers about the diophantine equation in distinct positive integers are given when additional requirements are asked on the x_i's such as: being large, odd, even or x_ix_j for i≠j. Various combinations of the above conditions are also considered.     

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

Cauchy–Riemann equations and J-symplectic forms

Let (Σ,j) be a Riemann surface. The almost complex manifolds (M,J) for which the J-holomorphic curves :Σ→M are of variational type, are characterized. This problem is related to the existence of a vertically non-degenerate closed complex 3-form on Σ×M (see Theorem 4.3 below), which determines a family of J-symplectic structures on (M,J) parametrized by Σ.     

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.