Approximation under an arc length constraint

Let f C[a, b]. LetP be a subset ofC[a, b], L b – a be a given real number. We say thatp P is a best approximation tof fromP, with arc length constraintL, ifA[p] _b ^a [1 + (p(x)) ²]dx L andp – f q – f for allq P withA[q] L. represents an arbitrary norm onC[a, b]. The constraintA[p] L might be interpreted physically as a materials constraint.In this paper we consider the questions of existence, uniqueness and characterization of constrained best approximations. In addition a bound, independent of degree, is found for the arc length of a best unconstrained Chebyshev polynomial approximation.The work of L. L. Keener is supported by the National Research Council of Canada Grant A8755.     

The caratheodory number for thek-core

Thek-core of the setS ⁿ is the intersection of the convex hull of all setsA S with ¦SA¦<-k. The Caratheodory number of thek-core is the smallest integerf (d,k) with the property thatx core _{kS, S} ⁿ implies the existence of a subsetT S such thatx core_kT and ¦T¦f (d, k). In this paper various properties off(d, k) are established.Research of this author was partially supported by Hungarian National Science Foundation grant no. 1812.     

On relatively short and long sides of convex pentagons

By the relative distance of pointsa andb of a convex bodyC we mean the ratio of the Euclidean distance ofa andb to the half of the Euclidean distance ofa, b C such thatab is a longest chord ofC parallel to the segmentab. We say that a sideab of a convexn-gon is relatively short (respectively: relatively long) if the relative distance ofa andb is at most (respectively: at least) the relative distance of two consecutive vertices of the regularn-gon. We show that every convexn-gon, wheren 5, has a relatively short side and a relatively long side, and that it is affine-regular if and only if all its sides are of equal relative lengths.Research supported in part by Komitet Bada Naukowych (Committee of Scientific Research), grant number 2 2005 92 03.     

A solution of Hadwiger's covering problem for zonoids

For a convex body M ⁿ byb(M) the least integerp is denoted, such that there are bodiesM ₁, ...,M _p each of which is homothetic toM with a positive ratiok<1 andM ₁...M _p M. H. Martini has proved [7] thatb(M)<-3·2 ^n–2 for every zonotope M ⁿ , which is not a parallelotope.In the paper this Martini's result is extended to zonoids. In the proof some notions and facts of real functions theory are used (points of density, approximative continuity).     

Tilings of polygons with similar triangles

We prove that if a polygonP is decomposed into finitely many similar triangles then the tangents of the angles of these triangles are algebraic over the field generated by the coordinates of the vertices ofP. IfP is a rectangle then, apart from four sporadic cases, the triangles of the decomposition must be right triangles. Three of these sporadic triangles tile the square. In any other decomposition of the square into similar triangles, the decomposition consists of right triangles with an acute angle such that tan is a totally positive algebraic number. Most of the proofs are based on the following general theorem: if a convex polygonP is decomposed into finitely many triangles (not necessarily similar) then the coordinate system can be chosen in such a way that the coordinates of the vertices ofP belong to the field generated by the cotangents of the angles of the triangles in the decomposition.This work was completed while the author had a visiting position at the Mathematical Institute of the Hungarian Academy of Sciences.     

Krasnosel'skii numbers for bounded finitely starlike sets inR d

For eachk andd, 1kd, definef(d, d)=d+1 andf(d, k)=2d if 1kd–1. The following results are established:Let be a uniformly bounded collection of compact, convex sets inR ^d . For a fixedk, 1kd, dim {MM in }k if and only if for some > 0, everyf(d, k) members of contain a commonk-dimensional set of measure (volume) at least.LetS be a bounded subset ofR ^d . Assume that for some fixedk, 1kd, there exists a countable family of (k–l)-flats {H _i :i1} inR ^d such that clS S {H_i i 1 } and for eachi1, (clS S) H _i has (k–1) dimensional measure zero. Every finite subset ofS sees viaS a set of positivek-dimensional measure if and only if for some>0, everyf(d,k) points ofS see viaS a set ofk-dimensional measure at least .The numbers off(d,d) andf(d, 1) above are best possible.Supported in part by NSF grant DMS-8705336.     

On the Sobolev distance of convex bodies

