Slight improvements of the Singleton bound

The problem of determining A_q(n,d), the maximum cardinality of a q-ary code of length n with minimum distance at least d, is considered in some cases where corresponding MDS codes do not exist. Slight improvements of the Singleton bound are given, including A_q(q+2,q)?q³-3 if q is odd, A₅(7,5)?5³-4 and A₁₆(18,15)?18⁴-4.     

Bounds for Covering Codes over Large Alphabets

Let K_q(n,R) denote the minimum number of codewords in any q-ary code of length n and covering radius R. We collect lower and upper bounds for K_q(n,R) where 6 ≤ q ≤ 21 and R ≤ 3. For q ≤ 10, we consider lengths n ≤ 10, and for q ≥ 11, we consider n ≤ 8. This extends earlier results, which have been tabulated for 2 ≤ q ≤ 5. We survey known bounds and obtain some new results as well, also for s-surjective codes, which are closely related to covering codes and utilized in some of the constructions.AMS Classification: 94B75, 94B25, 94B65Gerzson Kéri - Supported in part by the Hungarian National Research Fund, Grant No. OTKA-T029572.Patric R. J. Östergård - Supported in part by the Academy of Finland, Grants No. 100500 and No. 202315.     

Removable matchings and hamiltonian cycles

For a graph G, let σ₂(G) denote the minimum degree sum of two nonadjacent vertices (when G is complete, we let σ₂(G)=∞). In this paper, we show the following two results: (i) Let G be a graph of order n≥4k+3 with σ₂(G)≥n and let F be a matching of size k in G such that G−F is 2-connected. Then G−F is hamiltonian or G≅K₂+(K₂∪K_n−4) or ; (ii) Let G be a graph of order n≥16k+1 with σ₂(G)≥n and let F be a set of k edges of G such that G−F is hamiltonian. Then G−F is either pancyclic or bipartite. Examples show that first result is the best possible.     

New Results on Codes with Covering Radius 1 and Minimum Distance 2

The minimal cardinality of a q-ary code of length n and covering radius at most R is denoted by K_q(n, R); if we have the additional requirement that the minimum distance be at least d, it is denoted by K_q(n, R, d). Obviously, K_q(n, R, d) K_q(n, R). In this paper, we study instances for which K_q(n,1,2) > K_q(n, 1) and, in particular, determine K₄(4,1,2)=28 > 24=K₄(4,1).Supported in part by the Academy of Finland under grant 100500.     

Lower bounds on the minimum average distance of binary codes

Let β(n,M) denote the minimum average Hamming distance of a binary code of length n and cardinality M. In this paper we consider lower bounds on β(n,M). All the known lower bounds on β(n,M) are useful when M is at least of size about 2ⁿ⁻¹/n. We derive new lower bounds which give good estimations when size of M is about n. These bounds are obtained using a linear programming approach. In particular, it is proved that lim_n→∞β(n,2n)=5/2. We also give a new recursive inequality for β(n,M).     

Intersections of q-ary perfect codes

The intersections of q-ary perfect codes are under study. We prove that there exist two q-ary perfect codes C ₁ and C ₂ of length N = qn + 1 such that |C ₁ ? C ₂| = k · |P _i |/p for each k ∈ {0,..., p · K ? 2, p · K}, where q = p ^r , p is prime, r ≥ 1, $n = \tfrac{{q^{m - 1} - 1}}{{q - 1}}$ , m ≥ 2, |P _i | = p ^nr(q?2)+n , and K = p ^{n(2r?1)?r(m?1)}. We show also that there exist two q-ary perfect codes of length N which are intersected by p ^nr(q?3)+n codewords.     

On the chromaticity of complete multipartite graphs with certain edges added

Let P(G,λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H,λ)=P(G,λ) implies H is isomorphic to G. For integers k≥0, t≥2, denote by K((t−1)×p,p+k) the complete t-partite graph that has t−1 partite sets of size p and one partite set of size p+k. Let K(s,t,p,k) be the set of graphs obtained from K((t−1)×p,p+k) by adding a set S of s edges to the partite set of size p+k such that 〈S〉 is bipartite. If s=1, denote the only graph in K(s,t,p,k) by K⁺((t−1)×p,p+k). In this paper, we shall prove that for k=0,1 and p+k≥s+2, each graph G∈K(s,t,p,k) is chromatically unique if and only if 〈S〉 is a chromatically unique graph that has no cut-vertex. As a direct consequence, the graph K⁺((t−1)×p,p+k) is chromatically unique for k=0,1 and p+k≥3.     

