Combinatorial Groupoids,Cubical Complexes,and the Lovász Conjecture

This paper lays the foundation for a theory of combinatorial groupoids that allows us to use concepts like “holonomy”, “parallel transport”, “bundles”, “combinatorial curvature”, etc. in the context of simplicial (polyhedral) complexes, posets, graphs, polytopes and other combinatorial objects. We introduce a new, holonomy-type invariant for cubical complexes, leading to a combinatorial “Theorema Egregium” for cubical complexes that are non-embeddable into cubical lattices. Parallel transport of Hom-complexes and maps is used as a tool to extend Babson–Kozlov–Lovász graph coloring results to more general statements about nondegenerate maps (colorings) of simplicial complexes and graphs. The author was supported by grants 144014 and 144026 of the Serbian Ministry of Science and Technology.     

A combinatorial Lefschetz fixed point formula

We define a class of simplicial maps — those which are “expanding directions preserving” — from a barycentric subdivision to the original simplicial complex. These maps naturally induce a self map on the links of their fixed points. The local index at a fixed point of such a map turns out to be the Lefschetz number of the induced map on the link of the fixed point in relative homology. We also show that a weakly hyperbolic [4] simplicial map sdⁿK →K is expanding directions preserving.     

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

On the Stanley ring of cubical complex

We investigate the properties of the Stanley ring of a cubical complex, a cubical analogue of the Stanley-Reisner ring of a simplicial complex. We compute its Hilbert series in terms of thef-vector, and prove that by taking the initial ideal of the defining relations, with respect to the reverse lexicographic order, we obtain the defining relations of the Stanley-Reisner ring of the triangulation via “pulling the vertices” of the cubical complex. Applying an old idea of Hochster we see that this ring is Cohen-Macaulay when the complex is shellable, and we show that its defining ideal is generated by quadrics when the complex is also a subcomplex of the boundary complex of a convex cubical polytope. We present a cubical analogue of balanced Cohen-Macaulay simplicial complexes: the class of edge-orientable shellable cubical complexes. Using Stanley's results about balanced Cohen-Macaulay simplicial complexes and the degree two homogeneous generating system of the defining ideal, we obtain an infinite set of examples for a conjecture of Eisenbud, Green, and Harris. This conjecture says that theh-vector of a polynomial ring inn variables modulo an ideal which has ann-element homogeneous system of parameters of degree two, is thef-vector of a simplicial complex.     

n-connectedness in pure 2-complexes

A graph is a 1-dimensional simplicial complex. In this work we study an interpretation of “n-connectedness” for 2-dimensional simplicial complexes. We prove a 2-dimensional analogue of a theorem by Whitney for graphs: Theorem (A Whitney type theorem for pure 2-complexes).Let G be a pure 2-complex with no end-triangles. Then G is n-connected if and only if the valence of e is at least n for every interior edge e of G, and there does not exist a juncture set J of less than n edges of G. Examples ofn-connected pure 2-complexes are then given, and some consequences are proved.     

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.     

Decompositions of simplicial balls and spheres with knots consisting of few edges

Constructibility is a condition on pure simplicial complexes that is weaker than shellability. In this paper we show that non-constructible triangulations of the d-dimensional sphere exist for every . This answers a question of Danaraj and Klee [10]; it also strengthens a result of Lickorish [16] about non-shellable spheres. Furthermore, we provide a hierarchy of combinatorial decomposition properties that follow from the existence of a non-trivial knot with “few edges” in a 3-sphere or 3-ball, and a similar hierarchy for 3-balls with a knotted spanning arc that consists of “few edges.” Received March 15, 1999 / in final form August 19, 1999 / Published online July 3, 2000     

A Discrete Laplace–Beltrami Operator for Simplicial Surfaces

We define a discrete Laplace–Beltrami operator for simplicial surfaces (Definition 16). It depends only on the intrinsic geometry of the surface and its edge weights are positive. Our Laplace operator is similar to the well known finite-elements Laplacian (the so called “cotan formula”) except that it is based on the intrinsic Delaunay triangulation of the simplicial surface. This leads to new definitions of discrete harmonic functions, discrete mean curvature, and discrete minimal surfaces. The definition of the discrete Laplace–Beltrami operator depends on the existence and uniqueness of Delaunay tessellations in piecewise flat surfaces. While the existence is known, we prove the uniqueness. Using Rippa’s Theorem we show that, as claimed, Musin’s harmonic index provides an optimality criterion for Delaunay triangulations, and this can be used to prove that the edge flipping algorithm terminates also in the setting of piecewise flat surfaces. Research for this article was supported by the DFG Research Unit 565 “Polyhedral Surfaces” and the DFG Research Center Matheon “Mathematics for key technologies” in Berlin.     

