On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-Algebraic Sets

In this paper we prove new bounds on the sum of the Betti numbers of closed semi-algebraic sets and also give the first single exponential time algorithm for computing the Euler characteristic of arbitrary closed semi-algebraic sets. Given a closed semi-algebraic set S R ^k defined as the intersection of a real variety, Q=0, deg(Q)≤d, whose real dimension is k', with a set defined by a quantifier-free Boolean formula with no negations with atoms of the form P _i =0, P _i ≥ 0, P _i ≤ 0, deg(P _i ) ≤ d, 1≤ i≤ s, we prove that the sum of the Betti numbers of S is bounded by s ^k' (O(d)) ^k . This result generalizes the Oleinik—Petrovsky—Thom—Milnor bound in two directions. Firstly, our bound applies to arbitrary unions of basic closed semi-algebraic sets, not just for basic semi-algebraic sets. Secondly, the combinatorial part (the part depending on s ) in our bound, depends on the dimension of the variety rather than that of the ambient space. It also generalizes the result in [4] where a similar bound is proven for the number of connected components. We also prove that the sum of the Betti numbers of S is bounded by s ^k' 2 ^{O(k2 m4)} in case the total number of monomials occurring in the polynomials in is m. Using the tools developed for the above results, as well as some additional techniques, we give the first single exponential time algorithm for computing the Euler characteristic of arbitrary closed semi-algebraic sets. Received September 9, 1997, and in revised form March 18, 1998, and October 5, 1998.     

Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions

The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions. Specifically, if S is a set of n points in general position in R ^d , the maximum complexity of its Voronoi diagram under the L _∞ metric, and also under a simplicial distance function, are both shown to be . The upper bound for the case of the L _∞ metric follows from a new upper bound, also proved in this paper, on the maximum complexity of the union of n axis-parallel hypercubes in R ^d . This complexity is , for d ≥ 1 , and it improves to , for d ≥ 2 , if all the hypercubes have the same size. Under the L ₁ metric, the maximum complexity of the Voronoi diagram of a set of n points in general position in R ³ is shown to be . We also show that the general position assumption is essential, and give examples where the complexity of the diagram increases significantly when the points are in degenerate configurations. (This increase does not occur with an appropriate modification of the diagram definition.) Finally, on-line algorithms are proposed for computing the Voronoi diagram of n points in R ^d under a simplicial or L _∞ distance function. Their expected randomized complexities are for simplicial diagrams and for L _∞ -diagrams. Received July 31, 1995, and in revised form September 9, 1997.     

Geometrical solutions of some quadratic equations with non-real roots

This note gives geometrical/graphical methods of finding solutions of the quadratic equation ax ² + bx + c = 0, a p 0, with non-real roots. Three different cases which give rise to non-real roots of the quadratic equation have been discussed. In case I a geometrical construction and its proof for finding the solutions of the quadratic equation ax ² + bx + c = 0, a p 0, when a,b,c ] R, the set of real numbers, are presented. Case II deals with the geometrical solutions of the quadratic equation ax ² + bx + c = 0, a p 0, when b ] R, the set of real numbers; and a,c ] C, the set of complex numbers. Finally, the solutions of the quadratic equation ax ² + bx + c = 0, a p 0, when a,c ] R, the set of real numbers, and b ] C, the set of complex numbers, are presented in case III.     

Dynamics of landslide model with time delay and periodic parameter perturbations

In present paper, we analyze the dynamics of a single-block model on an inclined slope with Dieterich–Ruina friction law under the variation of two new introduced parameters: time delay T_d and initial shear stress μ. It is assumed that this phenomenological model qualitatively simulates the motion along the infinite creeping slope. The introduction of time delay is proposed to mimic the memory effect of the sliding surface and it is generally considered as a function of history of sliding. On the other hand, periodic perturbation of initial shear stress emulates external triggering effect of long-distant earthquakes or some non-natural vibration source. The effects of variation of a single observed parameter, T_d or μ, as well as their co-action, are estimated for three different sliding regimes: β < 1, β = 1 and β > 1, where β stands for the ratio of long-term to short-term stress changes. The results of standard local bifurcation analysis indicate the onset of complex dynamics for very low values of time delay. On the other side, numerical approach confirms an additional complexity that was not observed by local analysis, due to the possible effect of global bifurcations. The most complex dynamics is detected for β < 1, with a complete Ruelle–Takens–Newhouse route to chaos under the variation of T_d, or the co-action of both parameters T_d and μ. These results correspond well with the previous experimental observations on clay and siltstone with low clay fraction. In the same regime, the perturbation of only a single parameter, μ, renders the oscillatory motion of the block. Within the velocity-independent regime, β = 1, the inclusion and variation of T_d generates a transition to equilibrium state, whereas the small oscillations of μ induce oscillatory motion with decreasing amplitude. The co-action of both parameters, in the same regime, causes the decrease of block’s velocity. As for β > 1, highly-frequent, limit-amplitude oscillations of initial stress give rise to oscillatory motion. Also for β > 1, in case of perturbing only the initial shear stress, with smaller amplitude, velocity of the block changes exponentially fast. If the time delay is introduced, besides the stress perturbation, within the same regime, the co-action of T_d (T_d < 0.1) and small oscillations of μ induce the onset of deterministic chaos.     

