A class of optimal linear codes of length one above the Griesmer bound

In this paper, we determine the smallest lengths of linear codes with some minimum distances. We construct a [g _q (k, d) + 1, k, d] _q code for sq ^k-1 − sq ^k-2 − q ^s  − q ² + 1 ≤ d ≤ sq ^k-1 − sq ^k-2 − q ^s with 3 ≤ s ≤ k − 2 and q ≥ s + 1. Then we get n _q (k, d) = g _q (k, d) + 1 for (k − 2)q ^k-1 − (k − 1)q ^k-2 − q ² + 1 ≤ d ≤ (k − 2)q ^k-1 − (k − 1)q ^k-2, k ≥ 6, q ≥ 2k − 3; and sq ^k-1 − sq ^k-2 − q ^s  − q + 1 ≤ d ≤ sq ^k-1 − sq ^k-2 − q ^s , s ≥ 2, k ≥ 2s + 1 and q ≥ 2s − 1. This work was partially supported by the Com²MaC-SRC/ERC program of MOST/KOSEF (grant ^# R11-1999-054) and was partially supported by the Korea Research Foundation Grant funded by the Korean Government(MOEHRD)(KRF-2005-214-C00175).     

Distributions of Points in <Emphasis Type="Italic">d</Emphasis> Dimensions and Large <Emphasis Type="Italic">k</Emphasis>-Point Simplices

We consider a variant of Heilbronn’s triangle problem by investigating for a fixed dimension d≥2 and for integers k≥2 with k≤d distributions of n points in the d-dimensional unit cube [0,1] ^d , such that the minimum volume of the simplices, which are determined by (k+1) of these n points is as large as possible. Denoting by Δ _k,d (n), the supremum of this minimum volume over all distributions of n points in [0,1] ^d , we show that c _k,d ⋅(log n)^1/(d−k+1)/n ^k/(d−k+1)≤Δ _k,d (n)≤c _k,d ′/n ^k/d for fixed 2≤k≤d, and, moreover, for odd integers k≥1, we show the upper bound Δ _k,d (n)≤c _k,d ″/n ^{k/d+(k−1)/(2d(d−1))}, where c _k,d ,c _k,d ′,c _k,d ″>0 are constants. A preliminary version of this paper appeared in COCOON ’05.     

Estimates for the number of rational points on convex curves and surfaces

Let Γ ⊂ ℝ^d be a bounded strictly convex surface. We prove that the number k_n(Γ) of points of Γ that lie on the lattice satisfies the following estimates: lim inf k_n(Γ)/n^d−2 < ∞ for d ≥ 3 and lim inf k_n(Γ)/log n < ∞ for d = 2. Bibliography: 9 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 344, 2007, pp. 174–189.     

The gonality of smooth curves with plane models

LetC be the normalization of an integral plane curve of degreed with δ ordinary nodes or cusps as its singularities. If δ=0, then Namba proved that there is no linear seriesg _d ^−2/1 and that everyg _d ^−1/1 is cut out by a pencil of lines passing through a point onC. The main purpose of this paper is to generalize his result to the case δ>0. A typical one is as follows: Ifd≥2(k+1), and δ<kd−(k+1)²+3 for somek>0, thenC has no linear seriesg _d ^−3/1 . We also show that ifd≥2k+3 and δ<kd−(k+1)²+2, then each linear seriesg _d ^−2/1 onC is cut out by a pencil of lines. We have similar results forg _d ^−1/1 andg _2d ^−9/1 . Furthermore, we also show that all of our theorems are sharp.     

Equipartition of mass distributions by hyperplanes

We consider the problem of determining the smallest dimensiond=Δ(j, k) such that, for anyj mass distributions inR ^d , there arek hyperplanes so that each orthant contains a fraction 1/2 ^k of each of the masses. The case Δ(1,2)=2 is very well known. The casek=1 is answered by the ham-sandwich theorem with Δ(j, 1)=j. By using mass distributions on the moment curve the lower bound Δ(j, k)≥j(2 ^k −1)/k is obtained. We believe this is a tight bound. However, the only general upper bound that we know is Δ(j, k)≤j2 ^k−1. We are able to prove that Δ(j, k)=⌈j(^2k−1/k⌉ for a few pairs (j, k) ((j, 2) forj=3 andj=2 ⁿ withn≥0, and (2, 3)), and obtain some nontrivial bounds in other cases. As an intermediate result of independent interest we prove a Borsuk-Ulam-type theorem on a product of balls. The motivation for this work was to determine Δ(1, 4) (the only case forj=1 in which it is not known whether Δ(1,k)=k); unfortunately the approach fails to give an answer in this case (but we can show Δ(1, 4)≤5). This research was supported by the National Science Foundation under Grant CCR-9118874.     

Preservation of the injectivity of the Gauss map for general projections

Let X be a smooth irreducible quasi-projective variety of dimension n in P ^N with N ≥ 2n + 2. Let γ be its Gauss map, let be the embedding obtained from the general projection in P ^N and let γ′ be its Gauss map. We say that the general projection preserves the injectivity of the Gauss map if γ(Q) ≠ γ(Q′) implies γ′(Q) ≠ γ′ (Q′). We prove that this property holds in the following cases: N≥ 3n + 1; N ≥ 3n with n ≥ 2; N ≥ 3n−1 with n ≥ 4 and X does not contain a linear (n−1)-space. In case N = 3n−1 and X does contain a linear (n−1)-space (such smooth varieties exist) then the general projection does not preserver the injectivity of the Gauss map. This shows that there does not exist a straightforward kind of Bertini theorem for properties related to the Gauss map. The author is affiliated with the University at Leuven as a research fellow. This paper belongs to the FWO-project G.0318.06.     

A sufficient degree condition for a graph to contain all trees of size <Emphasis Type="Italic">k</Emphasis>

The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d _G (x) + d _G (y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d _G (u) ≥ k.     

On the Construction of Permutation Arrays via Mappings from Binary Vectors to Permutations

An (n, d, k)-mapping f is a mapping from binary vectors of length n to permutations of length n + k such that for all x, y {0,1}ⁿ, d_H (f(x), f(y)) ≥ d_H (x, y) + d, if d_H (x, y) ≤ (n + k) − d and d_H (f(x), f(y)) = n + k, if d_H (x, y) > (n + k) − d. In this paper, we construct an (n,3,2)-mapping for any positive integer n ≥ 6. An (n, r)-permutation array is a permutation array of length n and any two permutations of which have Hamming distance at least r. Let P(n, r) denote the maximum size of an (n, r)-permutation array and A(n, r) denote the same setting for binary codes. Applying (n,3,2)-mappings to the design of permutation array, we can construct an efficient permutation array (easy to encode and decode) with better code rate than previous results [Chang (2005). IEEE Trans inf theory 51:359–365, Chang et al. (2003). IEEE Trans Inf Theory 49:1054–1059; Huang et al. (submitted)]. More precisely, we obtain that, for n ≥ 8, P(n, r) ≥ A(n − 2, r − 3) > A(n − 1,r − 2) = A(n, r − 1) when n is even and P(n, r) ≥ A(n − 2, r − 3) = A(n − 1, r − 2) > A(n, r − 1) when n is odd. This improves the best bound A(n − 1,r − 2) so far [Huang et al. (submitted)] for n ≥ 8. The work was supported in part by the National Science Council of Taiwan under contract NSC-93-2213-E-009-117     

Tiling Transitive Tournaments and Their Blow-ups

Let TT _k denote the transitive tournament on k vertices. Let TT(h,k) denote the graph obtained from TT _k by replacing each vertex with an independent set of size h≥1. The following result is proved: Let c ₂=1/2, c ₃=5/6 and c _k =1−2^{−k−log k} for k≥4. For every ∈>0 there exists N=N(∈,h,k) such that for every undirected graph G with n>N vertices and with δ(G)≥c _k n, every orientation of G contains vertex disjoint copies of TT(h,k) that cover all but at most ∈n vertices. In the cases k=2 and k=3 the result is asymptotically tight. For k≥4, c _k cannot be improved to less than 1−2^{−0.5k(1+o(1))}. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the Bethe-Sommerfeld conjecture for higher-order elliptic operators

 We consider the elliptic operator P(D)+V in ℝ ^d , d≥2 where P(D) is a constant coefficient elliptic pseudo-differential operator of order 2ℓ with a homogeneous convex symbol P(ξ), and V is a real periodic function in L ^∞(ℝ ^d ). We show that the number of gaps in the spectrum of P(D)+V is finite if 4ℓ>d+1. If in addition, V is smooth and the convex hypersurface {ξℝ ^d :P(ξ)=1} has positive Gaussian curvature everywhere, then the number of gaps in the spectrum of P(D)+V is finite, provided 8ℓ>d+3 and 9≥d≥2, or 4ℓ>d−3 and d≥10. Received: 10 October 2001 / Published online: 28 March 2003 Mathematics Subject Classification (1991): 35J10 Research supported in part by NSF Grant DMS-9732894.     

A class of constructions for turán’s (3, 4)-problem

Letf(n) denote the minimal number of edges of a 3-uniform hypergraphG=(V, E) onn vertices such that for every quadrupleY ⊂V there existsY ⊃e ∈E. Turán conjectured thatf(3k)=k(k−1)(2k−1). We prove that if Turán’s conjecture is correct then there exist at least 2 ^k−2 non-isomorphic extremal hypergraphs on 3k vertices.     

Self-similar extremal processes

Given an extremal process X: [0,∞)→[0,∞)^d with lower curve C and associated point process N={(t_k, X_k):k≥0}, t_k distinct and X_k independent, given a sequence ζ _n =(τ _n , ξ _n ), n≥1, of time-space changes (max-automorphisms of [0,∞)^d+1), we study the limit behavior of the sequence of extremal processes Y_n(t)=ξ _n ^-1 ○ X ○ τ_n(t)=C_n(t) V max {ξ _n ^-1 ○ X_k: t_k ≤ τ_n(t){ ⇒ Y under a regularity condition on the norming sequence ζ_n and asymptotic negligibility of the max-increments of Y_n. The limit class consists of self-similar (with respect to a group η_α=(σ_α, L_α), α>0, of time-space changes) extremal processes. By self-similarity here we mean the property L_α ○ Y(t) ₌ ^d Y ○ α_α(t) for all α>0. The univariate marginals of Y are max-self-decomposable. If additionally the initial extremal process X is assumed to have homogeneous max-increments, then the limit process is max-stable with homogeneous max-increments. Supported by the Bulgarian Ministry of Education and Sciences (grant No. MM 234/1996). Proceedings of the Seminar on Stability Problems for Stochastic Models, Hajdúszoboszló, Hungary, 1997, Part I.     

On the generation of clones containing near-unanimity operations

It is a well-known consequence of the Baker-Pixley-Theorem that any clone containing a near-unanimity operation is finitely generated, leading to the question what arity the generating functions must have. In this paper, we show that, for arbitrary d ≥ 2 and large enough n, (n − 1) ^d − 1 is the smallest integer k such that, for every clone C on an n-element set that contains a (d + 1)-ary near-unanimity operation, C ^(k) generates C.     

Kähler hyperbolicity and the Euler number of a compact manifold with geodesic flow of Anosov type

 Let M be a 2m-dimensional compact Riemannian manifold with Anosov geodesic flow. We prove that every closed bounded k form, k≥2, on the universal covering of M is d(bounded). Further, if M is homotopy equivalent to a compact K?hler manifold, then its Euler number χ(M) satisfies (−1) ^m χ(M)>0. Received: 25 September 2001 / Published Online: 16 October 2002     

A Centrally Symmetric Version of the Cyclic Polytope

We define a centrally symmetric analogue of the cyclic polytope and study its facial structure. We conjecture that our polytopes provide asymptotically the largest number of faces in all dimensions among all centrally symmetric polytopes with n vertices of a given even dimension d=2k when d is fixed and n grows. For a fixed even dimension d=2k and an integer 1≤j<k we prove that the maximum possible number of j-dimensional faces of a centrally symmetric d-dimensional polytope with n vertices is at least for some c _j (d)>0 and at most as n grows. We show that c ₁(d)≥1−(d−1)⁻¹ and conjecture that the bound is best possible. Research of A. Barvinok partially supported by NSF grant DMS 0400617. Research of I. Novik partially supported by Alfred P. Sloan Research Fellowship and NSF grant DMS-0500748.     

On some 2-adic properties of a recurrence involving stirling numbers

We analyze some 2-adic properties of the sequence defined by the recurrence Z(1) = 1; Z(n) = Σ _k=1 ⁿ⁻¹ S(n, k)Z(k), n ≥ 2, which counts the number of ultradissimilarity relations, i.e., ultrametrics on an n-set. We prove the 2-adic growth property ν ₂(Z(n)) ≥ ⌈log₂ n⌉ −1 and present conjectures on the exact values.     

Convex subdivisions with low stabbing numbers

It is shown that for every subdivision of the d-dimensional Euclidean space, d ≥ 2, into n convex cells, there is a straight line that stabs at least Ω((log n/log log n)^1/(d−1)) cells. In other words, if a convex subdivision of d-space has the property that any line stabs at most k cells, then the subdivision has at most exp(O(k ^d−1 log k)) cells. This bound is best possible apart from a constant factor. It was previously known only in the case d = 2. Supported in part by NSERC grant RGPIN 35586.     

Extensions of the D(?k2)-triples {k2, k2 ± 1, 4k2 ± 1}

Let n be a nonzero integer. A set of m distinct positive integers is called a D(n)-m-tuple if the product of any two of them increased by n is a perfect square. Let k be a positive integer. In this paper, we show that if {k ², k ² + 1, 4k ² + 1, d} is a D(−k ²)-quadruple, then d = 1, and that if {k ² − 1, k ², 4k ² − 1, d} is a D(k ²)-quadruple, then d = 8k ²(2k ² − 1).     

Near optimal bounds for the Erdős distinct distances problem in high dimensions

We show that the number of distinct distances in a set of n points in ℝ ^d is Ω(n ^{2/d − 2 / d(d + 2)}), d ≥ 3. Erdős’ conjecture is Ω(n ^2/d ).     

The smallest degree sum that yields potentially Kr,r-graphic sequences

We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(K_r,r,n) such that every n-term graphic sequence π = (d₁,d₂,...,d_n) with term sum σ(π) = d₁ + d₂ + ... + d_n ≥ σ(K_r,r,n) is potentially K_r,r-graphic, where K_r,r is an r × r complete bipartite graph, i.e. π has a realization G containing K_r,r as its subgraph. In this paper, the values σ(K_r,r,n) for even r and n ≥ 4r² - r - 6 and for odd r and n ≥ 4r² + 3r - 8 are determined.