Minimal triangulations of Kummer varieties

By an (abstract) Kummer variety K^d we mean the d-dimensiona1 torus T^d modulo the involution ? ? — ?. The 2^d elements in T^d of order two are fixed points of the involution and therefore K^d has 2^d isolated singularities (for d ≧ 3). Any simplicial decomposition of K^d must have at least as many vertices. In this paper we describe a highly symmetrical simplicial decomposition of K^d with 2^d vertices such that the link of each vertex is a combinatorial real projective space ?P^d-1 with 2^d—1 vertices. The automorphism group of order (d + 1)! 2^d admits a natural representation in the affine group of dimension d over the field with two elements. A particular case is the classical Kummer surface with 16 nodes (d=4). In this case our 16-vertex triangulation has a close relationship with the abstract Kummer configuration 16₆.     

Two combinatorial properties of a class of simplicial polytopes

Letf(P _s ^d ) be the set of allf-vectors of simpliciald-polytopes. ForP a simplicial 2d-polytope let Σ(P) denote the boundary complex ofP. We show that for eachf ∈f(P _s ^d ) there is a simpliciald-polytopeP withf(P)=f such that the 11 02 simplicial diameter of Σ(P) is no more thanf ₀(P)−d+1 (one greater than the conjectured Hirsch bound) and thatP admits a subdivision into a simpliciald-ball with no new vertices that satisfies the Hirsch property. Further, we demonstrate that the number of bistellar operations required to obtain Σ(P) from the boundary of ad-simplex is minimum over the class of all simplicial polytopes with the samef-vector. This polytopeP will be the one constructed to prove the sufficiency of McMullen's conditions forf-vectors of simplicial polytopes.     

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.     

Triangulating point sets in space

A setP ofn points inR ^d is called simplicial if it has dimensiond and contains exactlyd + 1 extreme points. We show that whenP containsn interior points, there is always one point, called a splitter, that partitionsP intod + 1 simplices, none of which contain more thandn/(d + 1) points. A splitter can be found inO(d ⁴ +nd ²) time. Using this result, we give anO(nd ⁴ log_1+1/d n) algorithm for triangulating simplicial point sets that are in general position. InR ³ we give anO(n logn +k) algorithm for triangulating arbitrary point sets, wherek is the number of simplices produced. We exhibit sets of 2n + 1 points inR ³ for which the number of simplices produced may vary between (n – 1)² + 1 and 2n – 2. We also exhibit point sets for which every triangulation contains a quadratic number of simplices.Research supported by the Natural Science and Engineering Research Council grant A3013 and the F.C.A.R. grant EQ1678.     

Multicomplexes and polynomials with real zeros

We show that each polynomial a(z)=1+a₁z+?+a_dz^d in N[z] having only real zeros is the f-polynomial of a multicomplex. It follows that a(z) is also the h-polynomial of a Cohen-Macaulay ring and is the g-polynomial of a simplicial polytope. We conjecture that a(z) is also the f-polynomial of a simplicial complex and show that the multicomplex result implies this in the special case that the zeros of a(z) belong to the real interval [-1,0). We also show that for fixed d the conjecture can fail for at most finitely many polynomials having the required form.     

On stability ofm-variateC 1 interpolation

A simplicial mesh (triangulation) is constructed that generalizes the two-dimensional 4-direction mesh to ℝ ^m . This mesh, with symmetric, shift-invariant values at the vertices, is shown to admit a bounded C¹ interpolant if and only if the alternating sum of the values at the vertices of any 1-cube is zero. This implies that interpolation at the vertices of an m-dimensional, simplicial mesh by a C¹ piecewise polynomial of degree m+1 with one piece per simplex is unstable.     

Lattices on simplicial partitions

In this paper, (d+1)-pencil lattices on simplicial partitions in R^d are studied. The barycentric approach naturally extends the lattice from a simplex to a simplicial partition, providing a continuous piecewise polynomial interpolant over the extended lattice. The number of degrees of freedom is equal to the number of vertices of the simplicial partition. The constructive proof of this fact leads to an efficient computer algorithm for the design of a lattice.     

Multivariate Regression Depth

   Abstract. The regression depth of a hyperplane with respect to a set of n points in \Real ^d is the minimum number of points the hyperplane must pass through in a rotation to vertical. We generalize hyperplane regression depth to k -flats for any k between 0 and d-1 . The k=0 case gives the classical notion of center points. We prove that for any k and d , deep k -flats exist, that is, for any set of n points there always exists a k -flat with depth at least a constant fraction of n . As a consequence, we derive a linear-time (1+ɛ) -approximation algorithm for the deepest flat. We also show how to compute the regression depth in time O(n ^d-2 +nlog n) when 1≤ k≤ d-2 .     

Lagrange interpolation and finite element superconvergence

We consider the finite element approximation of the Laplacian operator with the homogeneous Dirichlet boundary condition, and study the corresponding Lagrange interpolation in the context of finite element superconvergence. For d‐dimensional Q_k‐type elements with d ≥ 1 and k ≥ 1, we prove that the interpolation points must be the Lobatto points if the Lagrange interpolation and the finite element solution are superclose in H¹ norm. For d‐dimensional P_k‐type elements, we consider the standard Lagrange interpolation—the Lagrange interpolation with interpolation points being the principle lattice points of simplicial elements. We prove for d ≥ 2 and k ≥ d + 1 that such interpolation and the finite element solution are not superclose in both H¹ and L² norms and that not all such interpolation points are superconvergence points for the finite element approximation. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 20: 33–59, 2004.     