On the commutativity of antiblocker diagrams under lift-and-project operators

The behavior of the disjunctive operator, defined by Balas, Ceria and Cornuéjols, in the context of the “antiblocker duality diagram” associated with the stable set polytope, QSTAB(G), of a graph and its complement, was first studied by Aguilera, Escalante and Nasini. The authors prove the commutativity of this diagram in any number of iterations of the disjunctive operator. One of the main consequences of this result is a generalization of the Perfect Graph Theorem under the disjunctive rank.In the same context, Lipták and Tunçel study the lift-and-project operators N₀, N and N₊ defined by Lovász and Schrijver. They find a graph for which the diagram does not commute in one iteration of the N₀- and N-operator. In connection with N₊, the authors implicitly suggest a similar result proving that if the diagram commutes in k=O(1) iterations, P=NP.In this paper, we give for any number of iterations, explicit proofs of the non commutativity of the N₀-, N- and N₊-diagram.In the particular case of the N₀- and N-operator, we find bounds for the ranks of the complements of line graphs (of complete graphs), which allow us to prove that the diagrams do not commute for these graphs.     

On Point Sets with Many Unit Distances in Few Directions

We study the problem of the maximum number of unit distances among n points in the plane, under the additional restriction that we count only those unit distances that occur in a fixed set of k directions, taking the maximum over all sets of n points and all sets of k directions. We prove that, for fixed k and sufficiently large n > n ₀ (k) , the extremal sets are essentially sections of lattices, bounded by edges parallel to the k directions and of equal length. <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p355.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received January 10, 1997, and in revised form May 16, 1997.     

On the Rate of Approximation of Closed Jordan Curves by Lemniscates

As proved by Hilbert, it is, in principle, possible to construct an arbitrarily close approximation in the Hausdorff metric to an arbitrary closed Jordan curve Γ in the complex plane {z} by lemniscates generated by polynomials P(z). In the present paper, we obtain quantitative upper bounds for the least deviations H _n (Γ) (in this metric) from the curve Γ of the lemniscates generated by polynomials of a given degree n in terms of the moduli of continuity of the conformal mapping of the exterior of Γ onto the exterior of the unit circle, of the mapping inverse to it, and of the Green function with a pole at infinity for the exterior of Γ. For the case in which the curve Γ is analytic, we prove that H _n (Γ) = O(q _n ), 0 ≤ q = q(Γ) < 1, n → ∞.__________Translated from Matematicheskie Zametki, vol. 77, no. 6, 2005, pp. 861–876.Original Russian Text Copyright ©2005 by O. N. Kosukhin.     

In between k -Sets, j -Facets, and i -Faces: (i ,j) - Partitions

   Abstract. Let S be a finite set of points in general position in R ^d . We call a pair (A,B) of subsets of S an (i,j) -partition of S if |A|=i , |B|=j and there is an oriented hyperplane h with S

The geometry of products of minors

We consider the Newton polytope Σ(m,n) of the product of all minors of an m× n matrix of indeterminates. Using the fact that this polytope is the secondary polytope of the product Δ _m-1 ×Δ _n-1 of simplices, and thus has faces corresponding to coherent polyhedral subdivisions of Δ _m-1 ×Δ _n-1 , we study facets of Σ(m,n) , which correspond to the coarsest, nontrivial such subdivisions. We make use of the relation between secondary and fiber polytopes, which in this case gives a representation of Σ(m,n) as the Minkowski average of all m × n transportation polytopes. <lsiheader> <onlinepub>7 August, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>20n2p231.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>no <sectionname> </lsiheader> Received August 7, 1996, and in revised form April 4, 1997.     

Distance matrices for points on a line,on a circle,and at the vertices of ann-dimensional cube

