Monotonicity of the cd-index for polytopes

We prove that the cd-index of a convex polytope satisfies a strong monotonicity property with respect to the cd-indices of any face and its link. As a consequence, we prove for d-dimensional polytopes a conjecture of Stanley that the cd-index is minimized on the d-dimensional simplex. Moreover, we prove the upper bound theorem for the cd-index, namely that the cd-index of any d-dimensional polytope with n vertices is at most that of C(n,d), the d-dimensional cyclic polytope with n vertices. Received September 29, 1998; in final form February 8, 1999     

Local properties of gaussian random fields on compact symmetric spaces and theorems of the Jackson-Bernstein type

We consider local properties of smaple functions of Gaussian isotropic random fields on compact Riemannian symmetric spacesM of rank 1. We give conditions under which the sample functions of a field almost surely possess logarithmic and power modulus of continuity. As a corollary, we prove a theorem of the Bernstein type for optimal approximations of functions of this sort by harmonic polynomials in the metric of the spaceL ₂(M). We use theorems of the Jackson-Bernstein-type to obtain sufficient conditions for the sample functions of a field to almost surely belong to the classes of functions associated with the Riesz and Cesàro means. International Mathematical Center, Ukrainian Academy of Sciences, Kiev. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 51, No. 1, pp. 60–68, January, 1999.     

Embedding a polytope in a lattice

We present a special similarity ofR ⁴ⁿ which maps lattice points into lattice points. Applying this similarity, we prove that if a (4n−1)-polytope is similar to a lattice polytope (a polytope whose vertices are all lattice points) inR ⁴ⁿ , then it is similar to a lattice polytope inR ⁴ⁿ⁻¹, generalizing a result of Schoenberg [4]. We also prove that ann-polytope is similar to a lattice polytope in someR ^N if and only if it is similar to a lattice polytope inR ²ⁿ⁺¹, and if and only if sin²(<ABC) is rational for any three verticesA, B, C of the polytope.     

How many cyclic subpolytopes can a non-cyclic polytope have?

Acyclic d-polytope is ad-polytope that is combinatorially equivalent to a polytope whose vertices lie on the moment curve {(t, t ², …,t ^d):t∈R}. Every subpolytope of an even-dimensional cyclic polytope is again cyclic. We show that a polytope [or neighborly polytope] withv vertices that is not cyclic has at mostd+1 [respectivelyd]d-dimensional cyclic subpolytopes withv−1 vertices, providedd is even andv≧d+5.     

Convergence of random zeros on complex manifolds

We show that the zeros of random sequences of Gaussian systems of polynomials of in- creasing degree almost surely converge to the expected limit distribution under very general hypotheses. In particular,the normalized distribution of zeros of systems of m polynomials of degree N,orthonor- malized on a regular compact set K(?)C~m,almost surely converge to the equilibrium measure on K as N→∞.     

When almost all sets are difference dominated

We investigate the relationship between the sizes of the sum and difference sets attached to a subset of {0,1,…,N}, chosen randomly according to a binomial model with parameter p(N), with N^?1 = o(p(N)). We show that the random subset is almost surely difference dominated, as N → ∞, for any choice of p(N) tending to zero, thus confirming a conjecture of Martin and O'Bryant. The proofs use recent strong concentration results. Furthermore, we exhibit a threshold phenomenon regarding the ratio of the size of the difference to the sumset. If p(N) = o(N^?1/2) then almost all sums and differences in the random subset are almost surely distinct and, in particular, the difference set is almost surely about twice as large as the sumset. If N^?1/2 = o(p(N)) then both the sum and difference sets almost surely have size (2N + 1) ? O(p(N)^?2), and so the ratio in question is almost surely very close to one. If p(N) = c · N^?1/2 then as c increases from zero to infinity (i.e., as the threshold is crossed), the same ratio almost surely decreases continuously from two to one according to an explicitly given function of c. We also extend our results to the comparison of the generalized difference sets attached to an arbitrary pair of binary linear forms. For certain pairs of forms f and g, we show that there in fact exists a sharp threshold at c_f,g · N^?1/2, for some computable constant c_f,g, such that one form almost surely dominates below the threshold and the other almost surely above it. The heart of our approach involves using different tools to obtain strong concentration of the sizes of the sum and difference sets about their mean values, for various ranges of the parameter p. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Cutting Polytopes and Flag f-Vectors