Inequalities for the zeros of dirichlet L-functions

Let χ denote a primitive, Dirichlet character to the modulus q>i and let L(s,χ) be the corresponding Dirichlet L-series defined by L(s,χ) = ∑χ(n)n^?s,s = σ+it, for σ>0. It is of interest to know where the zeros of L(s,χ) are located, since the location of these zeros would yield important results in number theory. In this paper, we show that the spectrum of each member of a certain class of Hermitian matrices leads to an explicit zero-free region for L(s,χ).     

Characterization of the absence of a spectral gapfor a class of periodic Jacobi operators

Let q ∈ {2, 3} and let 0 = s₀ < s₁ < … < s_q = T be integers. For m, n ∈ Z, we put ¯m,n = {j ∈ Z| m? j ? n}. We set l_j = s_j − s_j−1 for j ∈ 1, q. Given (p₁,, p_q) ∈ R^q, let b: Z → R be a periodic function of period T such that b(·) = p_j on s_j−1 + 1, s_j for each j ∈ 1, q. We study the spectral gaps of the Jacobi operator (Ju)(n) = u(n + 1) + u(n − 1) + b(n)u(n) acting on l²(Z). By [λ_2j , λ_2j−1] we denote the jth band of the spectrum of J counted from above for j ∈ 1, T. Suppose that p_m ≠ p_n for m ≠ n. We prove that the statements (i) and (ii) below are equivalent for λ ∈ R and i ∈ 1, T − 1.     

Hamiltonian cycles and dominating cycles passing through a linear forest

Let G be an (m+2)-graph on n vertices, and F be a linear forest in G with |E(F)|=m and ω₁(F)=s, where ω₁(F) is the number of components of order one in F. We denote by σ₃(G) the minimum value of the degree sum of three vertices which are pairwise non-adjacent. In this paper, we give several σ₃ conditions for a dominating cycle or a hamiltonian cycle passing through a linear forest. We first prove that if σ₃(G)≥n+2m+2+max{s−3,0}, then every longest cycle passing through F is dominating. Using this result, we prove that if σ₃(G)≥n+κ(G)+2m−1 then G contains a hamiltonian cycle passing through F. As a corollary, we obtain a result that if G is a 3-connected graph and σ₃(G)≥n+κ(G)+2, then G is hamiltonian-connected.     

A local smoothing estimate for the Schrödinger equation

We show that the Schrödinger operator eitΔ is bounded from Wα,q(Rn) to Lq(Rn×[0,1]) for all α>2n(1/2−1/q)−2/q and q?2+4/(n+1). This is almost sharp with respect to the Sobolev index. We also show that the Schrödinger maximal operator sup0<t<1|eitΔf| is bounded from Hs(Rn) to when s>s₀ if and only if it is bounded from Hs(Rn) to L²(Rn) when s>2s₀. A corollary is that sup0<t<1|eitΔf| is bounded from Hs(R²) to L²(R²) when s>3/4.     

On geometric SDPS-sets of elliptic dual polar spaces

Let n∈N?{0,1} and let K and K^′ be fields such that K^′ is a quadratic Galois extension of K. Let Q⁻(2n+1,K) be a nonsingular quadric of Witt index n in PG(2n+1,K) whose associated quadratic form defines a nonsingular quadric Q⁺(2n+1,K^′) of Witt index n+1 in PG(2n+1,K^′). For even n, we define a class of SDPS-sets of the dual polar space DQ⁻(2n+1,K) associated to Q⁻(2n+1,K), and call its members geometric SDPS-sets. We show that geometric SDPS-sets of DQ⁻(2n+1,K) are unique up to isomorphism and that they all arise from the spin embedding of DQ⁻(2n+1,K). We will use geometric SDPS-sets to describe the structure of the natural embedding of DQ⁻(2n+1,K) into one of the half-spin geometries for Q⁺(2n+1,K^′).     

