Weak complicial sets I. Basic homotopy theory

This paper develops the foundations of a simplicial theory of weak ω-categories, which builds upon the insights originally expounded by Ross Street in his 1987 paper on oriented simplices. The resulting theory of weak complicial sets provides a common generalisation of the theories of (strict) ω-categories, Kan complexes and Joyal's quasi-categories. We generalise a number of results due to the current author with regard to complicial sets and strict ω-categories to provide an armoury of well behaved technical devices, such as joins and Gray tensor products, which will be used to study the weak ω-category theory of these structures in a series of companion papers. In particular, we establish their basic homotopy theory by constructing a Quillen model structure on the category of stratified simplicial sets whose fibrant objects are the weak complicial sets. As a simple corollary of this work we provide an independent construction of Joyal's model structure on simplicial sets for which the fibrant objects are the quasi-categories.     

Function complexes for diagrams of simplicial sets

Let S be the category of simplicial sets, let D be a small category and let S^D denote the category of D-diagrams of simplicial sets. Then S^D admits a closed simplicial model category structure and the aim of this note is to show that, for every cofibrant diagram X ϵ S^D and every fibrant diagram Y ϵS^D, the homotopy type of the function complex hom(X, Y) can be computed as a homotopy inverse limit involving function complexes in S between the simplicial sets that appear in X and Y.     

Levels in the toposes of simplicial sets and cubical sets

The essential subtoposes of a fixed topos form a complete lattice, which gives rise to the notion of a level in a topos. In the familiar example of simplicial sets, levels coincide with dimensions and give rise to the usual notions of n-skeletal and n-coskeletal simplicial sets. In addition to the obvious ordering, the levels provide a stricter means of comparing the complexity of objects, which is determined by the answer to the following question posed by Bill Lawvere: when does n-skeletal imply k-coskeletal? This paper, which subsumes earlier unpublished work of some of the authors, answers this question for several toposes of interest to homotopy theory and higher category theory: simplicial sets, cubical sets, and reflexive globular sets. For the latter, n-skeletal implies (n+1)-coskeletal but for the other two examples the situation is considerably more complicated: n-skeletal implies (2n−1)-coskeletal for simplicial sets and 2n-coskeletal for cubical sets, but nothing stronger. In a discussion of further applications, we prove that n-skeletal cyclic sets are necessarily (2n+1)-coskeletal.     

Bredon homology and ramified covering G-maps

Let G be a finite group. The objective of this paper is twofold. First we prove that the cellular Bredon homology groups with coefficients in an arbitrary coefficient system M are isomorphic to the homotopy groups of certain topological abelian group. And second, we study ramified covering G-maps of simplicial sets and of simplicial complexes. As an application, we construct a transfer for them in Bredon homology, when M is a Mackey functor. We also show that the Bredon-Illman homology with coefficients in M satisfies the equivariant weak homotopy equivalence axiom in the category of G-spaces.     

Coloring by two-way independent sets

The paper stems from an attempt to investigate a somewhat mysterious phenomenon: conditions which suffice for the existence of a “large” set satisfying certain conditions (e.g., a large independent set in a graph) often suffice (or at least are conjectured to suffice) for the existence of a covering of the ground set by few sets satisfying these conditions (in the example of independent sets in a graph this means that the graph has small chromatic number). We consider two conjectures of this type, on coloring by sets which are “two-way independent”, in the sense of belonging to a matroid and at the same time being independent in a graph sharing its ground set with the matroid. We prove these conjectures for matroids of rank 2. We also consider dual conjectures, on packing bases of a matroid, which are independent in a given graph.     

An obstruction theory for diagrams of simplicial sets

We describe a version of obstruction theory for simplicial sets, which involves canonical obstruction cocycles and then use this to obtain a similar theory for diagrams of simplicial sets. An application of the latter (to the problem of realizing diagrams in the homotopy category by means of diagrams of simplicial sets) will be given in [4].     

On smooth sets of integers