The Angle Defect for Odd-Dimensional Simplicial Manifolds

In a 1967 paper, Banchoff stated that a certain type of polyhedral curvature, that applies to all finite polyhedra, was zero at all vertices of an odd-dimensional polyhedral manifold; one then obtains an elementary proof that odd-dimensional manifolds have zero Euler characteristic. In a previous paper, the author defined a different approach to curvature for arbitrary simplicial complexes, based upon a direct generalization of the angle defect. The generalized angle defect is not zero at the simplices of every odd-dimensional manifold. In this paper we use a sequence based upon the Bernoulli numbers to define a variant of the angle defect for finite simplicial complexes that still satisfies a Gauss-Bonnet-type theorem, but is also zero at any simplex of an odd-dimensional simplicial complex K (of dimension at least 3), such that χ(link(ηⁱ, K)) = 2 for all i-simplices ηⁱ of K, where i is an even integer such that 0 ≤ i ≤ n – 1. As a corollary, an elementary proof is given that any such simplicial complex has Euler characteristic zero.     

A filter inexact-restoration method for nonlinear programming

A new iterative algorithm based on the inexact-restoration (IR) approach combined with the filter strategy to solve nonlinear constrained optimization problems is presented. The high level algorithm is suggested by Gonzaga et al. (SIAM J. Optim. 14:646–669, 2003) but not yet implement—the internal algorithms are not proposed. The filter, a new concept introduced by Fletcher and Leyffer (Math. Program. Ser. A 91:239–269, 2002), replaces the merit function avoiding the penalty parameter estimation and the difficulties related to the nondifferentiability. In the IR approach two independent phases are performed in each iteration, the feasibility and the optimality phases. The line search filter is combined with the first one phase to generate a “more feasible” point, and then it is used in the optimality phase to reach an “optimal” point. Numerical experiences with a collection of AMPL problems and a performance comparison with IPOPT are provided.      

Dimension Gaps between Representability and Collapsibility

A simplicial complex K\mathsf{K} is called d -representable if it is the nerve of a collection of convex sets in ℝ ^d ; K\mathsf{K} is d -collapsible if it can be reduced to an empty complex by repeatedly removing a face of dimension at most d−1 that is contained in a unique maximal face; and K\mathsf{K} is d -Leray if every induced subcomplex of K\mathsf{K} has vanishing homology of dimension d and larger. It is known that d-representable implies d-collapsible implies d-Leray, and no two of these notions coincide for d≥2. The famous Helly theorem and other important results in discrete geometry can be regarded as results about d-representable complexes, and in many of these results, “d-representable” in the assumption can be replaced by “d-collapsible” or even “d-Leray.”     

<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 island confinement method for reducing search space in local search methods

Typically local search methods for solving constraint satisfaction problems such as GSAT, WalkSAT, DLM, and ESG treat the problem as an optimisation problem. Each constraint contributes part of a penalty function in assessing trial valuations. Local search examines the neighbours of the current valuation, using the penalty function to determine a “better” neighbour valuation to move to, until finally a solution which satisfies all the constraints is found. In this paper we investigate using some of the constraints as “hard” constraints, that are always satisfied by every trial valuation visited, rather than as part of a penalty function. In this way these constraints reduce the possible neighbours in each move and also the overall search space. The treating of some constraints as hard requires that the space of valuations that are satisfied is “connected” in order to guarantee that a solution can be found from any starting position within the region; thus the concept of islands and the name “island confinement method” arises. Treating some constraints as hard provides new difficulties for the search mechanism since the search space becomes more jagged, and there are more deep local minima. A new escape strategy is needed. To demonstrate the feasibility and generality of our approach, we show how the island confinement method can be incorporated in, and significantly improve, the search performance of two successful local search procedures, DLM and ESG, on SAT problems arising from binary CSPs. A preliminary version of this paper appeared in AAAI’2002.     

Algebraic Shifting and Basic Constructions on Simplicial Complexes

We try to understand the behavior of algebraic shifting with respect to some basic constructions on simplicial complexes, such as union, coning, and (more generally) join. In particular, for the disjoint union of simplicial complexes we prove Δ(K ˙∪ L) = Δ(Δ(K) ˙∪ Δ(L)) (conjectured by Kalai [6]), and for the join we give an example of simplicial complexes K and L for which Δ(K*L)≠Δ(Δ(K)*Δ(L)) (disproving a conjecture by Kalai [6]), where Δ denotes the (exterior) algebraic shifting operator. We develop a ‘homological’ point of view on algebraic shifting which is used throughout this work.     

