Volume approximation of smooth convex bodies by three-polytopes of restricted number of edges

For a given convex body K in with C ² boundary, let P ^c _n be the circumscribed polytope of minimal volume with at most n edges, and let P ⁱ _n be the inscribed polytope of maximal volume with at most n edges. Besides presenting an asymptotic formula for the volume difference as n tends to infinity in both cases, we prove that the typical faces of P ^c _n and P ⁱ _n are asymptotically regular triangles and squares, respectively, in a suitable sense. Supported by OTKA grants 043520 and 049301, and by the EU Marie Curie grants Discconvgeo, Budalggeo and PHD. Authors’ addresses: Károly J. B?r?czky, Alfréd Rényi Institute of Mathematics, P.O. Box 127, Budapest H–1364, Hungary, and Department of Geometry, Roland E?tv?s University, Pázmány Péter sétány 1/C, Budapest 1117, Hungary; Salvador S. Gomis, Department of Mathematical Analysis, University of Alicante, 03080 Alicante, Spain; Péter Tick, Gyűrű utca 24, Budapest H–1039, Hungary     

A rigidity theorem for the pair ${\cal q}{\Bbb C} P^n$ (complex hyperquadric, complex projective space)

Given a compact Kähler manifold M of real dimension 2n, let P be either a compact complex hypersurface of M or a compact totally real submanifold of dimension n. Let q\cal q (resp. \Bbb R Pⁿ{\Bbb R} P^n) be the complex hyperquadric (resp. the totally geodesic real projective space) in the complex projective space \Bbb C Pⁿ{\Bbb C} P^n of constant holomorphic sectional curvature 4l \lambda . We prove that if the Ricci and some (n-1)-Ricci curvatures of M (and, when P is complex, the mean absolute curvature of P) are bounded from below by some special constants and volume (P) / volume (M) ￡\leq volume (q\cal q)/ volume (\Bbb C Pⁿ)({\Bbb C} P^n) (resp. ￡\leq volume (\Bbb R Pⁿ)({\Bbb R} P^n) / volume (\Bbb C Pⁿ)({\Bbb C} P^n)), then there is a holomorphic isometry between M and \Bbb C Pⁿ{\Bbb C} P^n taking P isometrically onto q\cal q (resp. \Bbb R Pⁿ{\Bbb R} P^n). We also classify the Kähler manifolds with boundary which are tubes of radius r around totally real and totally geodesic submanifolds of half dimension, have the holomorphic sectional and some (n-1)-Ricci curvatures bounded from below by those of the tube \Bbb R Pⁿ_r{\Bbb R} P^n_r of radius r around \Bbb R Pⁿ{\Bbb R} P^n in \Bbb C Pⁿ{\Bbb C} P^n and have the first Dirichlet eigenvalue not lower than that of \Bbb R Pⁿ_r{\Bbb R} P^n_r.     

A Blichfeldt-type inequality for the surface area

In 1921, Blichfeldt gave an upper bound on the number of integral points contained in a convex body in terms of the volume of the body. More precisely, he showed that #(K?\Bbb Zⁿ) ￡ n! vol(K)+n\#(K\cap{\Bbb Z}^n)\le n! {\rm vol}(K)+n , whenever K ì \Bbb RⁿK\subset{\Bbb R}^n is a convex body containing n + 1 affinely independent integral points. Here we prove an analogous inequality with respect to the surface area F(K), namely #(K?\Bbb Zⁿ) < vol(K) + ((?n+1)/2) (n-1)! F(K)\#(K\cap{\Bbb Z}^n) < {\rm vol}(K) + ((\sqrt{n}+1)/2) (n-1)! {\rm F}(K) . The proof is based on a slight improvement of Blichfeldt’s bound in the case when K is a non-lattice translate of a lattice polytope, i.e., K = t + P, where t ? \Bbb Rⁿ\\Bbb Zⁿt\in{\Bbb R}^n\setminus{\Bbb Z}^n and P is an n-dimensional polytope with integral vertices. Then we have #((t+P)?\Bbb Zⁿ) ￡ n! vol(P)\#((t+P)\cap{\Bbb Z}^n)\le n! {\rm vol}(P) . Moreover, in the 3-dimensional case we prove a stronger inequality, namely #(K?\Bbb Zⁿ) < vol(K) + 2 F(K)\#(K\cap{\Bbb Z}^n)< {\rm vol}(K) + 2 {\rm F}(K) .     

On the singularities of residual intertwining operators