Forn pointsA _i ,i=1, 2, ...,n, in Euclidean space ℝ ^m , the distance matrix is defined as a matrix of the form D=(D _i ,j) _i ,j=1,...,n, where theD _i ,j are the distances between the pointsA _i andA _j . Two configurations of pointsA _i ,i=1, 2,...,n, are considered. These are the configurations of points all lying on a circle or on a line and of points at the vertices of anm-dimensional cube. In the first case, the inverse matrix is obtained in explicit form. In the second case, it is shown that the complete set of eigenvectors is composed of the columns of the Hadamard matrix of appropriate order. Using the fact that distance matrices in Euclidean space are nondegenerate, several inequalities are derived for solving the system of linear equations whose matrix is a given distance matrix. Translated fromMatematicheskie Zametki, Vol. 58, No. 1, pp. 127–138, July, 1995.     

Kinematics of Mechanisms to the Second Order – Application to the Closed Mechanisms

The degree of freedom of a closed mechanism is the dimension of a subset M of R ⁿ , M being the inverse image of the unity by the closure function f : (q ₁, ..., q _n ) f(q ₁, ..., q _n ), where q ₁, ..., q _n are the articular coordinates. We first study the regular points for the mapping f from R ⁿ into the Lie group of displacements and, second, study the singularities of the mapping f. The classical theory of mechanisms considers, often implicitly, that f is a subimmersion. Here, the calculations are made in a larger case, up to second order, and the results are then slightly different. The case of such classical mechanisms as Bennett, Bricard, and Goldberg mechanisms, justify the considerations of this more general framework and the example of a Bricard mechanism is chosen as an application of the method.     

Minimum perimeter rectangles that enclose congruent non-overlapping circles

We use computational experiments to find the rectangles of minimum perimeter into which a given number, n, of non-overlapping congruent circles can be packed. No assumption is made on the shape of the rectangles. In many of the packings found, the circles form the usual regular square-grid or hexagonal patterns or their hybrids. However, for most values of n in the tested range n≤5000, e.g., for n=7,13,17,21,22,26,31,37,38,41,43,…,4997,4998,4999,5000, we prove that the optimum cannot possibly be achieved by such regular arrangements. Usually, the irregularities in the best packings found for such n are small, localized modifications to regular patterns; those irregularities are usually easy to predict. Yet for some such irregular n, the best packings found show substantial, extended irregularities which we did not anticipate. In the range we explored carefully, the optimal packings were substantially irregular only for n of the form n=k(k+1)+1, k=3,4,5,6,7, i.e. for n=13,21,31,43, and 57. Also, we prove that the height-to-width ratio of rectangles of minimum perimeter containing packings of n congruent circles tends to 1 as n→∞.     

Points surrounding the origin

Suppose d > 2, n > d+1, and we have a set P of n points in d-dimensional Euclidean space. Then P contains a subset Q of d points such that for any p ∈ P, the convex hull of Q∪{p} does not contain the origin in its interior. We also show that for non-empty, finite point sets A ₁, ..., A _d+1 in ℝ ^d , if the origin is contained in the convex hull of A _i ∪ A _j for all 1≤i<j≤d+1, then there is a simplex S containing the origin such that |S∩A _i |=1 for every 1≤i≤d+1. This is a generalization of Bárány’s colored Carathéodory theorem, and in a dual version, it gives a spherical version of Lovász’ colored Helly theorem. Dedicated to Imre Bárány, Gábor Fejes Tóth, László Lovász, and Endre Makai on the occasion of their sixtieth birthdays. Supported by the Norwegian research council project number: 166618, and BK 21 Project, KAIST. Part of the research was conducted while visiting the Courant Institute of Mathematical Sciences. Supported by NSF Grant CCF-05-14079, and by grants from NSA, PSC-CUNY, the Hungarian Research Foundation OTKA, and BSF.     

Fujita phenomena in nonlinear pseudo-parabolic system

This paper deals with the Cauchy problem to the nonlinear pseudo-parabolic system ut-△u-αut=vp,vt-△v-αvt=uqwith p,q 1 and pq1,where the viscous terms of third order are included.We first find the critical Fujita exponent,and then determine the second critical exponent to characterize the critical space-decay rate of initial data in the co-existence region of global and non-global solutions.Moreover,time-decay profiles are obtained for the global solutions.It can be found that,diferent from those for the situations of general semilinear heat systems,we have to use distinctive techniques to treat the influence from the viscous terms of the highest order.To fix the non-global solutions,we exploit the test function method,instead of the general Kaplan method for heat systems.To obtain the global solutions,we apply the Lp-Lq technique to establish some uniform Lmtime-decay estimates.In particular,under a suitable classification for the nonlinear parameters and the initial data,various Lmtime-decay estimates in the procedure enable us to arrive at the time-decay profiles of solutions to the system.It is mentioned that the general scaling method for parabolic problems relies heavily on regularizing efect to establish the compactness of approximating solutions,which cannot be directly realized here due to absence of the smooth efect in the pseudo-parabolic system.     

