Divisors of the number of Latin rectangles

A k×n Latin rectangle on the symbols {1,2,…,n} is called reduced if the first row is (1,2,…,n) and the first column is T(1,2,…,k). Let Rk,n be the number of reduced k×n Latin rectangles and m=⌊n/2⌋. We prove several results giving divisors of Rk,n. For example, (k−1)! divides Rk,n when k?m and m! divides Rk,n when m<k?n. We establish a recurrence which determines the congruence class of for a range of different t. We use this to show that Rk,n≡((−1)^k−1(k−1)!)ⁿ⁻¹. In particular, this means that if n is prime, then Rk,n≡1 for 1?k?n and if n is composite then if and only if k is larger than the greatest prime divisor of n.     

On the classification of perfect codes: Extended side class structures

The two 1-error correcting perfect binary codes, C and C^′ are said to be equivalent if there exists a permutation π of the set of the n coordinate positions and a word such that . Hessler defined C and C^′ to be linearly equivalent if there exists a non-singular linear map φ such that C^′=φ(C). Two perfect codes C and C^′ of length n will be defined to be extended equivalent if there exists a non-singular linear map φ and a word such that

     

Improvements on the Johnson bound for Reed-Solomon codes

For Reed-Solomon codes with block length n and dimension k, the Johnson theorem states that for a Hamming ball of radius smaller than , there can be at most O(n²) codewords. It was not known whether for larger radius, the number of codewords is polynomial. The best known list decoding algorithm for Reed-Solomon codes due to Guruswami and Sudan [Venkatesan Guruswami, Madhu Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes, IEEE Transactions on Information Theory 45 (6) (1999) 1757-1767] is also known to work in polynomial time only within this radius. In this paper we prove that when k<αn for any constant 0<α<1, we can overcome the barrier of the Johnson bound for list decoding of Reed-Solomon codes (even if the field size is exponential). More specifically in such a case, we prove that for Hamming ball of radius (for any c>0) there can be at most number of codewords. For any constant c, we describe a polynomial time algorithm for enumerating all of them, thereby also improving on the Guruswami-Sudan algorithm. Although the improvement is modest, this provides evidence for the first time that the bound is not sacrosanct for such a high rate.We apply our method to obtain sharper bounds on a list recovery problem introduced by Guruswami and Rudra [Venkatesan Guruswami, Atri Rudra, Limits to list decoding Reed-Solomon codes, IEEE Transactions on Information Theory 52 (8) (2006) 3642-3649] where they establish super-polynomial lower bounds on the output size when the list size exceeds . We show that even for larger list sizes the problem can be solved in polynomial time for certain values of k.     

Density of constant radius normal binary covering codes

A binary code with covering radius R is a subset C of the hypercube Q_n={0,1}ⁿ such that every x∈Q_n is within Hamming distance R of some codeword c∈C, where R is as small as possible. For a fixed coordinate i∈[n], define to be the set of codewords with a b in the ith position. Then C is normal if there exists an i∈[n] such that for any v∈Q_n, the sum of the Hamming distances from v to and is at most 2R+1. We newly define what it means for an asymmetric covering code to be normal, and consider the worst-case asymptotic densities ν^*(R) and of constant radius R symmetric and asymmetric normal covering codes, respectively. Using a probabilistic deletion method, and analysis adapted from previous work by Krivelevich, Sudakov, and Vu, we show that and , giving evidence that minimum size constant radius covering codes could still be normal.     

The orientable genus of some joins of complete graphs with large edgeless graphs

In an earlier paper the authors showed that with one exception the nonorientable genus of the graph with m≥n−1, the join of a complete graph with a large edgeless graph, is the same as the nonorientable genus of the spanning subgraph . The orientable genus problem for with m≥n−1 seems to be more difficult, but in this paper we find the orientable genus of some of these graphs. In particular, we determine the genus of when n is even and m≥n, the genus of when n=2^p+2 for p≥3 and m≥n−1, and the genus of when n=2^p+1 for p≥3 and m≥n+1. In all of these cases the genus is the same as the genus of K_m,n, namely ⌈(m−2)(n−2)/4⌉.     

A symmetry result for a general class of divergence form PDEs in fibered media

In R^m×R^n−m, endowed with coordinates X=(x,y), we consider the PDE

     

Bound states and the Szeg? condition for Jacobi matrices and Schrödinger operators