We show how the flag f -vector of a polytope changes when cutting off any face, generalizing work of Lee for simple polytopes. The result is in terms of explicit linear operators on cd-polynomials. Also, we obtain the change in the flag f -vector when contracting any face of the polytope. Received July 13, 1998, and in revised form April 14, 1999.     

Cubical 4-Polytopes with Few Vertices

A cubical polytope is a convex polytope all of whose facets are conbinatorial cubes. A d-polytope Pis called almost simple if, in the graph of P, each vertex of Pis d-valent of (d+ 1)-valent. It is known that, for d> 4, all but one cubical d-polytopes with up to 2^d+1vertices are almost simple, which provides a complete enumeration of all the cubical d-polytopes with up to 2^d+1vertices. We show that this result is also true for d=4.     

Cubical d-Polytopes with Few Vertices for d>4

A cubical polytope is a convex polytope all of whose facets are combinatorial cubes. A d-polytope P is called almost simple if, in the graph of P, each vertex of P is d-valent or (d+1)-valent. We show that, for d>4, all but one cubicald -polytopes with up to 2 ^d+1 vertices are almost simple. This provides a complete enumeration of all the cubical d-polytopes with up to 2 ^d+1 vertices, for d>4.     

On convex bodies that permit packings of high density

It is well known that ann-dimensional convex body permits a lattice packing of density 1 only if it is a centrally symmetric polytope of at most 2(2 ⁿ –1) facets. This article concerns itself with the associated stability problem whether a convex body that permits a packing of high density is in some sense close to such a polytope. Several inequalities that address this stability problem are proved. A corresponding theorem for coverings by two-dimensional convex bodies is also proved.Supported by National Science Foundation Research Grants DMS 8300825 and DMS 8701893.     

Equipartite polytopes

A polytope P with 2n vertices is called equipartite if for any partition of its vertex set into two equal-size sets V ₁ and V ₂, there is an isometry of the polytope P that maps V ₁ onto V ₂. We prove that an equipartite polytope in ℝ ^d can have at most 2d+2 vertices. We show that this bound is sharp and identify all known equipartite polytopes in ℝ ^d . We conjecture that the list is complete.     

Sharp concentration of the chromatic number on random graphsG n,p

The distribution of the chromatic number on random graphsG _{n, p} is quite sharply concentrated. For fixedp it concentrates almost surely in √n ω(n) consecutive integers where ω(n) approaches infinity arbitrarily slowly. If the average degreepn is less thann ^1/6, it concentrates almost surely in five consecutive integers. Large deviation estimates for martingales are used in the proof.     

The central limit theorem for Markov chains started at a point

 The aim of this paper is to prove a central limit theorem and an invariance principle for an additive functional of an ergodic Markov chain on a general state space, with respect to the law of the chain started at a point. No irreducibility assumption nor mixing conditions are imposed; the only assumption bears on the growth of the L ² -norms of the ergodic sums for the function generating the additive functional, which must be with . The result holds almost surely with respect to the invariant probability of the chain. Received: 17 October 2001 / Revised version: 5 April 2002 / Published Online: 24 October 2002 Mathematics Subject Classification (2000): 60F05, 60J05     

Lois fortes des grands nombres presque sûres pour les sommes de Riesz–Raikov

The classical theorem of Riesz and Raikov states that if a > 1 is an integer and ƒ is a function in L ¹(ℝ/ℤ), then the averages

On the regularity of the distribution of the maximum of one-parameter Gaussian processes

The main result in this paper states that if a one-parameter Gaussian process has C ^2k paths and satisfies a non-degeneracy condition, then the distribution of its maximum on a compact interval is of class C ^k . The methods leading to this theorem permit also to give bounds on the successive derivatives of the distribution of the maximum and to study their asymptotic behaviour as the level tends to infinity. Received: 14 May 1999 / Revised version: 18 October 1999 / Published online: 14 December 2000     

On the Universal Partition Theorem for 4-Polytopes