Convergence of an explicit finite volume scheme for first order symmetric systems

Summary.  This paper is devoted to the derivation of a O(h ^1/2) error estimate for the classical upwind, explicit in time, finite volume scheme for linear first order symmetric systems. Such a result already existed for the corresponding implicit in time finite volume scheme, since it can be interpreted as a particular case of the space-time discontinuous Galerkin method but the technique of proof, used in that case, does not extend to explicit schemes. The general framework, recently developed to analyse the convergence rate of finite volume schemes for non linear scalar conservation laws, can not be used either, because it is not adapted for systems, even linear. In this article, we propose a new technique, which takes advantage of the linearity of the problem. The first step consists in controlling the approximation error ∥u−u _h ∥ _L2 by an expression of the form <ν _h , g>−2<μ _h , gu>, where u is the exact solution, g is a particular smooth function, and μ _h , ν _h are some linear forms depending on the approximate solution u _h . The second step consists in carefully estimating the error terms <μ _h , gu> and <ν _h , g>, by using uniform stability results for the discrete problem and regularity properties of the continuous solution. Received December 20, 2001 / Revised version received January 2, 2001 / Published online November 27, 2002 Mathematics Subject Classification (1991): 65N30     

On subgroups normalized by EO(2<Emphasis Type="Italic">l,R</Emphasis>)

It is shown that the problem of describing those subgroups in the general linear group GL(n, R) which are normalized by a classical group is much more difficult than believed previously. For the case of even orthogonal groups, a thorough level calculation is performed, which shows that, even under the assumption 2 ∈ R*, the level of a subgroup H ≤ GL(2l, R), l ≥ 3, normalized by EO(2l, R), is determined by three ideals (A, B, C) in R rather than by two ideals, as was generally believed. These ideals are related by C ² ≤ A = B ∩ C, and triples of such ideals are said to be admissible. Here, A is the level of H with respect to the linear transvections t _ij (ξ), and B is the level of H with respect to the orthogonal transvections T _ij (ξ). The definition of the third level component is a little more complicated. In an appropriate realization, the Lie algebra of the even orthogonal group consists of matrices antisymmetric with respect to the skew diagonal. The component C is the level of H with respect to the complementary invariant subspace, which consists of matrices symmetric with respect to the skew diagonal. With any admissible triple (A, B, C) we associate a relative elementary subgroup EEO(2l, R, A, B, C), which is normalized by EO(2l, R) and, moreover, is EO(2l, R)-perfect.     

Le rapport di isou (Euclide V, définition 17): Définition, utilisation, transmission

Dans le livre V des Eléments d'Euclide, la définition 17, du di isou logos, se compose de deux énoncés juxtaposés, qui ne sont pas équivalents. Le premier étant une simple réfection du théorème V,22, il convient de regarder le second seul comme authentique, comme le suggérent aussi bien l'emploi de l'expression di isou en géométrie grecque, que l'analyse précise de la tradition indirecte. En conséquence, la définition 17 doit être débarrassée de sa première partie; la définition 18.1, celle de la proportion réglée, doit être restituée comme authentique; la définition 18.2, de la proportion déréglée, doit être réduite à son libellé original, analogue à celui de 18.1.In Euclid's Elements V, Definition 17 (di isou logos) consists of two statements, which are not equivalent. The first one being a remake of theorem V,22, the second is the only one to be taken as genuine. This can be proved by the use of the expression di isou in Greek geometry, and also by a close scrutiny of the various witnesses of this part of the text. Consequently, Definition 17 should be cleared of its first part; Definition 18.1, of the ordered proportion, should be restored as genuine; Definition 18.2, of the perturbed proportion, should be reduced to its original core, and made similar to 18.1.     

On the maximum of the generalized Brownian bridge

We present some extensions of the distributions of the maximum of the Brownian bridge in [0,t] when the conditioning event is placed at a future timeu>t or at an intermediate timeu<t. The standard distributions of Brownian motion and Brownian bridge are obtained as limiting cases. These results permit us to derive also the distribution of the first-passage time of the Brownian bridge. Similar generalizations are carried out for the Brownian bridge with drift μ; in this case, it is shown that the maximal distribution is independent of μ (whenu≥t). Finally, the case of the two-sided maximal distribution of Brownian motion in [0,t], conditioned onB(u)=η (for bothu>t andu<t), is considered. Dip. di Statistica, Probabilità e Stat. Applicate, Università di Roma “La Sapienza,” Piazzale Aldo Moros, 00185 Roma, Italy. Published in Lietuvos Matematikos Rinkinys, Vol. 39, No. 2, pp. 200–213, April–June, 1999.