A Sharper Estimate on the Betti Numbers of Sets Defined by Quadratic Inequalities

In this paper we consider the problem of bounding the Betti numbers, b _i (S), of a semi-algebraic set S⊂ℝ ^k defined by polynomial inequalities P ₁≥0,…,P _s ≥0, where P _i ∈ℝ[X ₁,…,X _k ], s<k, and deg (P _i )≤2, for 1≤i≤s. We prove that for 0≤i≤k−1,

Different Bounds on the Different Betti Numbers of Semi-Algebraic Sets

   Abstract. A classic result in real algebraic geometry due to Oleinik—Petrovskii, Thom and Milnor, bounds the topological complexity (the sum of the Betti numbers) of basic semi-algebraic sets. This bound is tight as one can construct examples having that many connected components. However, till now no significantly better bounds were known on the individual higher Betti numbers. We prove better bounds on the individual Betti numbers of basic semi-algebraic sets, as well as arrangements of algebraic hypersurfaces. As a corollary we obtain a polynomial bound on the highest Betti numbers of basic semi-algebraic sets defined by quadratic inequalities.     

Different Bounds on the Different Betti Numbers of Semi-Algebraic Sets

Abstract. A classic result in real algebraic geometry due to Oleinik—Petrovskii, Thom and Milnor, bounds the topological complexity (the sum of the Betti numbers) of basic semi-algebraic sets. This bound is tight as one can construct examples having that many connected components. However, till now no significantly better bounds were known on the individual higher Betti numbers. We prove better bounds on the individual Betti numbers of basic semi-algebraic sets, as well as arrangements of algebraic hypersurfaces. As a corollary we obtain a polynomial bound on the highest Betti numbers of basic semi-algebraic sets defined by quadratic inequalities.     

On Projections of Semi-Algebraic Sets Defined by Few Quadratic Inequalities

Let S⊂ℝ ^k+m be a compact semi-algebraic set defined by P ₁≥0,…,P _ℓ ≥0, where P _i ∈ℝ[X ₁,…,X _k ,Y ₁,…,Y _m ], and deg (P _i )≤2, 1≤i≤ℓ. Let π denote the standard projection from ℝ ^k+m onto ℝ ^m . We prove that for any q>0, the sum of the first q Betti numbers of π(S) is bounded by (k+m) ^{O(q ℓ)}. We also present an algorithm for computing the first q Betti numbers of π(S), whose complexity is . For fixed q and ℓ, both the bounds are polynomial in k+m. The author was supported in part by an NSF Career Award 0133597 and a Sloan Foundation Fellowship.     

Computing the Top Betti Numbers of Semialgebraic Sets Defined by Quadratic Inequalities in Polynomial Time

For any ℓ>0, we present an algorithm which takes as input a semi-algebraic set, S, defined by P ₁≤0,…,P _s ≤0, where each P _i ∈R[X ₁,…,X _k ] has degree≤2, and computes the top ℓ Betti numbers of S, b _k−1(S),…,b _k−ℓ (S), in polynomial time. The complexity of the algorithm, stated more precisely, is . For fixed ℓ, the complexity of the algorithm can be expressed as , which is polynomial in the input parameters s and k. To our knowledge this is the first polynomial time algorithm for computing nontrivial topological invariants of semialgebraic sets in R ^k defined by polynomial inequalities, where the number of inequalities is not fixed and the polynomials are allowed to have degree greater than one. For fixed s, we obtain, by letting ℓ=k, an algorithm for computing all the Betti numbers of S whose complexity is . An erratum to this article can be found at     

<Emphasis Type="Italic">P</Emphasis>-orderings of finite subsets of Dedekind domains

If R is a Dedekind domain, P a prime ideal of R and S⊆R a finite subset then a P-ordering of S, as introduced by M. Bhargava in (J. Reine Angew. Math. 490:101–127, 1997), is an ordering {a _i } _i=1 ^m of the elements of S with the property that, for each 1<i≤m, the choice of a _i minimizes the P-adic valuation of ∏ _j<i (s−a _j ) over elements s∈S. If S, S ^′ are two finite subsets of R of the same cardinality then a bijection φ:S→S ^′ is a P-ordering equivalence if it preserves P-orderings. In this paper we give upper and lower bounds for the number of distinct P-orderings a finite set can have in terms of its cardinality and give an upper bound on the number of P-ordering equivalence classes of a given cardinality.     

