Many triangulated spheres

Lets(d, n) be the number of triangulations withn labeled vertices ofS ^d–1, the (d–1)-dimensional sphere. We extend a construction of Billera and Lee to obtain a large family of triangulated spheres. Our construction shows that logs(d, n)C ₁(d)n ^[(d–1)/2], while the known upper bound is logs(d, n)C ₂(d)n ^[d/2] logn.Letc(d, n) be the number of combinatorial types of simpliciald-polytopes withn labeled vertices. (Clearly,c(d, n)s(d, n).) Goodman and Pollack have recently proved the upper bound: logc(d, n)d(d+1)n logn. Combining this upper bound forc(d, n) with our lower bounds fors(d, n), we obtain, for everyd5, that lim _n(c(d, n)/s(d, n))=0. The cased=4 is left open. (Steinitz's fundamental theorem asserts thats(3,n)=c(3,n), for everyn.) We also prove that, for everyb4, lim _d(c(d, d+b)/s(d, d+b))=0. (Mani proved thats(d, d+3)=c(d, d+3), for everyd.)Lets(n) be the number of triangulated spheres withn labeled vertices. We prove that logs(n)=2^{0.69424n(1+o(1))}. The same asymptotic formula describes the number of triangulated manifolds withn labeled vertices.Research done, in part, while the author visited the mathematics research center at AT&T Bell Laboratories.     

Representations of integers as sums of powers with increasing exponents

Let(n) be the least integer such thatn may be represented in the formn=x ₁ ² +x ₂ ³ +...+x _(n) ⁽ⁿ⁾⁺¹ wherex ₁,x ₂, ...,x _(n) are natural numbers. We computed(n) forn 250 000 and found that(n) 5 for all thesen exceptn=56, 160 for which(n)=6. Also(n) 4 for 41542<n<=250 000.     

Isomorphisms of Steinberg groups over commutative rings

LetA andR be commutative rings, andm andn be integers3. It is proved that, if :St _m (A)St _n (R) is an isomorphism, thenm=n. Whenn4, we have: (1) Every isomorphism :St _n(A)St _n(R) induces an isomorphism:E _n (A)E _n (R), and is uniquely determined by; (2) IfSt _n (A) St _n (R) thenK _2.n (A)K _2.n (R); (3) Every isomorphismE _n (A) E _n (R) can be lifted to an isomorphismSt _n(A)St _n(R); (4)St _n(A) St _n(R) if and only ifAR. For the casen=3, ifSt ₃(A) andSt ₃(R) are respectively central extensions ofE ₃(A) andE ₃ (R), then the above (1) and (2) hold.The Project supported by National Natural Science Foundation of China     

Verschärfung einer Ungleichung von Ky Fan

Summary In this paper we prove the following:IfA _n ,G _n andH _n (resp.A _n ,G _n andH _n ) denote the arithmetic, geometric and harmonic means ofa ₁,, a _n (resp. 1 –a ₁,, 1 –a _n ) and ifa _i (0, 1/2],i = 1,,n, then(G _n /G _n ) ⁿ (A _n /A _n ) ^n-1 H _n /H _n , (^*) with equality holding forn = 1,2. Forn 3 equality holds if and only ifa ₁ = =a _n . The inequality (^*) sharpens the well-known inequality of Ky Fan:G _n /G _n A _n /A _n .

     

Complexes whose boundaries cannot be pushed around

LetK ^{n n} be a triangulatedn-ball. Examples are given to show that unlike in the two-dimensional case, the following hold for alln3: (1) there are nonconvexK ⁿ with no convex simplexwise linear embeddingsK ^{n n} , even though there are strictly convex simplexwise linear embeddings K ^{n n} ; (2) there are convexK ⁿ , with no spanning simplices, such that not every simplexwise linear embeddingf: K ^{n n} with convex image can be extended to a simplexwise linear embedding ofK ⁿ ; (3) there are convexK ⁿ such that the space of simplexwise linear homeomorphisms ofK ⁿ , fixed on K ⁿ , is not path connected.Partially supported by NSF Contract DMS-8503388.     

Simplicial Cohomology with Coefficients in Symmetric Categorical Groups

In this paper we introduce and study a cohomology theory {H ⁿ (–,A)} for simplicial sets with coefficients in symmetric categorical groups A. We associate to a symmetric categorical group A a sequence of simplicial sets {K(A,n)} _n0, which allows us to give a representation theorem for our cohomology. Moreover, we prove that for any n3, the functor K(–,n) is right adjoint to the functor _n , where _n (X ) is defined as the fundamental groupoid of the n-loop complex ⁿ (X ). Using this adjunction, we give another proof of how symmetric categorical groups model all homotopy types of spaces Y with _i (Y)=0 for all in,n+1 and n3; and also we obtain a classification theorem for those spaces: [–,Y]H ⁿ (–, _n (Y)).     

Partitioning arrangements of lines II: Applications

In this paper we present efficient deterministic algorithms for various problems involving lines or segments in the plane, using the partitioning algorithm described in a companion paper [A3]. These applications include: (i) anO(m ^2/3 n ^2/3 · log^2/3 n · log^/3 (m/n)+(m+n) logn) algorithm to compute all incidences betweenm points andn lines, where is a constant <3.33; (ii) anO(m ^2/3 n ^2/3 · log^5/3 n · log^/3 (m/n)+(m+n) logn) algorithm to computem faces in an arrangement ofn lines; (iii) anO(n ^4/3 log^(+2)/3 n) algorithm to count the number of intersections in a set ofn segments; (iv) anO(n ^4/3 log^{( + 2)/3} n) algorithm to count red-blue intersections between two sets of segments, and (v) anO(n ^3/2 log^/3 n) algorithm to compute spanning trees with low stabbing number for a set ofn points. We also present an algorithm that, given set ofn points in the plane, preprocesses it, in timeO(nm log^+1/2 n), into a data structure of sizeO(m) forn lognmn ², so that the number of points ofS lying inside a query triangle can be computed inO((n/m) log^3/2 n) time.Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. A preliminary version of this paper appears in theProceedings of the 5th ACM Symposium on Computational Geometry, 1989, pp. 11–22.     

Skew-symmetric association schemes with two classes and strongly regular graphs of type L 2n−1(4n−1)

A construction of a pair of strongly regular graphs ⁿ and ⁿ of type L _2n–1(4n–1) from a pair of skew-symmetric association schemes W, W of order 4n–1 is presented. Examples of graphs with the same parameters as ⁿ and ⁿ, i.e., of type L _2n–1(4n–1), were known only if 4n–1=p ³, where p is a prime. The first new graph appearing in the series has parameters (v, k, )=(225, 98, 45). A 4-vertex condition for relations of a skew-symmetric association scheme (very similar to one for the strongly regular graphs) is introduced and is proved to hold in any case. This has allowed us to check the 4-vertex condition for ⁿ and ⁿ, thus to prove that ⁿ and ⁿ are not rank three graphs if n>2.     

On the Densities of Certain Lattice Packings by Parallelepipeds

Given any (non-degenerate) n-dimensional lattice L, let (L) denote the supremum of the numbers such that there exists a lattice packing Q + L of density where Q is some o-symmetric parallelepiped with faces parallel to the coordinate axes. Many efforts have been made to determine or estimate the minimal such density _n taken over all n-dimensional lattices. It is known that 0$$ " align="middle" border="0"> . Here we investigate a sequence of lattices L _n which are known to minimize the function (L) in dimensions n 3 and are likely to provide the minima _n = (L _n ) in certain higher dimensions. We establish the inequality (L _n ) n ^–n/2 which supports the conjecture that lim sup _n ( _n )^{1/(n log n)} is positive.     

The law of the iterated logarithm for subsequences and characterization of the cluster set ofS n k/(2n k log logn k)1/2 in Banach spaces

LetS _n=X ₁+...+X _n, where {X _n;n=1, 2,...} is a sequence of i.i.d. random vectors with values in a Banach space and let be any infinite set of positive integers. In this paper we obtain the bounded and the compact laws of the iterated logarithm for {S _n;n}. We characterize the cluster set of {S _n/(2n log logn)^1/2;n}, for random vectors with mean zero, weak second moment, and satisfying certain additional conditions. Special situations, like type 2 Banach spaces and the real-valued case are also considered.     

Gröbner bases and triangulations of the second hypersimplex

The algebraic technique of Gröbner bases is applied to study triangulations of the second hypersimplex (2,n). We present a quadratic Gröbner basis for the associated toric idealK(K _n ). The simplices in the resulting triangulation of (2,n) have unit volume, and they are indexed by subgraphs which are linear thrackles [28] with respect to a circular embedding ofK _n . Forn6 the number of distinct initial ideals ofI(K _n ) exceeds the number of regular triangulations of (2,n); more precisely, the secondary polytope of (2,n) equals the state polytope ofI(K _n ) forn5 but not forn6. We also construct a non-regular triangulation of (2,n) forn9. We determine an explicit universal Gröbner basis ofI(K _n ) forn8. Potential applications in combinatorial optimization and random generation of graphs are indicated.Research partially supported by a doctoral fellowship of the National University of Mexico, the National Science Foundation, the David and Lucile Packard Foundation and the U.S. Army Research Office (through ACSyAM/MSI, Cornell).     

Properties of Standard n-Ideals of a Lattice

An n-ideal of a lattice L is a convex sublattice containing a fixed element n L and it is called standard if it is a standard element of the lattice of n-ideals I_n(L). In this paper we have shown that, for a neutral element n of a lattice L, the principal n-ideal a_n of a lattice L is a standard n-ideal if and only if a n is standard and a n is dual standard. We have also shown that if n is a neutral element and (n] and [n) are relatively complemented, then every homomorphism n-kernels of L is a standard n-ideal and every standard n-ideal is the n-kernel of precisely one congruence relation. Finally, we have shown that, for a relatively complemented lattice L with 0 and 1, C(L) is a Boolean algebra if and only if every standard n-ideal of L is a principal n-ideal.AMS Subject Classification (2000) 06B10 06B99 06C15     

On the lower Markov spectrum

C. Hightower found two infinite sequences of gaps in the Markov spectrum, ( _n , _n ) and ( _n , _n ) with _n and _n both Markov elements, converging to . This paper exhibits Markov elements _n ^* and _n ^* such that, for alln 1, ( _n ^* , _n ) and ( _{n n} ^* ) are gaps in the Markov spectrum. Other results include showing that, for alln 1, _n is completely isolated, while the other endpoints of the gaps are limit points in the Markov spectrum.     

Existence of HSOLSSOMs of type

In this paper we investigate the existence of holey self-orthogonal Latin squares with a symmetric orthogonal mate of type 2ⁿu¹ (HSOLSSOM(2ⁿu¹)). For u2, necessary conditions for existence of such an HSOLSSOM are that u must be even and n3u/2+1. Xu Yunqing and Hu Yuwang have shown that these HSOLSSOMs exist whenever either (1) n9 and n3u/2+1 or (2) n263 and n2(u-2). In this paper we show that in (1) the condition n9 can be extended to n30 and that in (2), the condition n263 can be improved to n4, except possibly for 19 pairs (n,u), the largest of which is (53,28).     

On the Parity of the Number of Partitions in Square Free Parts

Let p~(n) be the number of partitions of a positive integer n in square free parts. We prove that for large N,(a) The number of n N such that p~(n) is odd is log N,(b) The number of n N such that p~(n) is even is N/log N.     

A family of multiply extended grids

We construct an infinite family{ _n}_n=5 of finite connected graphs _n that are multiple extensions of the well-known extended grid discovered in [1] (which is isomorphic to ₅). The graphs _n are locally _n–1 forn > 5, and have the following property: the automorphism groupG(n) of _n permutes transitively the maximal cliques of _n (which aren-cliques) and the stabilizer of somen-clique of _n inG(n) induces _n on the vertices of. Furthermore we show that the clique complexes of the graphs _n are simply connected.     

Continuity of Usual Operations and Variational Convergences

Given convergent sequences of functions (f _n ) and (g _n ), we look for conditions ensuring that the sequences (f _n +g _n ), (max(f _n ,g _n )) and (f _n g _n ) converge, being the infimal convolution. The convergences we use are variational convergences. This study is motivated by applications to Hamilton–Jacobi equations.     

A Family of Asymptotically e(n − 1) ! Polynomial Orders of Nn

Here, N is the set of nonnegative integers, while an order in N ⁿ is a bijective function : N ⁿ N. Two orders are equivalent if they differ only by a permutation of their arguments. Let s(x)=x₁+ ··· +x _n for 0 < n N and x =(x ₁, ···, x _n ) N ⁿ ; such an is a diagonal order if (x) < (y) whenever x,y N ⁿ , and s(x) < s(y). Lew composed Skolem"s diagonal polynomial orders to construct c _n inequivalent nondiagonal polynomial orders in N ⁿ . Afterwards, Morales and Lew did the same with respect to the Morales–Lew"s diagonal orders, obtaining additional d _n inequivalent nondiagonal polynomial orders. Moreover, they proved that d _n / c _n as n . Recently, Sanchez obtained a family of (n – 1) ! inequivalent diagonal orders in N ⁿ . In this paper, we compose the Sanchez diagonal polynomial orders to construct e _n inequivalent nondiagonal polynomial orders with e _n e(n – 1) !, where e is the base of natural logarithms. Furthermore, we prove that e _n / d _n as n .     

Convergence in distribution and Skorokhod Convergence for the general theory of processes

Summary This paper proves some Skorokhod Convergence Theorems for processes with filtration. Roughly, these are theorems which say that if a family of processes with filtration (X ⁿ , ⁿ ),n, converges in distribution in a suitable sense, then there exists a family of equivalent processes (Y ⁿ , ⁿ ),n, which converges almost surely. The notion of equivalence used is that of adapted distribution, which guarantees that each (X ⁿ , ⁿ ) has the same stochastic properties as (X ⁿ , ⁿ ), with respect to its filtration, such as the martingale property or the Markov property. The appropriate notion of convergence in distribution is convergence in adapted distribution, which is developed in the paper. Fortunately, any tight sequence of processes has a subsequence which converges in adapted distribution. For discrete time processes, (Y ⁿ , ⁿ ),n, and their limit (Y, ) may be taken as all having the same fixed filtration ⁿ =. In the continuous time case, theY ⁿ , ⁿ may require different filtrations ⁿ , which converge to. To handle this, convergence of filtrations is defined and its theory developed.During part of the time this work was in progress, it was supported by an NSERC operating grant, and the author was an NSERC University Research Fellow. The author wishes to thank the Steklov Mathematical Institute of the Soviet Academy of Sciences for its hospitality while the principle research in this paper was being begun, A.N. Shiryaev and P.C. Greenwood, who made the author's visit there possible, and Ján Miná for his hospitality while that research was being finished. We thank the referee who suggested the results in Sect. 12