Standard graded vertex cover algebras, cycles and leaves

The aim of this paper is to characterize simplicial complexes which have standard graded vertex cover algebras. This property has several nice consequences for the squarefree monomial ideals defining these algebras. It turns out that such simplicial complexes are closely related to a range of hypergraphs which generalize bipartite graphs and trees. These relationships allow us to obtain very general results on standard graded vertex cover algebras which cover previous major results on Rees algebras of squarefree monomial ideals.

     

Simplicial trees are sequentially Cohen–Macaulay

This paper uses dualities between facet ideal theory and Stanley–Reisner theory to show that the facet ideal of a simplicial tree is sequentially Cohen–Macaulay. The proof involves showing that the Alexander dual (or the cover dual, as we call it here) of a simplicial tree is a componentwise linear ideal. We conclude with additional combinatorial properties of simplicial trees.     

Erd?s-Ko-Rado theorems for simplicial complexes

A recent framework for generalizing the Erd?s-Ko-Rado theorem, due to Holroyd, Spencer, and Talbot, defines the Erd?s-Ko-Rado property for a graph in terms of the graph's independent sets. Since the family of all independent sets of a graph forms a simplicial complex, it is natural to further generalize the Erd?s-Ko-Rado property to an arbitrary simplicial complex. An advantage of working in simplicial complexes is the availability of algebraic shifting, a powerful shifting (compression) technique, which we use to verify a conjecture of Holroyd and Talbot in the case of sequentially Cohen-Macaulay near-cones.     

Squarefree Vertex Cover Algebras

In this paper we introduce squarefree vertex cover algebras and exhibit a duality for them. We study the question when these algebras are standard graded and when these algebras coincide with the ordinary vertex cover algebras. It is shown that this is the case for simplicial complexes corresponding to principal Borel sets. Moreover, the generators of these algebras are explicitly described.     

Simplicial Lipschitz optimization without the Lipschitz constant

In this paper we propose a new simplicial partition-based deterministic algorithm for global optimization of Lipschitz-continuous functions without requiring any knowledge of the Lipschitz constant. Our algorithm is motivated by the well-known Direct algorithm which evaluates the objective function on a set of points that tries to cover the most promising subregions of the feasible region. Almost all previous modifications of Direct algorithm use hyper-rectangular partitions. However, other types of partitions may be more suitable for some optimization problems. Simplicial partitions may be preferable when the initial feasible region is either already a simplex or may be covered by one or a manageable number of simplices. Therefore in this paper we propose and investigate simplicial versions of the partition-based algorithm. In the case of simplicial partitions, definition of potentially optimal subregion cannot be the same as in the rectangular version. In this paper we propose and investigate two definitions of potentially optimal simplices: one involves function values at the vertices of the simplex and another uses function value at the centroid of the simplex. We use experimental investigation to compare performance of the algorithms with different definitions of potentially optimal partitions. The experimental investigation shows, that proposed simplicial algorithm gives very competitive results to Direct algorithm using standard test problems and performs particularly well when the search space and the numbers of local and global optimizers may be reduced by taking into account symmetries of the objective function.     

Diagrams and torsors

Suppose that A is a presheaf of categories enriched in simplicial sets on a small Grothendieck site. It is shown that the homotopy theory of enriched A-diagrams of equivalences taking values in simplicial sets can be identified with the homotopy theory of simplicial presheaves fibred over the diagonalized nerve dBA of A. The set [*,dBA] of morphisms in the simplicial presheaf homotopy category is identified with the set of path components of a category of A-torsors, for a suitable definition of A-torsor. These statements are special cases of localized results which hold when the corresponding localized model structures are proper. Examples of the latter include the motivic homotopy category, and so these results lead to a theory of motivic A-torsors which is classifiable up to equivalence by a family of morphisms in the motivic homotopy category. This research was supported by NSERC. Received: March 2006     

Chip-firing via open covers