By means of sign-patterns any finite family of polynomials induces a decomposition of R ⁿ into basic semialgebraic sets. In case of integer coefficients the latter decomposition roughly appears to be a partition into realization spaces of 4 -polytopes. The latter is stated by the Universal Partition Theorem for 4 -polytopes by Richter-Gebert. The present paper presents a different proof. As its main tool, the von Staudt polytope is introduced. The von Staudt polytope constitutes the polytopal equivalent of the well-known von Staudt constructions for point configurations. With the aid of the von Staudt polytope the original ideas of universality theory can be directly applied to the polytopal case. Moreover, a new method for representing real values (on a computation line) by polytopal means is presented. This method implies a bundling strategy in order to duplicate the encoded information. Based on this approach, the following complexity result is obtained. The incidence code of a polytope, exhibiting a realization space equivalent to a given semialgebraic set, can be computed in the same time that it requires to generate the defining polynomial system. Received December 19, 1995, and in revised form December 16, 1996, April 28, 1997, and September 10, 1997.     

Random polytopes: Their definition,generation and aggregate properties

The definition of random polytope adopted in this paper restricts consideration to those probability measures satisfying two properties. First, the measure must induce an absolutely continuous distribution over the positions of the bounding hyperplanes of the random polytope; and second, it must result in every point in the space being equally as likely as any other point of lying within the random polytope. An efficient Monte Carlo method for their computer generation is presented together with analytical formulas characterizing their aggregate properties. In particular, it is shown that the expected number of extreme points for such random polytopes increases monotonically in the number of constraints to the limiting case of a polytope topologically equivalent to a hypercube. The implied upper bound of 2 ⁿ wheren is the dimensionality of the space is significantly less than McMullen's attainable bound on the maximal number of vertices even for a moderate number of constraints.     

On the errors committed by sequences of estimator functionals

Consider a sequence of estimators [^(q)] _n\hat \theta _n which converges almost surely to θ ₀ as the sample size n tends to infinity. Under weak smoothness conditions, we identify the asymptotic limit of the last time [^(q)] _n\hat \theta _n is further than ɛ away from θ ₀ when ɛ → 0⁺. These limits lead to the construction of sequentially fixed width confidence regions for which we find analytic approximations. The smoothness conditions we impose is that [^(q)] _n\hat \theta _n is to be close to a Hadamard-differentiable functional of the empirical distribution, an assumption valid for a large class of widely used statistical estimators. Similar results were derived in Hjort and Fenstad (1992) for the case of Euclidean parameter spaces; part of the present contribution is to lift these results to situations involving parameter functionals. The apparatus we develop is also used to derive appropriate limit distributions of other quantities related to the far tail of an almost surely convergent sequence of estimators, like the number of times the estimator is more than ɛ away from its target. We illustrate our results by giving a new sequential simultaneous confidence set for the cumulative hazard function based on the Nelson-Aalen estimator and investigate a problem in stochastic programming related to computational complexity.     

Conical equipartitions of mass distributions

A conical dissection of R ^d is a decomposition of the space into polyhedral cones. An example of a conical dissection is a fan associated to the faces of a convex polytope. Motivated by some recent questions and results about (simultaneous) conical partitions of measures by Kaneko and Kano, Bárány and Matoušek, and Bespamyatnikh et al. [2], [4], [19], we study related partition problems in higher dimensions. In the case of a single measure, several conical partition results associated to a nondegenerated pointed simplex (Δ,a) in R ⁿ are obtained with the aid of the Brouwer fixed point theorem. In the other direction, it is demonstrated that general ``symmetrical' equipartition results [21] may be used to yield, by appropriate specialization, fairly general ``asymmetric,' conical equipartitions for two or more mass distributions. Finally, the topological nature of these results is exemplified by their extension to the case of topological (projective) planes. Received December 2, 1999, and in revised form July 1, 2000. Online publication Feburary 1, 2001.     

Interpolation of nonlinear functionals by integral continued fractions

We constructively prove the theorem of existence of an interpolation integral chain fraction for a nonlinear functionalF:Q[0,1]→R ¹. Kiev University, Kiev. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 51, No. 3, pp. 364–375, March, 1999.