Summary LetK ^d denote the cone of all convex bodies in the Euclidean spaceK ^d . The mappingK h _K of each bodyK K ^d onto its support function induces a metric _w onK ^d by" _w (K, L)h _L –h _{K w} where _w is the Sobolev I-norm on the unit sphere . We call _w (K, L) the Sobolev distance ofK andL. The goal of our paper is to develop some fundamental properties of the Sobolev distance.     

Reconstructing dimensions of intersections of convex sets

Denoting by dimA the dimension of the affine hull of the setA, we prove that if {K _i:i T} and {K _i ^j :i T} are two finite families of convex sets inR ⁿ and if dim {K _i :i S} = dim {K _i ^j :i S}for eachS T such that|S| n + 1 then dim {K _i :i T} = dim {K _i : {i T}}.     

Variations on the theme of repeated distances

We give an asymptotically sharp estimate for the error term of the maximum number of unit distances determined byn points in ^{d, d}4. We also give asymptotically tight upper bounds on the total number of occurrences of the favourite distances fromn points in ^{d, d}4. Related results are proved for distances determined byn disjoint compact convex sets in ².At the time this paper was written, both authors were visiting the Technion — Israel Institute of Technology.     

Finitely starlike sets whose F-stars have positive measure

Let and assume that there is a countable collection of lines {L _i : 1 i} such that (int cl S) and ((int cl S) S) L _i has one-dimensional Lebesgue measure zero, 1 i. Then every 4 point subset ofS sees viaS a set of positive two-dimensional Lebesgue measure if and only if every finite subset ofS sees viaS such a set. Furthermore, a parallel result holds with two-dimensional replaced by one-dimensional. Finally, setS is finitely starlike if and only if every 5 points ofS see viaS a common point. In each case, the number 4 or 5 is best possible.Supported in part by NSF grant DMS-8705336.     

Improved Krasnosel'skii theorems for the dimension of the kernel of a starshaped set

We will establish the following improved Krasnosel'skii theorems for the dimension of the kernel of a starshaped set: For each k and d, 0 k d, define f(d,k) = d+1 if k = 0 and f(d,k) = max{d+1,2d–2k+2} if 1 k d.Theorem 1. Let S be a compact, connected, locally starshaped set in R^d, S not convex. Then for a k with 0 k d, dim ker S k if and only if every f(d, k) lnc points of S are clearly visible from a common k-dimensional subset of S.Theorem 2. Let S be a nonempty compact set in R^d. Then for a k with 0 k d, dim ker S k if and only if every f (d, k) boundary points of S are clearly visible from a common k-dimensional subset of S. In each case, the number f(d, k) is best possible for every d and k.     

On a pair of functional equations of combinatorial interest

The equations of the title appear in the author's paper Chromatic Sums for Rooted Planar Triangulations, V: Special Equations. (Canadian Journal of Mathematics, 26 (1974), 893–907). They appear in that paper as Equations (24) and (25). They are simultaneous equations for two unknown functionsl andy ₂ of two variablesy ₁ andz. A parameter is involved. The main result is that for = 2 cos (2/n), wheren is a positive integer >1, the two equations can be reduced to a single equation (numbered (49)). Solutions of this are known forn <7. From such solutions we can expect to get information about the averaged chromatic polynomials of planar triangulations with a given number of triangles.The present work is basically an expository paper on the theory given in Chromatic Sums, V, but it includes some new results and many simplifications.     

On integer points in polyhedra

We give an upper bound on the number of vertices ofP _I , the integer hull of a polyhedronP, in terms of the dimensionn of the space, the numberm of inequalities required to describeP, and the size of these inequalities. For fixedn the bound isO(m ^{n n–} ). We also describe an algorithm which determines the number of integer points in a polyhedron to within a multiplicative factor of 1+ in time polynomial inm, and 1/ when the dimensionn is fixed.Supported by Sonderfschungsbereich 303 (DFG) and NSF grant ECS-8611841.Partially supported by NSF grant DMS-8905645.Supported by NSF grants ECS-8418392 and CCR-8805199.mcd%vax.oxford.ac.uk     

Ambiguous loci of the metric projection onto compact starshaped sets in a Banach space

