Some combinatorial properties of flag simplicial pseudomanifolds and spheres

A simplicial complex Δ is called flag if all minimal nonfaces of Δ have at most two elements. The following are proved: First, if Δ is a flag simplicial pseudomanifold of dimension d−1, then the graph of Δ (i) is (2d−2)-vertex-connected and (ii) has a subgraph which is a subdivision of the graph of the d-dimensional cross-polytope. Second, the h-vector of a flag simplicial homology sphere Δ of dimension d−1 is minimized when Δ is the boundary complex of the d-dimensional cross-polytope.     

Teoremi merceriani relativi a trasformazioni regolari non negative e anche più generali

Sunto Ad una successione (complessa) |s_n| associamo la successione trasformata |t_n| mediante una matrice di sommazione regolare C; sono noti teoremi merceriani (per es.G. H. Hardy, E. R. Love) che dalla relazione s_n — qt_n → (1 — q)l deducono s_n → l, sotto la condizione che il moltiplicatore q sia interno a determinati campi In questa NOta si considera C regolare non negativa e, mediante l'introduzione di un' opportuna ? funzione di aderenza di un insieme in un altro ? e l'applicazione del classico teorema del ? nocciolo ? diK. Knopp, si determinano campi più ampi di quello circolare stabilito daE. R. Love; si estende il risultato anche a matrici C regolari più generali mediante teoremi più recenti diR. P. Agnew eA. Robinson; inoltre si perfeziona il classico teorema diJ. Mercer-G. H. Hardy.

---

Summary Let |t_n| be trasformed, by a regular summation matrix C, of a (complex) sequence |s_n|. Mercerian theorems (e. g. G. H. Hardy, E. R. Love theorems) deduce s_n → l from s_n — qt_n → (1 — q)l if q lies in a suitable domain. This paper is concerned with regular non-negative C. A suitable ? adherence-function of a set into another ? is introduced and theKnopp's ? Core theorem ? leads to wider domains thanE. R. Love circle. The result is extended to more general regular matrices C by means ofR. P. Agnew andA. Robinson theorems. The classicalJ. Mercer-G. H. Hardy theorem is also improved.

---

---

A Giovanni Sansone nel suo 70^mo compleanno.

---

Il presente lavoro è stato oggetto di una comunicazione al VI Congresso Nazionale della Unione Matematica Italiana (Napoli, 11–16 settembre 1959).     

Topology of Random 2-Complexes

We study the Linial–Meshulam model of random two-dimensional simplicial complexes. One of our main results states that for p≪n ⁻¹ a random 2-complex Y collapses simplicially to a graph and, in particular, the fundamental group π ₁(Y) is free and H ₂(Y)=0, asymptotically almost surely. Our other main result gives a precise threshold for collapsibility of a random 2-complex to a graph in a prescribed number of steps. We also prove that, if the probability parameter p satisfies p≫n ^−1/2+ϵ , where ϵ>0, then an arbitrary finite two-dimensional simplicial complex admits a topological embedding into a random 2-complex, with probability tending to one as n→∞. We also establish several related results; for example, we show that for p<c/n with c<3 the fundamental group of a random 2-complex contains a non-abelian free subgroup. Our method is based on exploiting explicit thresholds (established in the paper) for the existence of simplicial embeddings and immersions of 2-complexes into a random 2-complex.     

Dirac’s Theorem on Simplicial Matroids

We introduce the notion of k-hyperclique complexes, i.e., the largest simplicial complexes on the set [n] with a fixed k-skeleton. These simplicial complexes are a higher-dimensional analogue of clique (or flag) complexes (case k = 2) and they are a rich new class of simplicial complexes. We show that Dirac’s theorem on chordal graphs has a higher-dimensional analogue in which graphs and clique complexes get replaced, respectively, by simplicial matroids and k-hyperclique complexes. We prove also a higher-dimensional analogue of Stanley’s reformulation of Dirac’s theorem on chordal graphs.      

Sum Complexes—a New Family of Hypertrees

A k-dimensional hypertree X is a k-dimensional complex on n vertices with a full (k−1)-dimensional skeleton and \binomn-1k\binom{n-1}{k} facets such that H _k (X;ℚ)=0. Here we introduce the following family of simplicial complexes. Let n,k be integers with k+1 and n relatively prime, and let A be a (k+1)-element subset of the cyclic group ℤ _n . The sum complex X _A is the pure k-dimensional complex on the vertex set ℤ _n whose facets are σ⊂ℤ _n such that |σ|=k+1 and ∑ _x∈σ x∈A. It is shown that if n is prime, then the complex X _A is a k-hypertree for every choice of A. On the other hand, for n prime, X _A is k-collapsible iff A is an arithmetic progression in ℤ _n .     

Vietoris–Rips Complexes of Planar Point Sets

