An algorithm for the difference between set covers

A set cover for a set S is a collection C of special subsets whose union is S. Given covers A and B for two sets, the set-cover difference problem is to construct a new cover for the elements covered by A but not B. Applications include testing equivalence of set covers and maintaining a set cover dynamically. In this paper, we solve the set-cover difference problem by defining a difference operation A-B, which turns out to be a pseudocomplement on a distributive lattice. We give an algorithm for constructing this difference, and show how to implement the algorithm for two examples with applications in computer science: face covers on a hypercube, and rectangle covers on a grid. We derive an upper bound on the time complexity of the algorithm, and give upper and lower bounds on complexity for face covers and rectangle covers.     

Using machine learning to predict catastrophes in dynamical systems

Nonlinear dynamical systems, which include models of the Earth’s climate, financial markets and complex ecosystems, often undergo abrupt transitions that lead to radically different behavior. The ability to predict such qualitative and potentially disruptive changes is an important problem with far-reaching implications. Even with robust mathematical models, predicting such critical transitions prior to their occurrence is extremely difficult. In this work, we propose a machine learning method to study the parameter space of a complex system, where the dynamics is coarsely characterized using topological invariants. We show that by using a nearest neighbor algorithm to sample the parameter space in a specific manner, we are able to predict with high accuracy the locations of critical transitions in parameter space.     

The bitwisted Cartesian model for the free loop fibration

Using the notion of truncating twisting function from a simplicial set to a cubical set a special, bitwisted, Cartesian product of these sets is defined. For the universal truncating twisting function, the (co)chain complex of the corresponding bitwisted Cartesian product agrees with the standard Cartier (Hochschild) chain complex of the simplicial (co)chains. The modelling polytopes Fn are constructed. An explicit diagonal on Fn is defined and a multiplicative model for the free loop fibration ΩY→ΛY→Y is obtained. As an application we establish an algebra isomorphism H^∗(ΛY;Z)≈S(U)⊗Λ(s−1U) for the polynomial cohomology algebra H^∗(Y;Z)=S(U).     

Simple homotopy types of Hom-complexes, neighborhood complexes, Lovász complexes, and atom crosscut complexes

In this paper we provide concrete combinatorial formal deformation algorithms, namely sequences of elementary collapses and expansions, which relate various previously extensively studied families of combinatorially defined polyhedral complexes.To start with, we give a sequence of elementary collapses leading from the barycentric subdivision of the neighborhood complex to the Lovász complex of a graph. Then, for an arbitrary lattice L we describe a formal deformation of the barycentric subdivision of the atom crosscut complex Γ(L) to its order complex . We proceed by proving that the complex of sets bounded from below J(L) can also be collapsed to .Finally, as a pinnacle of our project, we apply all these results to certain graph complexes. Namely, by describing an explicit formal deformation, we prove that, for any graph G, the neighborhood complex N(G) and the polyhedral complex Hom(K₂,G) have the same simple homotopy type in the sense of Whitehead.     

On the algorithmic complexity of coloring simple hypergraphs and steiner triple systems

In this paper we establish that decidingt-colorability for a simplek-graph whent≧3,k≧3 is NP-complete. Next, we establish that if there is a polynomial time algorithm for finding the chromatic number of a Steiner Triple system then there exists a polynomial time “approximation” algorithm for the chromatic number of simple 3-graphs. Finally, we show that the existence of such an approximation algorithm would imply that P=NP. Dedicated to Paul Erdős on his seventieth birthday     

Decomposition of submodular functions

A decomposition theory for submodular functions is described. Any such function is shown to have a unique decomposition consisting of indecomposable functions and certain highly decomposable functions, and the latter are completely characterized. Applications include decompositions of hypergraphs based on edge and vertex connectivity, the decomposition of matroids based on three-connectivity, the Gomory—Hu decomposition of flow networks, and Fujishige’s decomposition of symmetric submodular functions. Efficient decomposition algorithms are also discussed.     

The Buchsbaum property of symbolic powers of Stanley-Reisner ideals of dimension 1