LetE be a real Banach space andL(E) the family of all nonempty compact starshaped subsets ofE. Under the Hausdorff distance,L(E) is a complete metric space. The elements of the complement of a first Baire category subset ofL(E) are called typical elements ofL(E). ForXL(E) we denote by the metrical projection ontoX, i.e. the mapping which associates to eachaE the set of all points inX closest toa. In this note we prove that, ifE is strictly convex and separable with dimE2, then for a typicalXL(E) the map is not single valued at a dense set of points. Moreover, we show that a typical element ofL(E) has kernel consisting of one point and set of directions dense in the unit sphere ofE.     

Staircase kernels for orthogonald-polytopes

LetS be a finite union of boxes inR ^d . Forx inS, defineA _x ={yx is clearly visible fromy via staircase paths inS}, and let KerS denote the staircase kernel ofS. Then KerS={A _x x is a point of local nonconvexity ofS}. A similar result holds with clearly visible replaced by visible and points of local nonconvexity ofS replaced by boundary points ofS.Supported in part by NSF grant DMS-9207019.     

Darstellung einer Ordnung von Maßen durch Stoppzeiten

Summary Given a stochastic matrixP on the state spaceI an ordering for measures inI can be defined in the following way: iff(f)(f) for allf in a sufficiently rich subcone of the cone of positiveP-subharmonic functions. It is shown that, if, are probability measures with , then in theP-process (X _n)_n0 having as initial distribution there exists a stopping time such thatX is distributed according to. In addition, can be chosen in such a way, that for every positive subharmonicf with(f)< the submartingale (f(X _n))_n0 is uniformly integrable.     

Remarks on ergodicity of stationary irreducible transient Markov chains

Summary Consider a stationary process {X _n(), – < n < . If the measure of the process is finite (the measure of the whole sample space finite), it is well known that ergodicity of the process {X _n(), - < n < and of each of the subprocesses {X _n(), 0 n < , {X _n(), – < n 0 are equivalent (see [3]). We shall show that this is generally not true for stationary processes with a sigma-finite measure, specifically for stationary irreducible transient Markov chains. An example of a stationary irreducible transient Markov chain {X _n(), - < n <} with {itX_n(), 0 n < < ergodic but {X _n(), < n 0 nonergodic is given. That this can be the case has already been implicitly indicated in the literature [4]. Another example of a stationary irreducible transient Markov chain with both {X _n(), 0 n < and {itX _n(),-< < n 0} ergodic but {X _n(), - < n < nonergodic is presented. In fact, it is shown that all stationary irreducible transient Markov chains {X _n(), - < n < < are nonergodic.This research was supported in part by the Office of Naval Research.John Simon Guggenheim Memorial Fellow.     

On the asymptotic and invariantσ-algebras of random walks on locally compact groups

Summary Consider a random walk of law on a locally compact second countable groupG. Let the starting measure be equivalent to the Haar measure and denote byQ the corresponding Markov measure on the space of pathsG . We study the relation between the spacesL (G , ^a ,Q) andL (G , ⁱ ,Q) where ^a and ⁱ stand for the asymptotic and invariant -algebras, respectively. We obtain a factorizationL (G , ^a ,Q) L (G , ⁱ ,Q)L (C) whereC is a cyclic group whose order (finite or infinite) coincides with the period of the Markov shift and is determined by the asymptotic behaviour of the convolution powers ⁿ.     

j-partitions for visible shorelines

Summary LetC be a compact set inR ². A setS R ² C is said to have aj-partition relative toC if and only if there existj or fewer pointsc ₁,, c _j inC such that each point ofS sees somec _i via the complement ofC. Letm, j be fixed integers, 3 m, 2 j, and writem (uniquely) asm = qj + r, where 1 r j. Assume thatC is a convexm-gon in R², withS R ² C. Forq = 0 orq = 1, the setS has aj-partition relative toC. Forq 2,S has aj-partition relative toC if and only if every (qj + 1)-member subset ofS has aj-partition relative toC, and the Helly numberqj + 1 is best possible.IfC is a disk, no such Helly number exists.     

The hypermetric cone is polyhedral

The hypermetric coneH _n is the cone in the spaceR ^n(n–1)/2 of all vectorsd=(d _ij)_1i<jn satisfying the hypermetric inequalities: –_1ijn z _j z _j d _ij 0 for all integer vectorsz inZ ⁿ with –_1in z _i =1. We explore connections of the hypermetric cone with quadratic forms and the geometry of numbers (empty spheres andL-polytopes in lattices). As an application, we show that the hypermetric coneH _n is polyhedral.