We investigate chip-firing with respect to open covers of discrete graphs and metric graphs. For the case of metric graphs we show that given an open cover and a sink q, stabilization of a divisor D is unique and that there is a distinguished configuration equivalent to D, which we call the critical configuration. Also, we show that given a double cover of the metric graph by stars, which is the continuous analogue of the sandpile model, the critical configurations are in bijection with reduced divisors. Passing to the discrete case, we interpret open covers of a graph as simplicial complexes on the vertex and observe that chip-firing with respect to a simplicial complex is equivalent to the model introduced by Paoletti [G. Paoletti. July 11 2007: Master in Physics at University of Milan, defending thesis “Abelian sandpile models and sampling of trees and forests”; supervisor: Prof. S. Caracciolo. http://pcteserver.mi.infn.it/caraccio/index.html]. We generalize this setup for directed graphs using weighted simplicial complexes on the vertex set and show that the fundamental results extend. In the undirected case we present a generalization of the Cori-Le Borgne algorithm for chip-firing models via open covers, giving an explicit bijection between the critical configurations and the spanning trees of a graph.(http://www.elsevier.com/locate/endm)     

Symbolic powers of monomial ideals and vertex cover algebras

We introduce and study vertex cover algebras of weighted simplicial complexes. These algebras are special classes of symbolic Rees algebras. We show that symbolic Rees algebras of monomial ideals are finitely generated and that such an algebra is normal and Cohen-Macaulay if the monomial ideal is squarefree. For a simple graph, the vertex cover algebra is generated by elements of degree 2, and it is standard graded if and only if the graph is bipartite. We also give a general upper bound for the maximal degree of the generators of vertex cover algebras.     

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.     

Signable posets and partitionable simplicial complexes

The notion of apartitionable simplicial complex is extended to that of asignable partially ordered set. It is shown in a unified way that face lattices of shellable polytopal complexes, polyhedral cone fans, and oriented matroid polytopes, are all signable. Each of these classes, which are believed to be mutually incomparable, strictly contains the class of convex polytopes. A general sufficient condition, termedtotal signability, for a simplicial complex to satisfy McMullen's Upper Bound Theorem on the numbers of faces, is provided. The simplicial members of each of the three classes above are concluded to be partitionable and to satisfy the upper bound theorem. The computational complexity of face enumeration and of deciding partitionability is discussed. It is shown that under a suitable presentation, the face numbers of a signable simplicial complex can be efficiently computed. In particular, the face numbers of simplicial fans can be computed in polynomial time, extending the analogous statement for convex polytopes. The research of S. Onn was supported by the Alexander von Humboldt Stifnung, by the Fund for the Promotion of Research at the Technion, and by Technion VPR fund 192–198.     

Three models for the homotopy theory of homotopy theories

Given any model category, or more generally any category with weak equivalences, its simplicial localization is a simplicial category which can rightfully be called the “homotopy theory” of the model category. There is a model category structure on the category of simplicial categories, so taking its simplicial localization yields a “homotopy theory of homotopy theories”. In this paper we show that there are two different categories of diagrams of simplicial sets, each equipped with an appropriate definition of weak equivalence, such that the resulting homotopy theories are each equivalent to the homotopy theory arising from the model category structure on simplicial categories. Thus, any of these three categories with the respective weak equivalences could be considered a model for the homotopy theory of homotopy theories. One of them in particular, Rezk’s complete Segal space model category structure on the category of simplicial spaces, is much more convenient from the perspective of making calculations and therefore obtaining information about a given homotopy theory.     

The octahedral algorithm,a new simplicial fixed point algorithm

A new variable dimension simplicial algorithm for the computation of solutions of systems of nonlinear equations or the computation of fixed points is presented. It uses the restrart technique of Merrill to improve the accuracy of the solution. The algorithm is shown to converge quadratically under certain conditions. The algorithm should be efficient and relatively easy to implement.Partially supported by the Western Michigan University Sabbatical and Faculty Research Funds.     

Buchsbaum* complexes

A class of finite simplicial complexes, which we call Buchsbaum* over a field, is introduced. Buchsbaum* complexes generalize triangulations of orientable homology manifolds as well as doubly Cohen-Macaulay complexes. By definition, the Buchsbaum* property depends only on the geometric realization and the field. Characterizations in terms of simplicial homology are given. It is proved that Buchsbaum* complexes are doubly Buchsbaum. Various constructions, among them one which generalizes convex ear decompositions, are shown to yield Buchsbaum* simplicial complexes. Graph theoretic and enumerative properties of Buchsbaum* complexes are investigated.     

Simplicial Endomorphisms

The monoids of simplicial endomorphisms, i.e., the monoids of endomorphisms in the simplicial category, are submonoids of monoids one finds in Temperley–Lieb algebras, and as the monoids of Temperley–Lieb algebras are linked to situations where an endofunctor is adjoint to itself, so the monoids of simplicial endomorphisms are linked to arbitrary adjoint situations. This link is established through diagrams of the kind found in Temperley–Lieb algebras. Results about these matters, which were previously prefigured up to a point, are here surveyed and reworked. A presentation of monoids of simplicial endomorphisms by generators and relations has been given a long time ago. Here a closely related presentation is given, with completeness proved in a new and self-contained manner.     

Higher ?ech Theory

We introduce a notion of cover of level n for a topological space, or more generally any Grothendieck site, with the key property that simplicial homotopy classes computed along the filtered diagram of n-covers biject with global homotopy classes when the target is an n-type. When the target is an Eilenberg–MacLane sheaf, this specializes to computing derived functor cohomology, up to degree n, via simplicial homotopy classes taken along n-covers. Our approach is purely simplicial and combinatorial.     

A simplicial decomposition algorithm for solving the variational inequality formulation of the general traffic assignment problem for large scale networks

Summary The class of simplicial decomposition methods has been shown to constitute efficient tools for the solution of the variational inequality formulation of the general traffic assignment problem. This paper presents a particular implementation of such an algorithm, with emphasis on its ability to solve large scale problems efficiently. The convergence of the algorithm is monitored by the primal gap function, which arises naturally in simplicial decomposition schemes. The gap function also serves as an instrument for maintaining a reasonable subproblem size, through its use in column dropping criteria. The small dimension and special structure of the subproblems also allows for the use of very efficient algorithms; several algorithms in the class of linearization methods are presented. When restricting the number of retained extremal flows in a simplicial decomposition scheme, the number of major iterations tends to increase. For large networks the shortest path calculations, leading to new extremal flow generation, require a large amount of the total computation time. A special study is therefore made in order to choose the most efficient extremal flow generation technique. Computational results on symmetric problems are presented for networks of some large cities, and on asymmetric problems for some of the networks used in the literature. Computational results for bimodal models of some large cities leading to asymmetric problems are also discussed.     

Special Eccentric Vertices for the Class of Chordal Graphs and Related Classes

A vertex is simplicial if the vertices of its neighborhood are pairwise adjacent. It is known that, for every vertex v of a chordal graph, there exists a simplicial vertex among the vertices at maximum distance from v. Here we prove similar properties in other classes of graphs related to that of chordal graphs. Those properties will not be in terms of simplicial vertices, but in terms of other types of vertices that are used to characterize those classes.     

Homotopy simplicial faces and the homology of realizations of simplicial topological spaces

The notion of a differential module with homotopy simplicial faces is introduced, which is a homotopy analog of the notion of a differential module with simplicial faces. The homotopy invariance of the structure of a differential module with homotopy simplicial faces is proved. Relationships between the construction of a differential module with homotopy simplicial faces and the theories of A _∞-algebras and D _∞-differential modules are found. Applications of the method of homotopy simplicial faces to describing the homology of realizations of simplicial topological spaces are presented.     

On the exhaustivity of simplicial partitioning

During the last 40 years, simplicial partitioning has been shown to be highly useful, including in the field of nonlinear optimization, specifically global optimization. In this article, we consider results on the exhaustivity of simplicial partitioning schemes. We consider conjectures on this exhaustivity which seem at first glance to be true (two of which have been stated as true in published articles). However, we will provide counter-examples to these conjectures. We also provide a new simplicial partitioning scheme, which provides a lot of freedom, whilst guaranteeing exhaustivity.