The Partitioned Version of the Erdős—Szekeres Theorem

   Abstract. Let k≥ 4 . A finite planar point set X is called a convex k -clustering if it is a disjoint union of k sets X ₁ , . . . ,X _k of equal sizes such that x ₁ x ₂ . . . x _k is a convex k -gon for each choice of x ₁ ∈ X ₁ , . . . ,x _k ∈ X _k . Answering a question of Gil Kalai, we show that for every k≥ 4 there are two constants c=c(k) , c'=c'(k) such that the following holds. If X is a finite set of points in general position in the plane, then it has a subset X' of size at most c' such that X \ X' can be partitioned into at most c convex k -clusterings. The special case k=4 was proved earlier by Pór. Our result strengthens the so-called positive fraction Erdos—Szekeres theorem proved by Barany and Valtr. The proof gives reasonable estimates on c and c' , and it works also in higher dimensions. We also improve the previous constants for the positive fraction Erdos—Szekeres theorem obtained by Pach and Solymosi.     

Asymptotic formula for the decay of correlations in the stochastic model of planar rotators at high temperature

We consider the stochastic model of planar rotators x(t)={x_k(t), k∈Z^d}, t≥0, x_k(t)∈T¹, at high temperature. For the decay of correlations <f_A(x(0)), g_A+k(t) (x(t))>, the asymptotic formula is obtained at t→∞, k(t)→∞, k(t)∈Z^d. The basic methods we used are the spectral analysis of the Markov semigroup generator and the saddle-point method. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 112, No. 1, pp. 67–80.     

Partitioning Posets

Given a poset P = (X, ≺ ), a partition X ₁, ..., X _k of X is called an ordered partition of P if, whenever x ∈ X _i and y ∈ X _j with x ≺ y, then i ≤ j. In this paper, we show that for every poset P = (X, ≺ ) and every integer k ≥ 2, there exists an ordered partition of P into k parts such that the total number of comparable pairs within the parts is at most (m − 1)/k, where m ≥ 1 is the total number of edges in the comparability graph of P. We show that this bound is best possible for k = 2, but we give an improved bound, , for k ≥ 3, where c(k) is a constant depending only on k. We also show that, given a poset P = (X, ≺ ) and an integer 2 ≤ k ≤ |X|, we can find an ordered partition of P into k parts that minimises the total number of comparable pairs within parts in time polynomial in the size of P. We prove more general, weighted versions of these results. Supported by an EPSRC doctoral training grant.     

Accuracy of several multidimensional refinable distributions

Compactly supported distributions f₁,..., f_r on ℝ^d are fefinable if each f_i is a finite linear combination of the rescaled and translated distributions f_j(Ax−k), where the translates k are taken along a lattice Γ ⊂ ∝^d and A is a dilation matrix that expansively maps Γ into itself. Refinable distributions satisfy a refinement equation f(x)=Σ_k∈Λ c_k f(Ax−k), where Λ is a finite subset of Γ, the c_k are r×r matrices, and f=(f₁,...,f_r)^T. The accuracy of f is the highest degree p such that all multivariate polynomials q with degree(q)<p are exactly reproduced from linear combinations of translates of f₁,...,f_r along the lattice Γ. We determine the accuracy p from the matrices c_k. Moreover, we determine explicitly the coefficients y_α,i(k) such that x^α=Σ _i=1 ^r Σ_k∈Γy_α,i(k) fi(x+k). These coefficients are multivariate polynomials y_α,i(x) of degree |α| evaluated at lattice points k∈Γ.     

Weierstrass multiple points on algebraic curves and ramified coverings

Here we prove the following result on Weierstrass multiple points. Theorem:Fix integers k, g with k≥5 and g>4k. Then there exist a genus g, Riemann surface X and k points P ₁, …,P _k of X such that for all integers b ₁≥…≥b _k ≥0we have:

Some new generalized difference sequence spaces defined by a sequence of moduli

The idea of difference sequence sets X( ) = {x = (x k ) : x ∈ X} with X = l ∞ , c and c 0 was introduced by Kizmaz [12]. In this paper, using a sequence of moduli we define some generalized difference sequence spaces and give some inclusion relations.     

Multivalued perturbations ofm-accretive differential inclusions

Given anm-accretive operatorA in a Banach spaceX and an upper semicontinuous multivalued mapF: [0,a]×X→2 ^X , we consider the initial value problemu′∈−Au+F(t,u) on [0,a],u(0)=x ₀. We concentrate on the case when the semigroup generated by—A is only equicontinuous and obtain existence of integral solutions if, in particular,X* is uniformly convex andF satisfies β(F(t,B))≤k(t)β(B) for all boundedB⊂X wherek∈L ¹([0,a]) and β denotes the Hausdorff-measure of noncompactness. Moreover, we show that the set of all solutions is a compactR _δ-set in this situation. In general, the extra condition onX* is essential as we show by an example in whichX is not uniformly smooth and the set of all solutions is not compact, but it can be omited ifA is single-valued and continuous or—A generates aC _o-semigroup of bounded linear operators. In the simpler case when—A generates a compact semigroup, we give a short proof of existence of solutions, again ifX* is uniformly (or strictly) convex. In this situation we also provide a counter-example in ℝ⁴ in which no integral solution exists. The author gratefully acknowledges financial support by DAAD within the scope of the French-German project PROCOPE.     

A Ramsey-Sperner theorem

Letn≥k≥1 be integers and letf(n, k) be the smallest integer for which the following holds: If ℱ is a family of subsets of ann-setX with |ℱ|<f(n,k) then for everyk-coloring ofX there existA B ∈ ℱ,A∈B, A⊂B such thatB-A is monochromatic. Here it is proven that for a fixedk there exist constantsc _k andd _k such that and ask→∞. The proofs of both the lower and the upper bounds use probabilistic methods.     

Decrease rate of the probabilities ofε-deviations for the means of stationary processes

The asymptotic behavior asn → ∞ of the normed sumsσn =n ⁻¹ Σ _k ⁼⁰ⁿ⁻¹ Xk for a stationary processX = (X _n ,n ∈ ℤ) is studied. For a fixedε > 0, upper estimates for P(sup _k≥n |σ _k | ≥ε) asn → ∞ are obtained. Translated fromMatematicheskie Zametki, Vol. 64, No. 3, pp. 366–372, September, 1998.     

A geometrical approach to theK-divisibility problem

We give a geometrical interpretation of the Brudnyi-KrugljakK-divisibility theorem—one of the fundamental results of modern interpolation theory of Banach spaces. We show that this result is closely connected with a curious intersection theorem which can be formulated in the spirit of Helly’s classical theorem. LetB ₀,B ₁ be two closed convex balanced subset of a Banach spaceX. We prove that under a wide range of various conditions the family of setsB = {B =sB ₀ +tB ₁ +c;s, t ∈R,c ∈X} possesses the following intersection property: LetB′ be a subfamily ofB such that every two sets fromB′ have a common point. Then ∩ _B∈B′ γ oB ≠ 0, where γ>0 is an absolute constant (γ ≤ 7 + 4 √2) and the symbol γ oB denotes a dilation ofB with respect to its center by a factor of γ. As a consequence we obtain a generalization of theK-divisibility theorem for sums of two elements. Supported by the Center for Absorption in Science, Israel Ministry of Immigrant Absorption and by grant No. 95-00225 from the United States-Israel Binational Science Foundation (BSF), Jerusalem, Israel.