Let G be a reductive algebraic group defined over \Bbb Q {\Bbb Q} . Let P, P' be parabolic subgroups of G, defined over \Bbb Q {\Bbb Q} , and let _boxclose_boxclose, a_P') t \in W({\frak a}_{P}, {\frak a}_{P'}) . In this paper we study the intertwining operator M_P￠|P(t,l), l ? \frak a^*_{P,\Bbb C} M_{P' \vert P}(t,\lambda),\,\lambda \in {\frak a}^*_{P,{\Bbb C}} , acting in corresponding spaces of automorphic forms. One of the main results states that each matrix coefficient of M_P￠|P(t,l) M_{P' \vert P}(t,\lambda) is a meromorphic function of order ￡ n + 1 \le n + 1 , where n = dim G. Using this result, we further investigate the rank one intertwining operators, in particular, we study the distribution of their poles.     

Polytopes of partitions of numbers

We study the vertices and facets of the polytopes of partitions of numbers. The partition polytope P_n is the convex hull of the set of incidence vectors of all partitions n=x₁+2x₂++nx_n. We show that the sequence P₁,P₂,…,P_n,… can be treated as an embedded chain. The dynamics of behavior of the vertices of P_n, as n increases, is established. Some sufficient and some necessary conditions for a point of P_n to be its vertex are proved. Representation of the partition polytope as a polytope on a partial algebra—which is a generalization of the group polyhedron in the group theoretic approach to the integer linear programming—allows us to prove subadditive characterization of the nontrivial facets of P_n. These facets correspond to extreme rays of the cone of subadditive functions with additional requirements p₀=p_n and p_i+p_n−i=p_n,1≤i<n. The trivial facets are explicitly indicated. We also show how all vertices and facets of the polytopes of constrained partitions—in which some numbers are forbidden to participate—can be obtained from those of the polytope P_n. All vertices and facets of P_n for n≤8 and n≤6, respectively, are presented.     

Packing,covering and decomposing of a complete uniform hypergraph into delta-systems

Anh-uniform hypergraph generated by a set of edges {E ₁,...,E _c} is said to be a delta-system Δ(p,h,c) if there is ap-element setF such that ∇F|=p andE _i⌢E _j=F,∀i≠j. The main result of this paper says that givenp, h andc, there isn ₀ such that forn≥n ₀ the set of edges of a completeh-uniform hypergraphK _n ^h can be partitioned into subsets generating isomorphic delta-systems Δ(p, h, c) if and only if . This result is derived from a more general theorem in which the maximum number of delta-systems Δ(p, h, c) that can be packed intoK _n ^h and the minimum number of delta-systems Δ(p, h, c) that can cover the edges ofK _n ^h are determined for largen. Moreover, we prove a theorem on partitioning of the edge set ofK _n ^h into subsets generating small but not necessarily isomorphic delta-systems.     

Embedding Planar Graphs at Fixed Vertex Locations

 Let G be a planar graph of n vertices, v ₁,…,v _n , and let {p ₁,…,p _n } be a set of n points in the plane. We present an algorithm for constructing in O(n ²) time a planar embedding of G, where vertex v _i is represented by point p _i and each edge is represented by a polygonal curve with O(n) bends (internal vertices). This bound is asymptotically optimal in the worst case. In fact, if G is a planar graph containing at least m pairwise independent edges and the vertices of G are randomly assigned to points in convex position, then, almost surely, every planar embedding of G mapping vertices to their assigned points and edges to polygonal curves has at least m/20 edges represented by curves with at least m/40³ bends. Received: May 24, 1999 Final version received: April 10, 2000     

Equality of two variable weighted means: reduction to differential equations

Summary. Let F, Y \Phi, \Psi be strictly monotonic continuous functions, F,G be positive functions on an interval I and let n ? \Bbb N \{1} n \in {\Bbb N} \setminus \{1\} . The functional equation¶¶F^-1 ([(?_i=1ⁿF(x_i)F(x_i))/(?_i=1ⁿ F(x_i)]) Y^-1 ([(?_i=1ⁿY(x_i)G(x_i))/(?_i=1ⁿ G(x_i))])  (x₁,?,x_n ? I) \Phi^{-1}\,\left({\sum\limits_{i=1}^{n}\Phi(x_{i})F(x_{i})\over\sum\limits_{i=1}^{n} F(x_{i}}\right) \Psi^{-1}\,\left({\sum\limits_{i=1}^{n}\Psi(x_{i})G(x_{i})\over\sum\limits_{i=1}^{n} G(x_{i})}\right)\,\,(x_{1},\ldots,x_{n} \in I) ¶was solved by Bajraktarevi' [3] for a fixed n 3 3 n\ge 3 . Assuming that the functions involved are twice differentiable he proved that the above functional equation holds if and only if¶¶Y(x) = [(aF(x) + b)/(cF(x) + d)],       G(x) = kF(x)(cF(x) + d) \Psi(x) = {a\Phi(x)\,+\,b\over c\Phi(x)\,+\,d},\qquad G(x) = kF(x)(c\Phi(x) + d) ¶where a,b,c,d,k are arbitrary constants with k(c²+d²)(ad-bc) 1 0 k(c^2+d^2)(ad-bc)\ne 0 . Supposing the functional equation for all n = 2,3,... n = 2,3,\dots Aczél and Daróczy [2] obtained the same result without differentiability conditions.¶The case of fixed n = 2 is, as in many similar problems, much more difficult and allows considerably more solutions. Here we assume only that the same functional equation is satisfied for n = 2 and solve it under the supposition that the functions involved are six times differentiable. Our main tool is the deduction of a sixth order differential equation for the function j = F°Y^-1 \varphi = \Phi\circ\Psi^{-1} . We get 32 new families of solutions.     

Representations of nilpotent Lie algebras

Let (L,[p]) a finite dimensional nilpotent restricted Lie algebra of characteristic p 3 3, c ? L^*p \geq 3, \chi \in L^* a linear form. In this paper we study the representation theory of the reduced universal enveloping algebra u(L,c)u(L,\chi ). It is shown that u(L,c)u(L,\chi ) does not admit blocks of tame representation type. As an application, we prove that the nonregular AR-components of u(L,c)u(L,\chi ) are of types \Bbb Z [A_￥ ]\Bbb Z [A_\infty ] or \Bbb Z [A_n]/(t)\Bbb Z [A_n]/(\tau ).     

Numerical properties of Chern classes of certain covering manifolds

In this paper, we study numerical properties of Chern classes of certain covering manifolds. One of the main results is the following: Let ψ : X → Pⁿ be a finite covering of the n-dimensional complex projective space branched along a hypersurface with only simple normal crossings and suppose X is nonsingular. Let c_i(X) be the i-th Chern class of X. Then (i) if the canonical divisor K_X is numerically effective, then (−1)^kc_k(X) (k ≥ 2) is numerically positive, and (ii) if X is of general type, then (−1)ⁿcⁱ_l (X) cⁱ_r, (X) > 0, where i_l + … + i_r = n. Furthermore we show that the same properties hold for certain Kummer coverings.     

Rates of convergence for classes of functions: The non-i.i.d. case

Let X_i, i ≥ 1, be a sequence of φ-mixing random variables with values in a sample space (X, A). Let L(X_i) = P_(i) for all i ≥ 1 and let _n, n ≥ 1, be classes of real-valued measurable functions on (X, A). Given any function g on (X, A), let S_n(g) = Σ_{i = 1}ⁿ {g(X_i) − Eg(X_i)}. Under weak metric entropy conditions on _n and under growth conditions on both the mixing coefficients and the maximal variance V V(n) max_{i ≤ n} sup_{g n} ∫ g² dP_(i), we show that there is a numerical constant U < ∞ such that

Full-size image

a.s. ^*, where _{i = 1}^xP_(i) and H H(n) is the square root of the entropy of the class _n. Additionally, the rate of convergence H⁻¹(n/V)^1/2 cannot, in general, be improved upon. Applications of this result are considered.     

A Characteristic Property of Injective Holomorphic Germs

Let X ₀ be the germ at 0 of a complex variety and let f: X₀? \Bbb Cⁿ₀f:\ X_0\rightarrow {\Bbb C}^n_0 be a holomorphic germ. We say that f is pseudoimmersive if for any g: \Bbb R₀? X₀g:\ {\Bbb R}_0\rightarrow X_0 such that f °g ? C^￥ f \circ g \in C^{\infty} , we have g ? C^￥g\in C^{\infty} . We prove that f is pseudoimmersive if and only if it is injective. Some results about the real case are also considered.     

Lagrangian barriers and symplectic embeddings

We prove that every symplectic Kähler manifold (M;W) (M;\Omega) with integral [W] [\Omega] decomposes into a disjoint union (M,W) = (E,w₀) \coprod D (M,\Omega) = (E,\omega_0) \coprod \Delta , where (E,w₀) (E,\omega_0) is a disc bundle endowed with a standard symplectic form w₀ \omega_0 and D \Delta is an isotropic CW-complex. We perform explicit computations of this decomposition on several examples.¶As an application we establish the following symplectic intersection phenomenon: There exist symplectically irremovable intersections between contractible domains and Lagrangian submanifolds. For example, we prove that every symplectic embedding j:B²ⁿ(l) ? \Bbb CPⁿ \varphi:B^{2n}(\lambda) \to {\Bbb C}P^n of a ball of radius l² 3 1/2 \lambda^2 \ge 1/2 must intersect the standard Lagrangian real projective space \Bbb RPⁿ ì \Bbb CPⁿ {\Bbb R}P^n \subset {\Bbb C}P^n .     

Punishing Factors for Finitely Connected Domains

Let Ω and Π be two finitely connected hyperbolic domains in the complex plane \Bbb C{\Bbb C} and let R(z, Ω) denote the hyperbolic radius of Ω at z and R(w, Π) the hyperbolic radius of Π at w. We consider functions f that are analytic in Ω and such that all values f(z) lie in the domain Π. This set of analytic functions is denoted by A(Ω, Π). We prove among other things that the quantities C_n(W,P) := sup_{f ? A(W,P)}sup_{z ? W}\frac|f⁽ⁿ⁾(z)| R(f(z),P)n! (R(z,W))ⁿC_n(\Omega,\Pi)\,:=\,\sup_{f\in A(\Omega,\Pi)}\sup_{z\in \Omega}\frac{\vert f^{(n)}(z)\vert\,R(f(z),\Pi)}{n!\,(R(z,\Omega))^n} are finite for all n ? \Bbb N{n \in {\Bbb N}} if and only if ∂Ω and ∂Π do not contain isolated points.     

Covering the vertices of a graph by cycles of prescribed length

The main theorem of that paper is the following: let G be a graph of order n, of size at least (n² - 3n + 6)/2. For any integers k, n₁, n₂,…,n_k such that n = n₁ + n₂ +. + n_k and n_i ? 3, there exists a covering of the vertices of G by disjoint cycles (C_i) =l…k with |C_i| = ni, except when n = 6, n₁ = 3, n₂ = 3, and G is isomorphic to G₁, the complement of G₁ consisting of a C₃ and a stable set of three vertices, or when n = 9, n₁ = n₂ = n₃ = 3, and G is isomorphic to G₂, the complement of G₂ consisting of a complete graph on four vertices and a stable set of five vertices. We prove an analogous theorem for bipartite graphs: let G be a bipartite balanced graph of order 2n, of size at least n² - n + 2. For any integers s, n₁, n₂,…,n_s with n_i ? 2 and n = n₁ + n₂ + ? + n_s, there exists a covering of the vertices of G by s disjoint cycles C_i, with |C_i| = 2n_i.     

Covering Complete Hypergraphs with Cuts of Minimum Total Size

A cut [X, V − X] in a hypergraph with vertex-set V is the set of all edges that meet both X and V − X. Let s _r (n) denote the minimum total size of any cover of the edges of the complete r-uniform hypergraph on n vertices K_n^r{K_n^r} by cuts. We show that there is a number n _r such that for every n > n _r , s _r (n) is uniquely achieved by a cover with ?\fracn-1r-1?{\lfloor \frac{n-1}{r-1}\rfloor} cuts [X _i , V − X _i ] such that the X _i are pairwise disjoint sets of size at most r − 1. We show that c₁r2^r < n_r < c₂r⁵2^r{c_1r2^r < n_r < c_2r^52^r} for some positive absolute constants c ₁ and c ₂. Using known results for s ₂(n) we also determine s ₃(n) exactly for all n.     

About the error term for best approximation with respect to the Hausdorff related metrics

Let M be a convex body with C ³ ₊ boundary in \Bbb R ^d , d\geq 3 , and consider a polytope P _n (or P _(n) ) with at most n vertices (at most n facets) minimizing the Hausdorff distance from M . It has long been known that as n tends to infinity, there exist asymptotic formulae of order n ^-2/(d-1) for the Hausdorff distances δ _{\rm H} (P _n ,M) and δ _{\rm H} (P _(n) ,M) . In this paper a bound of order n ^-5/(2(d-1)) is given for the error of the asymptotic formulae. This bound is clearly not the best possible, and Gruber \cite{Gru97} conjectured that if the boundary of M is sufficiently smooth, then there exist asymptotic expansions for δ _{\rm H} (P _n ,M) and δ _{\rm H} (P _(n) ,M) . With the help of quasiconformal mappings, we show for the three-dimensional unit ball that the error is at least f(n)⋅ n ^-2 where f(n) tends to infinity. Therefore in this case, no asymptotic expansion exists in terms of n ^-2/(d-1) =n ^-1 . Received April 25, 1999, and in revised form January 20, 2000, and May 31, 2000. Online publication January 17, 2001.     

Lattice Polytopes with Distinct Pair-Sums

Let P be a lattice polytope in R ⁿ , and let P \cap Z ⁿ = {v ₁ ,\ldots,v _N } . If the N + N\choose 2 points 2v ₁ ,\ldots, 2v _N ;v ₁ +v ₂ ,\ldots, v _N-1 + v _N are distinct, we say that P is a ``distinct pair-sum' or ``dps' polytope. We show that if P is a dps polytope in R ⁿ , then N≤ 2 ⁿ , and, for every n , we construct dps polytopes in R ⁿ which contain 2 ⁿ lattice points. We also discuss the relation between dps polytopes and the study of sums of squares of real polynomials. Received November 10, 2000, and in revised form June 28, 2001. Online publication November 2, 2001.     

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.