This work studies evenly distributed sets of integers—sets whose quantity within each interval is proportional to the size of the interval, up to a bounded additive deviation. Namely, for ρ,Δ∈R a set A of integers is (ρ,Δ)- smooth if for any interval I of integers; a set A is Δ-smooth if it is (ρ,Δ)-smooth for some real number ρ. The paper introduces the concept of Δ-smooth sets and studies their mathematical structure. It focuses on tools for constructing smooth sets having certain desirable properties and, in particular, on mathematical operations on these sets. Three additional papers by us are build on the work of this paper and present practical applications of smooth sets to common and well-studied scheduling problems.One of the above mathematical operations is composition of sets of natural numbers. For two infinite sets A,B⊆N, the composition of A and B is the subset D of A such that, for all i, the ith member of A is in D if and only if the ith member of N is in B. This operator enables the partition of a (ρ,Δ)-smooth set into two sets that are (ρ₁,Δ)-smooth and (ρ₂,Δ)-smooth, for any ρ₁,ρ₂ and Δ obeying some reasonable restrictions. Another powerful tool for constructing smooth sets is a one-to-one partial function f from the unit interval into the natural numbers having the property that any real interval X⊆[0,1) has a subinterval Y which is ‘very close’ to X s.t. f(Y) is (ρ,Δ)-smooth, where ρ is the length of Y and Δ is a small constant.     

On inner Kan complexes in the category of dendroidal sets

The category of dendroidal sets is an extension of that of simplicial sets, suitable for defining nerves of operads rather than just of categories. In this paper, we prove some basic properties of inner Kan complexes in the category of dendroidal sets. In particular, we extend fundamental results for simplicial sets of Boardman and Vogt, of Cordier and Porter, and of Joyal to dendroidal sets.     

Exclusive and essential sets of implicates of Boolean functions

In this paper we study relationships between CNF representations of a given Boolean function f and certain sets of implicates of f. We introduce two definitions of sets of implicates which are both based on the properties of resolution. The first type of sets, called exclusive sets of implicates, is shown to have a functional property useful for decompositions. The second type of sets, called essential sets of implicates, is proved to possess an orthogonality property, which implies that every CNF representation and every essential set must intersect. The latter property then leads to an interesting question, to which we give an affirmative answer for some special subclasses of Horn Boolean functions.     

Sampling sets and sufficient sets for A

We give new characterizations of the subsets S of the unit disc of the complex plane such that the topology of the space A^−∞ of holomorphic functions of polynomial growth on coincides with the topology of space of the restrictions of the functions to the set S. These sets are called weakly sufficient sets for A^−∞. Our approach is based on a study of the so-called (p,q)-sampling sets which generalize the A^−p-sampling sets of Seip. A characterization of (p,q)-sampling and weakly sufficient rotation invariant sets is included. It permits us to obtain new examples and to solve an open question of Khôi and Thomas.     

Scheduling interfering job sets on parallel machines

We consider bicriteria scheduling on identical parallel machines in a nontraditional context: jobs belong to two disjoint sets, and each set has a different criterion to be minimized. The jobs are all available at time zero and have to be scheduled (non-preemptively) on m parallel machines. The goal is to generate the set of all non-dominated solutions, so the decision maker can evaluate the tradeoffs and choose the schedule to be implemented. We consider the case where, for one of the two sets, the criterion to be minimized is makespan while for the other the total completion time needs to be minimized. Given that the problem is NP-hard, we propose an iterative SPT–LPT–SPT heuristic and a bicriteria genetic algorithm for the problem. Both approaches are designed to exploit the problem structure and generate a set of non-dominated solutions. In the genetic algorithm we use a special encoding scheme and also a unique strategy – based on the properties of a non-dominated solution – to ensure that all parts of the non-dominated front are explored. The heuristic and the genetic algorithm are compared with a time-indexed integer programming formulation for small and large instances. Results indicate that the both the heuristic and the genetic algorithm provide high solution quality and are computationally efficient. The heuristics proposed also have the potential to be generalized for the problem of interfering job sets involving other bicriteria pairs.     

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.     

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

Crisp sets as classes of discontinuous fuzzy sets

This paper aims to show how, by using a threshold-based approach, a path from imprecise information to a crisp ‘decision’ can be developed. It deals with the problem of the logical transformation of a fuzzy set into a crisp set. Such threshold arises from the ideas of contradiction and separation, and allows us to prove that crisp sets can be structurally considered as classes of discontinuous fuzzy sets. It is also shown that continuous fuzzy sets are computationally indistinguishable from some kind of discontinuous fuzzy sets.     

Minimal 1-saturating sets and complete caps in binary projective spaces