Generalized Ham-Sandwich Cuts

Bárány, Hubard, and Jerónimo recently showed that for given well-separated convex bodies S ₁,…,S _d in R ^d and constants β _i ∈[0,1], there exists a unique hyperplane h with the property that Vol (h ⁺∩S _i )=β _i ⋅Vol (S _i ); h ⁺ is the closed positive transversal halfspace of h, and h is a “generalized ham-sandwich cut.” We give a discrete analogue for a set S of n points in R ^d which are partitioned into a family S=P ₁∪⋅⋅⋅∪P _d of well-separated sets and are in weak general position. The combinatorial proof inspires an O(n(log n) ^d−3) algorithm which, given positive integers a _i ≤|P _i |, finds the unique hyperplane h incident with a point in each P _i and having |h ⁺∩P _i |=a _i . Finally we show two other consequences of the direct combinatorial proof: the first is a stronger result, namely that in the discrete case, the conditions assuring existence and uniqueness of generalized cuts are also necessary; the second is an alternative and simpler proof of the theorem in Bárány et al., and in addition, we strengthen the result via a partial converse.     

A Higman inequality for regular near polygons

The inequality of Higman for generalized quadrangles of order (s,t) with s>1 states that t≤s ². We generalize this by proving that the intersection number c _i of a regular near 2d-gon of order (s,t) with s>1 satisfies the tight bound c _i ≤(s ²ⁱ −1)/(s ²−1), and we give properties in case of equality. It is known that hemisystems in generalized quadrangles meeting the Higman bound induce strongly regular subgraphs. We also generalize this by proving that a similar subset in regular near 2d-gons meeting the bounds would induce a distance-regular graph with classical parameters (d,b,α,β)=(d,−q,−(q+1)/2,−((−q) ^d +1)/2) with q an odd prime power.     

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.     

On some invariants in numerical semigroups and estimations of the order bound

Let S={s _i } _i∈??? be a numerical semigroup. For s _i ∈S, let ν(s _i ) denote the number of pairs (s _i ?s _j ,s _j )∈S ². When S is the Weierstrass semigroup of a family $\{\mathcal{C}_{i}\}_{i\in\mathbb{N}}Let S={s _i } _i∈ℕ⊆ℕ be a numerical semigroup. For s _i ∈S, let ν(s _i ) denote the number of pairs (s _i −s _j ,s _j )∈S ². When S is the Weierstrass semigroup of a family {C_i}_{i ? \mathbbN}\{\mathcal{C}_{i}\}_{i\in\mathbb{N}} of one-point algebraic-geometric codes, a good bound for the minimum distance of the code C_i\mathcal{C}_{i} is the Feng and Rao order bound d _ORD (C _i ). It is well-known that there exists an integer m such that d _ORD (C _i )=ν(s _i+1) for each i≥m. By way of some suitable parameters related to the semigroup S, we find upper bounds for m and we evaluate m exactly in many cases. Further we conjecture a lower bound for m and we prove it in several classes of semigroups.     

Large-deviation probability and the local dimension of sets

Let X ₁ , X ₂ , ..., X_n be n independent identically distributed real random variables and S_n = Σ _n=1 ⁿ X_i. We obtain precise asymptotics forP (S_n ∈ nA) for rather arbitrary Borel sets A₁ in terms of the density of the dominating points in A. Our result extends classical theorems in the field of large deviations for independent samples. We also obtain asymptotics forP (S_n ∈ γ_nA), with γ_n/n → ∞. Proceedings of the Seminar on Stability Problems for Stochastic Models, Vologda, Russia, 1998, Part I.     

A class of Hamiltonian and edge symmetric Cayley graphs on symmetric groups

Abstract. Let Sn be the symmetric group     

On K s -free subgraphs in K s+k -free graphs and vertex Folkman numbers