Statistical hydrodynamics of magnetic fluids. I. the nonequilibrium statistical operator method

The Zubarev nonequilibrium statistical operator is used to describe the generalized hydrodynamic state of a magnetic fluid in an external magnetic field. The magnetic fluid is modeled with “liquid-state” and “magnetic” subsystems described using the classical and quantum statistics methods respectively. Equations of the generalized statistical hydrodynamics for a magnetic fluid in a nonhomogeneous external magnetic field with the Heisenberg spin interaction are derived for “liquid-state” and “magnetic” subsystems characterized by different nonequilibrium temperatures. These equations can be used to describe both the weakly and strongly nonequilibrium states. Some limiting cases are analyzed in which the variables of one of the subsystems can be formally neglected. Translated from Teoreticheskaya i Matematicheskaya Fizika. Vol. 115, No. 1, pp. 132–153, April, 1998.     

On the simplicial <Emphasis Type="Italic">BF</Emphasis> model

This note is a brief introduction to the results on the simplicial BF model obtained by the author in the framework of the program proposed by A. Losev. These results and more comprehensive explanations will be published elsewhere. We regard them as a step toward solving the problem of constructing the combinatorial Chern-Simons theory, proposed by M. Atiyah. We also popularize the algebraic view on the simplicial BF model as a deformation of the de Rham algebra on a manifold in the (yet to be defined) category of “quantum L_∞-algebras.” Bibliography: 2 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 331, 2006, pp. 84–90.     

Generalized cluster complexes via quiver representations

We give a quiver representation theoretic interpretation of generalized cluster complexes defined by Fomin and Reading. Using d-cluster categories defined by Keller as triangulated orbit categories of (bounded) derived categories of representations of valued quivers, we define a d-compatibility degree (−∥−) on any pair of “colored” almost positive real Schur roots which generalizes previous definitions on the noncolored case and call two such roots compatible, provided that their d-compatibility degree is zero. Associated to the root system Φ corresponding to the valued quiver, using this compatibility relation, we define a simplicial complex which has colored almost positive real Schur roots as vertices and d-compatible subsets as simplices. If the valued quiver is an alternating quiver of a Dynkin diagram, then this complex is the generalized cluster complex defined by Fomin and Reading. Supported by the NSF of China (Grants 10471071) and by the Leverhulme Trust through the network ‘Algebras, Representations and Applications’.     

Model selection bias and Freedman’s paradox

In situations where limited knowledge of a system exists and the ratio of data points to variables is small, variable selection methods can often be misleading. Freedman (Am Stat 37:152–155, 1983) demonstrated how common it is to select completely unrelated variables as highly “significant” when the number of data points is similar in magnitude to the number of variables. A new type of model averaging estimator based on model selection with Akaike’s AIC is used with linear regression to investigate the problems of likely inclusion of spurious effects and model selection bias, the bias introduced while using the data to select a single seemingly “best” model from a (often large) set of models employing many predictor variables. The new model averaging estimator helps reduce these problems and provides confidence interval coverage at the nominal level while traditional stepwise selection has poor inferential properties.     

Analysis of space–time discontinuous Galerkin method for nonlinear convection–diffusion problems

The paper presents the theory of the discontinuous Galerkin finite element method for the space–time discretization of a nonstationary convection–diffusion initial-boundary value problem with nonlinear convection and linear diffusion. The problem is not singularly perturbed with dominating convection. The discontinuous Galerkin method is applied separately in space and time using, in general, different space grids on different time levels and different polynomial degrees p and q in space and time dicretization. In the space discretization the nonsymmetric, symmetric and incomplete interior and boundary penalty (NIPG, SIPG, IIPG) approximation of diffusion terms is used. The paper is concerned with the proof of error estimates in “L ²(L ²)”- and “DG”-norm formed by the “L ²(H ¹)”-seminorm and penalty terms. A special technique based on the use of the Gauss–Radau interpolation and numerical integration has been used for the derivation of an abstract error estimate. In the “DG”-norm the error estimates are optimal with respect to the size of the space grid. They are optimal with respect to the time step, if the Dirichlet boundary condition has behaviour in time as a polynomial of degree ≤ q.     

A continuous approach to combinatorial optimization: application of water system pump operations

In this paper, we have suggested a penalty method to modify the combinatorial optimization problem with the linear constraints to a global optimization problem with linear constraints. It also deals with a topic of vital significance of pump operation optimization in a water system. In this connection we have done a lot of work to formulate a model based on a simplified flow volume balance to resolve the problem of optimal pump operation settings of switching “ON” and “OFF” with the reduced gradient method. This global solution approach incorporates some benefits for practical application to a real system as is shown in the case study.