Fix a finite set of points in Euclidean n-space \mathbbEⁿ\mathbb{E}^{n} , thought of as a point-cloud sampling of a certain domain D ì \mathbbEⁿD\subset\mathbb{E}^{n} . The Vietoris–Rips complex is a combinatorial simplicial complex based on proximity of neighbors that serves as an easily-computed but high-dimensional approximation to the homotopy type of D. There is a natural “shadow” projection map from the Vietoris–Rips complex to \mathbbEⁿ\mathbb{E}^{n} that has as its image a more accurate n-dimensional approximation to the homotopy type of D.     

On simplicial and cubical complexes with short links

We consider closed simplicial and cubicaln-complexes in terms of the links of their (n−2)-faces. Especially, we consider the case when this link has size 3 or 4, i.e., every (n−2)-face is contained in 3 or 4n-faces. Such simplical complexes withshort (i.e., of length 3 or 4) links are completely classified by theircharacteristic partition. We consider also embedding into (the skeletons of) hypercubes of the skeletons of simplical and cubical complexes. Research of the second author was financed by EC’s IIIRP Programme, within the Research Training Network “Algebraic Combinatorics in Europe,” grant IIPRN-CT-2001-00272. The third author acknowledges financial support of the Russian Foundation of Fundamental Research (grant 02-01-00803) and the Russian Foundation for Scientific Schools (grant NSh. 2185.2003.1), Program OMN (Division of Mathematical Sciences) of the Russian Academy of Sciences.     

A simplicial complex of 2-stack sortable permutations

For each n, we construct a simplicial complex whose k-dimensional faces are in one-to-one correspondence with 2-stack sortable permutations of length n having k ascents.     

Oriented matroids with few mutations

This paper defines a “connected sum” operation on oriented matroids of the same rank. This construction is used for three different applications in rank 4. First it provides nonrealizable pseudoplane arrangements with a low number of simplicial regions. This contrasts the case of realizable hyperplane arrangements: by a classical theorem of Shannon every arrangement ofn projective planes in ℝP ^d-1 contains at leastn simplicial regions and every plane is adjacent to at leastd simplicial regions [17], [18]. We construct a class of uniform pseudoarrangements of 4n pseudoplanes in ℝP³ with only 3n+1 simplicial regions. Furthermore, we construct an arrangement of 20 pseudoplanes where one plane is not adjacent to any simplicial region. Finally we disprove the “strong-map conjecture” of Las Vergnas [1]. We describe an arrangement of 12 pseudoplanes containing two points that cannot be simultaneously contained in an extending hyperplane.     

The topological structure of 3-pseudomanifolds

A 3-pseudomanifold (briefly 3-pm) is a finite connected simplicial 3-complex in which the link of every vertex is a closed 2-manifold. Such a link issingular if it is not a sphere. It is proved that for a preassigned list Σ of closed 2-manifolds (other than spheres), there is a 3-pm in which the list of singular links is precisely Σ, iff the number of the non-orientable members in Σ with odd genus is even. Close relationship is found between 3-pms and 3-manifolds with boundary. This yields a simple proof for the 2-dimensional case of Pontrjagin-Thom’s theorem (i.e., necessary and sufficient condition for a 2-manifold to bound a 3-manifold). The concept of a 3-pm is generalized to higher dimensions.     

An elementary proof of the Loomis–Whitney theorem

Loomis and Whitney proved an inequality between volume and areas of projections of an open set in n-dimensional space related to the isoperimetric inequality. They reduced the problem to a combinatorial theorem proved by a repeated use of Hölder inequality. In this paper we prove a general inequality between real numbers which easily implies the combinatorial theorem of Loomis and Whitney.

     

<Emphasis Type="Italic">f</Emphasis>-Vectors of barycentric subdivisions

For a simplicial complex or more generally Boolean cell complex Δ we study the behavior of the f- and h-vector under barycentric subdivision. We show that if Δ has a non-negative h-vector then the h-polynomial of its barycentric subdivision has only simple and real zeros. As a consequence this implies a strong version of the Charney–Davis conjecture for spheres that are the subdivision of a Boolean cell complex or the subdivision of the boundary complex of a simple polytope. For a general (d − 1)-dimensional simplicial complex Δ the h-polynomial of its n-th iterated subdivision shows convergent behavior. More precisely, we show that among the zeros of this h-polynomial there is one converging to infinity and the other d − 1 converge to a set of d − 1 real numbers which only depends on d. F. Brenti and V. Welker are partially supported by EU Research Training Network “Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272 and the program on “Algebraic Combinatorics” at the Mittag-Leffler Institut in Spring 2005.     

The (2 n+1−2)-ray algorithm: A new simplicial algorithm to compute economic equilibria