Extending the problem of determining Ramsey numbers Erdős and Rogers introduced the following function. For given integers 2 ≤ s < t let f _s,t (n) = min{max{|S|: S ⊆ V (H) and H[S] contains no K _s }}, where the minimum is taken over all K _t -free graphs H of order n. This function attracted a considerable amount of attention but despite that, the gap between the lower and upper bounds is still fairly wide. For example, when t=s+1, the best bounds have been of the form Ω(n ^1/2+o(1)) ≤ f _s,s+1(n) ≤ O(n ^1−ɛ(s)), where ɛ(s) tends to zero as s tends to infinity. In this paper we improve the upper bound by showing that f _s,s+1(n) ≤ O(n ^2/3). Moreover, we show that for every ɛ > 0 and sufficiently large integers 1 ≪ k ≪ s, Ω(n ^1/2−ɛ ) ≤ f _s,s+k (n) ≤ O(n ^1/2+ɛ . In addition, we also discuss some connections between the function f _s,t and vertex Folkman numbers.     

A Nichtnegativstellensatz for polynomials in noncommuting variables

Let S⋃{f} be a set of symmetric polynomials in noncommuting variables. If f satisfies a polynomial identity Σ _i h _i ^* fh _i = 1 + Σ _i g _i ^* s _i g _i for some s _i ∈ S ⋃ {1}, then f is obviously nowhere negative semidefinite on the class of tuples of nonzero operators defined by the system of inequalities s ≥ 0 (s ∈ S). We prove the converse under the additional assumption that the quadratic module generated by S is Archimedean. Supported by the European network RAAG (EC contract HPRN-CT-2001-00271). Igor Klep was supported from the state budget by the Slovenian Research Agency (project No. Z1-9570-0101-06).     

The Stanley Conjecture on Intersections of Four Monomial Prime Ideals

We show that the Stanley's Conjecture holds for an intersection of four monomial prime ideals of a polynomial algebra S over a field and for an arbitrary intersection of monomial prime ideals (P _i ) _i∈[s] of S such that each P _i is not contained in the sum of the other (P _j ) _j≠i .     

Projective and indecomposableS-acts

LetS be a semigroup andE the set of all idempotents inS. LetS-Act be the category of allS-acts. LetC be a full subcategory ofS-Act which contains_s S and is closed under coproducts and summands. It is proved that, inC, anS-actP is projective and unitary if and only ifP≅ ∐ _{jϕ I} Se _i ,e _i ϕE. In particular,P is a projective, indecomposable and unitary object if and only ifP ≅Se for somee ∈E. These generalize some results obtained by Knauer and Talwar. Research partially supported by a UGC (HK) (Grant No. 2160092).     

Projective and indecomposableS-acts

LetS be a semigroup andE the set of all idempotents inS. LetS-Act be the category of allS-acts. LetC be a full subcategory ofS-Act which contains_s S and is closed under coproducts and summands. It is proved that, inC, anS-actP is projective and unitary if and only ifP≅ ∐ _{jϕ I} Se _i ,e _i ϕE. In particular,P is a projective, indecomposable and unitary object if and only ifP ≅Se for somee ∈E. These generalize some results obtained by Knauer and Talwar.     

On rigidity of Clifford torus in a unit sphere

We extend the scalar curvature pinching theorems due to Peng-Terng, Wei-Xu and Suh-Yang. Let M be an n-dimensional compact minimal hypersurface in S n+1 satisfying Sf 4 f_3~2 ≤ 1/n S~3 , where S is the squared norm of the second fundamental form of M, and f_k =sum λ_i~k from i and λ_i (1 ≤ i ≤ n) are the principal curvatures of M. We prove that there exists a positive constant δ(n)(≥ n/2) depending only on n such that if n ≤ S ≤ n + δ(n), then S ≡ n, i.e., M is one of the Clifford torus S~k ((k/n)~1/2 ) ×S~...     

PP-Rings of Generalized Power Series

Abstract As a generalization of power series rings, Ribenboim introduced the notion of the rings of generalized power series. Let R be a commutative ring, and (S, ≤) a strictly totally ordered monoid. We prove that (1) the ring [[R ^S,≤]] of generalized power series is a PP-ring if and only if R is a PP-ring and every S-indexed subset C of B(R) (the set of all idempotents of R) has a least upper bound in B(R) and (2) if (S, ≤) also satisfies the condition that 0 ≤s for any s∈S, then the ring [[R ^S,≤ ]] is weakly PP if and only if R is weakly PP. Research supported by National Natural Science Foundation of China, 19501007, and Natural Science Foundation of Gansu, ZQ-96-01