Small Point Sets that Meet All Generators of W(2n+1,q)

Let W(2n+1,q), n1, be the symplectic polar space of finite order q and (projective) rank n. We investigate the smallest cardinality of a set of points that meets every generator of W(2n+1,q). For q even, we show that this cardinality is q ⁿ⁺¹+q ^{n–1, and we characterize all sets of this cardinality. For q odd, better bounds are known.     

Partitions of natural numbers with the same representation functions

For a set A of nonnegative integers the representation functions R₂(A,n), R₃(A,n) are defined as the number of solutions of the equation n=a+a^′,a,a^′∈A with a<a^′, a?a^′, respectively. Let D(0)=0 and let D(a) denote the number of ones in the binary representation of a. Let A₀ be the set of all nonnegative integers a with even D(a) and A₁ be the set of all nonnegative integers a with odd D(a). In this paper we show that (a) if R₂(A,n)=R₂(N?A,n) for all n?2N−1, then R₂(A,n)=R₂(N?A,n)?1 for all n?12N²−10N−2 except for A=A₀ or A=A₁; (b) if R₃(A,n)=R₃(N?A,n) for all n?2N−1, then R₃(A,n)=R₃(N?A,n)?1 for all n?12N²+2N. Several problems are posed in this paper.     

The supertail of a subspace partition

Let V = V(n, q) be a vector space of dimension n over the finite field with q elements, and let d ₁ < d ₂ < ... < d _m be the dimensions that occur in a subspace partition ${\mathcal{P}}$ of V. Let σ _q (n, t) denote the minimum size of a subspace partition ${\mathcal P}$ of V, in which t is the largest dimension of a subspace. For any integer s, with 1 < s ≤ m, the set of subspaces in ${\mathcal{P}}$ of dimension less than d _s is called the s-supertail of ${\mathcal{P}}$ . The main result is that the number of spaces in an s-supertail is at least σ _q (d _s , d _s?1).     

The minimum size of a finite subspace partition

A subspace partition of P=PG(n,q) is a collection of subspaces of P whose pairwise intersection is empty. Let σ_q(n,t) denote the minimum size (i.e., minimum number of subspaces) in a subspace partition of P in which the largest subspace has dimension t. In this paper, we determine the value of σ_q(n,t) for . Moreover, we use the value of σ_q(2t+2,t) to find the minimum size of a maximal partial t-spread in PG(3t+2,q).     

On the prime power factorization of n!

For a fixed prime q, let eq(n) denote the order of q in the prime factorization of n!. For two fixed integers m?2 and r with 0?r?m−1, let A(x;m,q,r) denote the numbers of positive integers n?x for which . In this paper we shall prove a sharp asymptotic formula of A(x;m,q,r).     

Characterizing geometric designs, II

We provide a characterization of the classical point-line designs PG₁(n,q), where n?3, among all non-symmetric 2-(v,k,1)-designs as those with the maximal number of hyperplanes. As an application of this result, we characterize the classical quasi-symmetric designs PGn−2(n,q), where n?4, among all (not necessarily quasi-symmetric) designs with the same parameters as those having line size q+1 and all intersection numbers at least qn−4+?+q+1. Finally, we also give an explicit lower bound for the number of non-isomorphic designs having the same parameters as PG₁(n,q); in particular, we obtain a new proof for the known fact that this number grows exponentially for any fixed value of q.     

A semi-recursion for the number of involutions in special orthogonal groups over finite fields

Let I(n) be the number of involutions in a special orthogonal group SO(n,Fq) defined over a finite field with q elements, where q is the power of an odd prime. Then the numbers I(n) form a semi-recursion, in that for m>1 we haveI(2m+3)=(q2m+2+1)I(2m+1)+q2m(q2m−1)I(2m−2). We give a purely combinatorial proof of this result, and we apply it to give a universal bound for the character degree sum for finite classical groups defined over Fq.     

Monotonicity of the minimum cardinality of an identifying code in the hypercube

Let M_t(n) denote the minimum cardinality of a t-identifying code in the n-cube. It was conjectured that for all n?2 and t?1 we have M_t(n)?M_t(n+1). We prove this inequality for t=1.