Three‐query PCPs with perfect completeness over non‐Boolean domains

We study non‐Boolean PCPs that have perfect completeness and query three positions in the proof. For the case when the proof consists of values from a domain of size d for some integer constant d ≥ 2, we construct a nonadaptive PCP with perfect completeness and soundness d^?1 + d^?2 + ?, for any constant ? > 0, and an adaptive PCP with perfect completeness and soundness d^?1 + ?, for any constant ? > 0. The latter PCP can be converted into a nonadaptive PCP with perfect completeness and soundness d^?1 + ?, for any constant ? > 0, where four positions are read from the proof. These results match the best known constructions for the case d = 2 and our proofs also show that the particular predicates we use in our PCPs are nonapproximable beyond the random assignment threshold. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Grünbaum 4-arrangements on the 120-cell and the 600-cell

In 1971, Branko Grünbaum noted that the projectived-arrangements formed by including with the facet hyperplanes of a regular polytope in E^d some of its hyperplanes of mirror symmetry and possibly the hyperplane at infinity might be expected to be simplicial. In this paper we show that none of the 4-arrangements so associated with either the 120-cell or the 600-cell inE ⁴ is simplicial.     

Simplicial cross-polytopic d-arrangements

Branko Grünbaum has observed that the projective d-arrangements formed by the facet hyperplanes of a regular polytope together with some of its hyperplanes of mirror symmetry and possibly the hyperiplane at infinity are sometimes simplicial.We investigate the projective d-arrangements associated in this manner with a cross-polytope. Fourteen such simplicial arrangements are known: three 1-arrangements, four 2-arrangements, six 3-arrangements, and one 4-arrangement. In this paper we prove that no other arrangement so associated with a cross-polytope is simplicial.     

Every Simplicial Polytope with at Most d + 4 Vertices Is a Quotient of a Neighborly Polytope

We show that every simplicial d-polytope with d+4 vertices is a quotient of a neighborly (2d+4)-polytope with 2d+8 vertices, using the technique of affine Gale diagrams. The result is extended to matroid polytopes. Received September 27, 1995.     

On the family of diophantine triples {<Emphasis Type="Italic">k</Emphasis> + 1, 4<Emphasis Type="Italic">k</Emphasis>, 9<Emphasis Type="Italic">k</Emphasis> + 3}

We prove that if k is a positive integer and d is a positive integer such that the product of any two distinct elements of the set {k + 1, 4k, 9k + 3, d} increased by 1 is a perfect square, then d = 144k ³ + 192k ² + 76k + 8.      

Regularity of line configurations

We show that in arithmetically-Gorenstein line arrangements with only planar singularities, each line intersects the same number of other lines. This number has an algebraic interpretation: it is the Castelnuovo–Mumford regularity of the coordinate ring of the arrangement.We also prove that every $(d?1)$-dimensional simplicial complex whose 0-th and 1-st homologies are trivial is the nerve complex of a suitable d-dimensional standard graded algebra of depth ≥3. This provides the converse of a recent result by Katzman, Lyubeznik and Zhang.     

d n = 0: Generalized Homology

We study the generalized homology associated with a nilpotent endomorphism d satisfying d ^N = 0,For simplicial modules, we construct such nilpotent endomorphisms and we prove a general result relating the corresponding generalized homologies to the ordinary homology. We also discuss the generalization of the notion of graded differential algebra in this context.     

Second-order accuracy of depth-based bootstrap confidence regions

We consider the problem of setting bootstrap confidence regions for multivariate parameters based on data depth functions. We prove, under mild regularity conditions, that depth-based bootstrap confidence regions are second-order accurate in the sense that their coverage error is of order n⁻¹, given a random sample of size n. The results hold in general for depth functions of types A and D, which cover as special cases the Tukey depth, the majority depth, and the simplicial depth. A simulation study is also provided to investigate empirically the bootstrap confidence regions constructed using these three depth functions.     

Face numbers and the fundamental group

We resolve a conjecture of Kalai asserting that the g ₂-number of any (finite) simplicial complex Δ that represents a normal pseudomanifold of dimension d ≥ 3 is at least as large as \(\left( {\begin{array}{*{20}{c}} {d + 2} \\ 2 \end{array}} \right)m\left( \Delta \right)\), where m(Δ) denotes the minimum number of generators of the fundamental group of Δ. Furthermore, we prove that a weaker bound, \({h_2}\left( \Delta \right) \geqslant \left( {\begin{array}{*{20}{c}} {d + 1} \\ 2 \end{array}} \right)m\left( \Delta \right)\), applies to any d-dimensional pure simplicial poset Δ all of whose faces of co-dimension ≥ 2 have connected links. This generalizes a result of Klee. Finally, for a pure relative simplicial poset Ψ all of whose vertex links satisfy Serre’s condition (S _r ), we establish lower bounds on h ₁(Ψ),...,h _r (Ψ) in terms of the μ-numbers introduced by Bagchi and Datta.     

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].     

Lattices on simplicial partitions which are not simply connected

In this paper, (d+1)-pencil lattices on simplicial partitions in R^d, which are not simply connected, are studied. It is shown, how the fact that a partition is not simply connected can be used to increase the flexibility of a lattice. A local modification algorithm is developed also to deal with slight partition topology changes that may appear afterwards a lattice has already been constructed.