Let S be a polynomial ring and I be the Stanley-Reisner ideal of a simplicial complex Δ. The purpose of this paper is investigating the Buchsbaum property of S/I^(r) when Δ is pure dimension 1. We shall characterize the Buchsbaumness of S/I^(r) in terms of the graphical property of Δ. That is closely related to the characterization of the Cohen-Macaulayness of S/I^(r) due to the first author and N.V. Trung.     

Discrete Morse theory for totally non-negative flag varieties

In a seminal 1994 paper Lusztig (1994) [26], Lusztig extended the theory of total positivity by introducing the totally non-negative part (G/P)_?0 of an arbitrary (generalized, partial) flag variety G/P. He referred to this space as a “remarkable polyhedral subspace”, and conjectured a decomposition into cells, which was subsequently proven by the first author Rietsch (1998) [33]. In Williams (2007) [40] the second author made the concrete conjecture that this cell decomposed space is the next best thing to a polyhedron, by conjecturing it to be a regular CW complex that is homeomorphic to a closed ball. In this article we use discrete Morse theory to prove this conjecture up to homotopy-equivalence. Explicitly, we prove that the boundaries of the cells are homotopic to spheres, and the closures of cells are contractible. The latter part generalizes a result of Lusztig's (1998) [28], that (G/P)_?0 - the closure of the top-dimensional cell - is contractible. Concerning our result on the boundaries of cells, even the special case that the boundary of the top-dimensional cell (G/P)_>0 is homotopic to a sphere, is new for all G/P other than projective space.     

Perfect state transfer in cubelike graphs

Suppose C is a subset of non-zero vectors from the vector space . The cubelike graphX(C) has as its vertex set, and two elements of are adjacent if their difference is in C. If M is the d×|C| matrix with the elements of C as its columns, we call the row space of M the code of X. We use this code to study perfect state transfer on cubelike graphs. Bernasconi et al. have shown that perfect state transfer occurs on X(C) at time π/2 if and only if the sum of the elements of C is not zero. Here we consider what happens when this sum is zero. We prove that if perfect state transfer occurs on a cubelike graph, then it must take place at time τ=π/2D, where D is the greatest common divisor of the weights of the code words. We show that perfect state transfer occurs at time π/4 if and only if D=2 and the code is self-orthogonal.     

On construction ofk-wise independent random variables

A 0–1probability space is a probability space (, 2,P), where the sample space -{0, 1} ⁿ for somen. A probability space isk-wise independent if, whenY _i is defined to be theith coordinate or the randomn-vector, then any subset ofk of theY _i 's is (mutually) independent, and it is said to be a probability spacefor p ₁,p ₂, ...,p _n ifP[Y _i =1]=p _i .We study constructions ofk-wise independent 0–1 probability spaces in which thep _i 's are arbitrary. It was known that for anyp ₁,p ₂, ...,p _n , ak-wise independent probability space of size always exists. We prove that for somep ₁,p ₂, ...,p _n [0,1],m(n,k) is a lower bound on the size of anyk-wise independent 0–1 probability space. For each fixedk, we prove that everyk-wise independent 0–1 probability space when eachp _i =k/n has size (n _k ). For a very large degree of independence —k=[n], for >1/2- and allp _i =1/2, we prove a lower bound on the size of . We also give explicit constructions ofk-wise independent 0–1 probability spaces.This author was supported in part by NSF grant CCR 9107349.This research was supported in part by the Israel Science Foundation administered by the lsrael Academy of Science and Humanities and by a grant of the Israeli Ministry of Science and Technology.     

On t-structures and torsion theories induced by compact objects

First, we show that a compact object C in a triangulated category, which satisfies suitable conditions, induces a t-structure. Second, in an abelian category we show that a complex P· of small projective objects of term length two, which satisfies suitable conditions, induces a torsion theory. In the case of module categories, using a torsion theory, we give equivalent conditions for P· to be a tilting complex. Finally, in the case of artin algebras, we give a one-to-one correspondence between tilting complexes of term length two and torsion theories with certain conditions.     