For Jacobi matrices with a_n=1+(−1)ⁿαn^−γ, b_n=(−1)ⁿβn^−γ, we study bound states and the Szeg? condition. We provide a new proof of Nevai's result that if , the Szeg? condition holds, which works also if one replaces (−1)ⁿ by . We show that if α=0, β≠0, and , the Szeg? condition fails. We also show that if γ=1, α and β are small enough ( will do), then the Jacobi matrix has finitely many bound states (for α=0, β large, it has infinitely many).     

Classification of solutions of a critical Hardy-Sobolev operator

In this article we classify all positive finite energy solutions of the equation in Rⁿ where and a point x∈Rⁿ is denoted as x=(y,z)∈R^k×R^n-k. As a consequence we obtain the best constant and extremals of a related Hardy-Sobolev inequality.     

Embeddings of homology equivalent manifolds with boundary

We prove a theorem on equivariant maps implying the following two corollaries:(1) Let N and M be compact orientable n-manifolds with boundaries such that M⊂N, the inclusion M→N induces an isomorphism in integral cohomology, both M and N have (n−d−1)-dimensional spines and . Then the restriction-induced map Embm(N)→Embm(M) is bijective. Here Embm(X) is the set of embeddings X→Rm up to isotopy (in the PL or smooth category).(2) For a 3-manifold N with boundary whose integral homology groups are trivial and such that N?D³ (or for its special 2-spine N) there exists an equivariant map , although N does not embed into R³.The second corollary completes the answer to the following question: for which pairs (m,n) for each n-polyhedron N the existence of an equivariant map implies embeddability of N into Rm? An answer was known for each pair (m,n) except (3,3) and (3,2).     

On the variety parameterizing completely decomposable polynomials

The purpose of this paper is to relate the variety parameterizing completely decomposable homogeneous polynomials of degree d in n+1 variables on an algebraically closed field, called , with the Grassmannian of (n−1)-dimensional projective subspaces of P^n+d−1. We compute the dimension of some secant varieties to . Moreover by using an invariant embedding of the Veronese variety into the Plücker space, we are able to compute the intersection of G(n−1,n+d−1) with , some of its secant varieties, the tangential variety and the second osculating space to the Veronese variety.     

New Orlicz-Hardy spaces associated with divergence form elliptic operators

Let L be the divergence form elliptic operator with complex bounded measurable coefficients, ω the positive concave function on (0,∞) of strictly critical lower type pω∈(0,1] and ρ(t)=t−1/ω−1(t−1) for t∈(0,∞). In this paper, the authors study the Orlicz-Hardy space Hω,L(Rn) and its dual space BMOρ,L^*(Rn), where L^* denotes the adjoint operator of L in L²(Rn). Several characterizations of Hω,L(Rn), including the molecular characterization, the Lusin-area function characterization and the maximal function characterization, are established. The ρ-Carleson measure characterization and the John-Nirenberg inequality for the space BMOρ,L(Rn) are also given. As applications, the authors show that the Riesz transform ∇L−1/2 and the Littlewood-Paley g-function gL map Hω,L(Rn) continuously into L(ω). The authors further show that the Riesz transform ∇L−1/2 maps Hω,L(Rn) into the classical Orlicz-Hardy space Hω(Rn) for and the corresponding fractional integral L−γ for certain γ>0 maps Hω,L(Rn) continuously into , where is determined by ω and γ, and satisfies the same property as ω. All these results are new even when ω(t)=tp for all t∈(0,∞) and p∈(0,1).     

Directed cyclic Hamiltonian cycle systems of the complete symmetric digraph

In this paper, we prove that directed cyclic Hamiltonian cycle systems of the complete symmetric digraph, , exist if and only if n is odd with n≠15 and n≠p^α for p an odd prime and α≥2 or with n≠2p^α for p an odd prime and α≥1. We also show that directed cyclic Hamiltonian cycle systems of the complete symmetric digraph minus a set of n/2 vertex-independent digons, (K_n−I)^∗, exist if and only if .     

Heteroclinic solutions for a class of the second order Hamiltonian systems

We shall be concerned with the existence of heteroclinic orbits for the second order Hamiltonian system , where q∈Rn and V∈C¹(R×Rn,R), V?0. We will assume that V and a certain subset M⊂Rn satisfy the following conditions. M is a set of isolated points and #M?2. For every sufficiently small ε>0 there exists δ>0 such that for all (t,z)∈R×Rn, if d(z,M)?ε then −V(t,z)?δ. The integrals , z∈M, are equi-bounded and −V(t,z)→∞, as |t|→∞, uniformly on compact subsets of Rn?M. Our result states that each point in M is joined to another point in M by a solution of our system.