A new variable dimension simplicial restart algorithm is introduced to compute economic equilibria. The number of rays along which the algorithm can leave the starting point differs from the thusfar known algorithms. More precisely, the new algorithm has one ray to each of the 2 ⁿ⁺¹−2 faces of then-dimensional price simplex, whereas the existing algorithms haven+1 rays either to each facet or to each vertex of the unit simplex. The path of points followed by the algorithm can be interpreted as a globally and universally convergent price adjustment process. The process is also economically meaningful and therefore it is a good alternative for the well-known Walras' tatonnement process. Computational results show that the algorithm is competitive with the most efficient simplicial algorithms developed thusfar. This work is part of theVF-program “Equilibrium and Disequilibrium in Demand and Supply”, which has been approved by the Netherlands Ministry of Education and Sciences.     

Finite group actions and étale cohomology

If a finite group G acts on a quasi-projective variety X, then H*_c(X,Z/n), the étale cohomology with compact support of X with coefficients inZ/n, has aZ/n[G]-module structure. It is well known that there is a finer invariant, an object RΓ_c(X,Z/n) of the derived category ofZ/n[G]-modules, whose cohomology is H*_c(X,Z/n). We show that there is a finer invariant still, a bounded complex Λ_c(X,Z/n) of direct summands of permutationZ/n[G]-modules, well-defined up to chain homotopy equivalence, which is isomorphic to RΓ_c(X,Z/n) in the derived category. This complex has many properties analogous to those of the simplicial chain complex of a simplicial complex with a group action. There are similar results forl-adic cohomology.     

A Chebyshev Type Upper Estimate for Prime Elements in Additive Arithmetic Semigroups

 Let G(n) and Λ(n) be two sequences of nonnegative numbers which satisfy G(0)=1 and an additive convolution equation . A Chebyshev-type upper estimate for prime elements in an additive arithmetic semigroup is essentially a tauberian theorem on Λ(n) and G(n). Suppose with real constants . The theorem proved here states that and that holds with an explicit function R(n) of order <1 in n. This theorem is sharp. It has several applications.     

Topological Model Categories Generated by Finite Complexes

 Our main result states that for each finite complex L the category TOP of topological spaces possesses a model category structure (in the sense of Quillen) whose weak equivalences are precisely maps which induce isomorphisms of all [L]-homotopy groups. The concept of [L]-homotopy has earlier been introduced by the first author and is based on Dranishnikov’s notion of extension dimension. As a corollary we obtain an algebraic characterization of [L]-homotopy equivalences between [L]-complexes. This result extends two classical theorems of J. H. C. Whitehead. One of them – describing homotopy equivalences between CW-complexes as maps inducing isomorphisms of all homotopy groups – is obtained by letting L = {point}. The other – describing n-homotopy equivalences between at most (n+1)-dimensional CW-complexes as maps inducing isomorphisms of k-dimensional homotopy groups with k ⩽ n – by letting L = S ⁿ⁺¹ , n ⩾ 0.     

Enriched homology and cohomology modules of simiplicial complexes

For a simplicial complex Δ on {1, 2,…, n} we define enriched homology and cohomology modules. They are graded modules over k[x ₁,…, x _n ] whose ranks are equal to the dimensions of the reduced homology and cohomology groups. We characterize Cohen-Macaulay, l-Cohen-Macaulay, Buchsbaum, and Gorenstein^* complexes Δ, and also orientable homology manifolds in terms of the enriched modules. We introduce the notion of girth for simplicial complexes and make a conjecture relating the girth to invariants of the simplicial complex. We also put strong vanishing conditions on the enriched homology modules and describe the simplicial complexes we then get. They are block designs and include Steiner systems S(c, d, n) and cyclic polytopes of even dimension. This paper is to a large extent a complete rewriting of a previous preprint, “Hierarchies of simplicial complexes via the BGG-correspondence”. Also Propositions 1.7 and 3.1 have been generalized to cell complexes in [11].     

A basic inequality and new characterization of Whitney spheres in a complex space form

LetN ⁿ (4c) be ann-dimensional complex space form of constant holomorphic sectional curvature 4c and letx:M ⁿ →N ⁿ (4c) be ann-dimensional Lagrangian submanifold inN ⁿ (4c). We prove that the following inequality always hold onM ⁿ: whereh is the second fundamental form andH is the mean curvature of the submanifold. We classify all submanifolds which at every point realize the equality in the above inequality. As a direct consequence of our Theorem, we give, a new characterization of theWhitney spheres in a complex space form. Partially supported by a research fellowship of the Alexander von Humboldt Stiftung.     

A Chebyshev Type Upper Estimate for Prime Elements in Additive Arithmetic Semigroups

 Let G(n) and Λ(n) be two sequences of nonnegative numbers which satisfy G(0)=1 and an additive convolution equation . A Chebyshev-type upper estimate for prime elements in an additive arithmetic semigroup is essentially a tauberian theorem on Λ(n) and G(n). Suppose with real constants . The theorem proved here states that and that holds with an explicit function R(n) of order <1 in n. This theorem is sharp. It has several applications. (Received 31 March 1999; in revised form 21 October 1999)