Monodromy eigenvalues and zeta functions with differential forms

For a complex polynomial or analytic function f, there is a strong correspondence between poles of the so-called local zeta functions or complex powers ∫|f|^2sω, where the ω are C^∞ differential forms with compact support, and eigenvalues of the local monodromy of f. In particular Barlet showed that each monodromy eigenvalue of f is of the form , where s₀ is such a pole. We prove an analogous result for similar p-adic complex powers, called Igusa (local) zeta functions, but mainly for the related algebro-geometric topological and motivic zeta functions.     

Cubical Subdivisions and Local h-Vectors

Face numbers of triangulations of simplicial complexes were studied by Stanley by use of his concept of a local h-vector. It is shown that a parallel theory exists for cubical subdivisions of cubical complexes, in which the role of the h-vector of a simplicial complex is played by the (short or long) cubical h-vector of a cubical complex, defined by Adin, and the role of the local h-vector of a triangulation of a simplex is played by the (short or long) cubical local h-vector of a cubical subdivision of a cube. The cubical local h-vectors are defined in this paper and are shown to share many of the properties of their simplicial counterparts. Generalizations to subdivisions of locally Eulerian posets are also discussed.     

A random 1-011-011-01algorithm for depth first search

In this paper we present a fast parallel algorithm for constructing a depth first search tree for an undirected graph. The algorithm is anRNC algorithm, meaning that it is a probabilistic algorithm that runs in polylog time using a polynomial number of processors on aP-RAM. The run time of the algorithm isO(T _MM(n) log³ n), and the number of processors used isP _MM (n) whereT _MM(n) andP _MM(n) are the time and number of processors needed to find a minimum weight perfect matching on ann vertex graph with maximum edge weightn.This research was done while the first author was visiting the Mathematical Research Institute in Berkeley. Research supported in part by NSF grant 8120790.Supported by Air Force Grant AFOSR-85-0203A.     

Families of cuts with the MFMC-property

A family ℱ of cuts of an undirected graphG=(V, E) is known to have the weak MFMC-property if (i) ℱ is the set ofT-cuts for someT⊆V with |T| even, or (ii) ℱ is the set of two-commodity cuts ofG, i.e. cuts separating any two distinguished pairs of vertices ofG, or (iii) ℱ is the set of cuts induced (in a sense) by a ring of subsets of a setT⊆V. In the present work we consider a large class of families of cuts of complete graphs and prove that a family from this class has the MFMC-property if and only if it is one of (i), (ii), (iii).     

Baire space and second category extensions

Nearness structures induced by a T₁ second category or Baire space strict extension are characterized. Given a T₁ topological space it is shown that there exists a one-to-one correspondence between compatible nearness structures satisfying certain stated conditions and T₁ Baire space strict extensions of the space, up to the usual equivalence. A similar result is provided for second category T₁ strict extensions.     

Paired domination on interval and circular-arc graphs

We study the paired-domination problem on interval graphs and circular-arc graphs. Given an interval model with endpoints sorted, we give an O(m+n) time algorithm to solve the paired-domination problem on interval graphs. The result is extended to solve the paired-domination problem on circular-arc graphs in O(m(m+n)) time.     

Minimizing setups in ordered sets of fixed width

A simply polynomial time algorithm is given for computing the setup number, or jump number, of an ordered set with fixed width. This arises as an interesting application of a polynomial time algorithm for solving a more general weighted problem in precedence constrained scheduling.     

A las vegas rnc algorithm for maximum matching

Recently two randomized algorithms were discovered that find a maximum matching in an arbitrary graph in polylog time, when run on a parallel random access machine. Both are Monte Carlo algorithms — they have the drawback that with non-zero probability the output is a non-maximum matching. We use the min-max formula for the size of a maximum matching to convert any Monte Carlo maximum matching algorithm into a Las Vegas (error-free) one. The resulting algorithm returns (with high probability) a maximum matching and a certificate proving that the matching is indeed maximum. Research supported by DARPA grant N00039-84-C-0098 and by a US Army Research Office fellowship.