In binary projective spaces PG(v,2), minimal 1-saturating sets, including sets with inner lines and complete caps, are considered. A number of constructions of the minimal 1-saturating sets are described. They give infinite families of sets with inner lines and complete caps in spaces with increasing dimension. Some constructions produce sets with an interesting symmetrical structure connected with inner lines, polygons, and orbits of stabilizer groups. As an example we note an 11-set in PG(4,2) called “Pentagon with center”. The complete classification of minimal 1-saturating sets in small geometries is obtained by computer and is connected with the constructions described.     

Fixed point sets of deformations of polyhedra with local cut points

A locally finite simplicial complex is said to be 2-dimensionally connected if is connected. Such spaces exhibit ``classical' behavior in that they all admit deformations with one fixed point, and they admit fixed point free deformations if and only if the Euler characteristic is zero. A result of G.-H. Shi implies that, for non 2-dimensionally connected spaces, the fixed point sets of deformations are equivalent to the fixed point sets of certain combinatorial maps which he calls good displacements. U. K. Scholz combined Shi's results with a theorem of P. Hall to obtain a characterization of all finite simplicial complexes which admit fixed point free deformations. In this paper we begin by explicitly capturing the combinatorial structure of a non 2-dimensionally connected polyhedron in a bipartite graph. We then apply an extended version of Hall's theorem to this graph to get a realization theorem which gives necessary and sufficient conditions for the existence of a deformation with a prescribed finite fixed point set. Scholz's result, and a characterization of all finite simplicial complexes without fixed point free deformations that admit deformations with a single fixed point follow immediately from this realization theorem.

     

A Short Simplicial h -Vector and the Upper Bound Theorem

   Abstract. The Upper Bound Conjecture is verified for a class of odd-dimensional simplicial complexes that in particular includes all Eulerian simplicial complexes with isolated singularities. The proof relies on a new invariant of simplicial complexes—a short simplicial h -vector.     

Fuzzy sets: A topos-logical point of view

Bénabou deduction-categories are defined, with a set of additional assumptions that define categories with formal finite limits (resp. formal regular categories, formal logoi, formal topoi). They are shown to be generalized structures in which higher-order many-sorted languages can be realized. The corresponding Gentzen-type higher-order calculus of sequents is explicited and the soundness theorem is formulated. A construction is given, which associates to each deduction category with formal properties a real category with the corresponding real properties, in a universal way. The corresponding sounddess and completeness properties are formulated for the real categories thus obtained. Fuzzy sets, as generalized by Goguen are introduced, considered as the objects of a category Fuz(H), which turns out to be the real category associated to a very simple formal topos, and thus to be itself a topos: furthermore this is proved to be a Grothendieck topos which is a strictly full epireflective subcategory of Higgs' category of ‘H-valued sets’. Topoi are proposed as generalized fuzzy sets, and deductio0-categories as generalized² fuzzy sets. Some related topics such as Arbib-Manes fuzzy theories, probability, many-valued and fuzzy logics, intensional logic are very briefly touched upon.     

Homotopy type of circle graph complexes motivated by extreme Khovanov homology

It was proven by González-Meneses, Manchón and Silvero that the extreme Khovanov homology of a link diagram is isomorphic to the reduced (co)homology of the independence simplicial complex obtained from a bipartite circle graph constructed from the diagram. In this paper, we conjecture that this simplicial complex is always homotopy equivalent to a wedge of spheres. In particular, its homotopy type, if not contractible, would be a link invariant (up to suspension), and it would imply that the extreme Khovanov homology of any link diagram does not contain torsion. We prove the conjecture in many special cases and find it convincing to generalize it to every circle graph (intersection graph of chords in a circle). In particular, we prove it for the families of cactus, outerplanar, permutation and non-nested graphs. Conversely, we also give a method for constructing a permutation graph whose independence simplicial complex is homotopy equivalent to any given finite wedge of spheres. We also present some combinatorial results on the homotopy type of finite simplicial complexes and a theorem shedding light on previous results by Csorba, Nagel and Reiner, Jonsson and Barmak. We study the implications of our results to knot theory; more precisely, we compute the real-extreme Khovanov homology of torus links T(3, q) and obtain examples of H-thick knots whose extreme Khovanov homology groups are separated either by one or two gaps as long as desired.     

Homology groups of semicubical sets

We study the homology groups of semicubical sets with coefficients in the homological systems of abelian groups. The main theorem states that the groups under consideration are isomorphic to the homology groups of the category of singular cubes. This yields an isomorphism criterion for the homology groups of semicubical sets, the spectral sequence of a locally directed covering, and the spectral sequence of a morphism of semicubical sets.