On the Stanley–Reisner ideal of an expanded simplicial complex

Let Δ be a simplicial complex. We study the expansions of Δ mainly to see how the algebraic and combinatorial properties of Δ and its expansions are related to each other. It is shown that Δ is Cohen–Macaulay, sequentially Cohen–Macaulay, Buchsbaum or k-decomposable, if and only if an arbitrary expansion of Δ has the same property. Moreover, some homological invariants like the regularity and the projective dimension of the Stanley–Reisner ideals of Δ and those of their expansions are compared.     

Products of Menger spaces: A combinatorial approach

We construct Menger subsets of the real line whose product is not Menger in the plane. In contrast to earlier constructions, our approach is purely combinatorial. The set theoretic hypothesis used in our construction is far milder than earlier ones, and holds in almost all canonical models of set theory of the real line. On the other hand, we establish productive properties for versions of Menger's property parameterized by filters and semifilters. In particular, the Continuum Hypothesis implies that every productively Menger set of real numbers is productively Hurewicz, and each ultrafilter version of Menger's property is strictly between Menger's and Hurewicz's classic properties. We include a number of open problems emerging from this study.     

A unified framework for testing linear‐invariant properties

In the study of property testing, a particularly important role has been played by linear invariant properties, i.e., properties of Boolean functions on the hypercube which are closed under linear transformations of the domain. Examples of such properties include linearity, Reed‐Muller codes, and Fourier sparsity. In this work, we describe a framework that can lead to a unified analysis of the testability of all linear‐invariant properties, drawing on techniques from additive combinatorics and from graph theory. Our main contributions here are the following:

相似文献   

Semivalues as power indices

A restricted notion of semivalue as a power index, i.e. as a value on the lattice of simple games, is axiomatically introduced by using the symmetry, positivity and dummy player standard properties together with the transfer property. The main theorem, that parallels the existing statement for semivalues on general cooperative games, provides a combinatorial definition of each semivalue on simple games in terms of weighting coefficients, and shows the crucial role of the transfer property in this class of games. A similar characterization is also given that refers to unanimity coefficients, which describe the action of the semivalue on unanimity games. We then combine the notion of induced semivalue on lower cardinalities with regularity and obtain a series of characteristic properties of regular semivalues on simple games, that concern null and nonnull players, subgames, quotients, and weighted majority games.     

Szemerédi’s Lemma for the Analyst

Szemerédi’s regularity lemma is a fundamental tool in graph theory: it has many applications to extremal graph theory, graph property testing, combinatorial number theory, etc. The goal of this paper is to point out that Szemerédi’s lemma can be thought of as a result in analysis. We show three different analytic interpretations. Received: February 2006 Revision: April 2006 Accepted: April 2006     

Regular combinatorial maps

The classical approach to maps is by cell decomposition of a surface. A combinatorial map is a graph-theoretic generalization of a map on a surface. Besides maps on orientable and non-orientable surfaces, combinatorial maps include tessellations, hypermaps, higher dimensional analogues of maps, and certain toroidal complexes of Coxeter, Shephard, and Grünbaum. In a previous paper the incidence structure, diagram, and underlying topological space of a combinatorial map were investigated. This paper treats highly symmetric combinatorial maps. With regularity defined in terms of the automorphism group, necessary and sufficient conditions for a combinatorial map to be regular are given both graph- and group-theoretically. A classification of regular combinatorial maps on closed simply connected manifolds generalizes the well-known classification of metrically regular polytopes. On any closed manifold with nonzero Euler characteristic there are at most finitely many regular combinatorial maps. However, it is shown that, for nearly any diagram D, there are infinitely many regular combinatorial maps with diagram D. A necessary and sufficient condition for the regularity of rank 3 combinatorial maps is given in terms of Coxeter groups. This condition reveals the difficulty in classifying the regular maps on surfaces. In light of this difficulty an algorithm for generating a large class of regular combinatorial maps that are obtained as cyclic coverings of a given regular combinatorial map is given.     

Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization

The strong conical hull intersection property and bounded linear regularity are properties of a collection of finitely many closed convex intersecting sets in Euclidean space. These fundamental notions occur in various branches of convex optimization (constrained approximation, convex feasibility problems, linear inequalities, for instance). It is shown that the standard constraint qualification from convex analysis implies bounded linear regularity, which in turn yields the strong conical hull intersection property. Jameson’s duality for two cones, which relates bounded linear regularity to property (G), is re-derived and refined. For polyhedral cones, a statement dual to Hoffman’s error bound result is obtained. A sharpening of a result on error bounds for convex inequalities by Auslender and Crouzeix is presented. Finally, for two subspaces, property (G) is quantified by the angle between the subspaces. Received October 1, 1997 / Revised version received July 21, 1998? Published online June 11, 1999     

Reguläre Inzidenzkomplexe I

The concept of regular incidence-complexes generalizes the notion of regular polyhedra in a combinatorial sense. A regular incidence-complex is a partially ordered set with regularity defined by certain transitivity properties of its automorphism group. The concept includes all regular d-polytopes and all regular complex d-polytopes as well as many geometries and well-known configurations.     

A combinatorial proof of a fixed point property

A class of finite simplicial complexes, called pseudo cones, is developed that has a number of useful combinatorial properties. A partially ordered set is a pseudo cone if its order complex is a pseudo cone. Pseudo cones can be constructed from other pseudo cones in a number of ways. Pseudo cone ordered sets include finite dismantlable ordered sets and finite truncated noncomplemented lattices. The main result of the paper is a combinatorial proof of the fixed simplex property for finite pseudo cones in which a combinatorial structure is constructed that relates fixed simplices to one another. This gives combinatorial proofs of some well known non-constructive results in the fixed point theory of finite partially ordered sets.     

Strong CHIP, normality, and linear regularity of convex sets

We extend the property (N) introduced by Jameson for closed convex cones to the normal property for a finite collection of convex sets in a Hilbert space. Variations of the normal property, such as the weak normal property and the uniform normal property, are also introduced. A dual form of the normal property is derived. When applied to closed convex cones, the dual normal property is the property (G) introduced by Jameson. Normality of convex sets provides a new perspective on the relationship between the strong conical hull intersection property (strong CHIP) and various regularity properties. In particular, we prove that the weak normal property is a dual characterization of the strong CHIP, and the uniform normal property is a characterization of the linear regularity. Moreover, the linear regularity is equivalent to the fact that the normality constant for feasible direction cones of the convex sets at is bounded away from 0 uniformly over all points in the intersection of these convex sets.

     

Toughness and Delaunay triangulations

We show that nondegenerate Delaunay triangulations satisfy a combinatorial property called 1-toughness. A graphG is1-tough if for any setP of vertices,c(G–P)|G|, wherec(G–P) is the number of components of the graph obtained by removingP and all attached edges fromG, and |G| is the number of vertices inG. This property arises in the study of Hamiltonian graphs: all Hamiltonian graphs are 1-tough, but not conversely. We also show that all Delaunay triangulationsT satisfy the following closely related property: for any setP of vertices the number of interior components ofT–P is at most |P|–2, where an interior component ofT–P is a component that contains no boundary vertex ofT. These appear to be the first nontrivial properties of a purely combinatorial nature to be established for Delaunay triangulations. We give examples to show that these bounds are best possible and are independent of one another. We also characterize the conditions under which a degenerate Delaunay triangulation can fail to be 1-tough. This characterization leads to a proof that all graphs that can be realized as polytopes inscribed in a sphere are 1-tough. One consequence of the toughness results is that all Delaunay triangulations and all inscribable graphs have perfect matchings.This research was sponsored in part by the National Science Foundation under Grant IRI-88-02457.     

Embedding Semigroups into Idempotent Generated Ones

We present a concrete model of the embedding due to Pastijn and Yan of a semigroup S into an idempotent generated semigroup now in terms of a Rees matrix semigroup over S¹. The paper starts with a comparison of the two embeddings. Studying the properties of this embedding, we prove that it is functorial. We show that a number of usual semigroup properties is preserved by this embedding, such as periodicity, finiteness, the cryptic property, regularity, complete semisimplicity and various local properties, but complete regularity is not one of them.     

Lah numbers and Lindström's lemma

We provide a combinatorial interpretation of Lah numbers by means of planar networks. Henceforth, as a consequence of Lindström's lemma, we conclude that the related Lah matrix possesses a remarkable property of total non-negativity.     

Embedding Semigroups into Idempotent Generated Ones

We present a concrete model of the embedding due to Pastijn and Yan of a semigroup S into an idempotent generated semigroup now in terms of a Rees matrix semigroup over S¹. The paper starts with a comparison of the two embeddings. Studying the properties of this embedding, we prove that it is functorial. We show that a number of usual semigroup properties is preserved by this embedding, such as periodicity, finiteness, the cryptic property, regularity, complete semisimplicity and various local properties, but complete regularity is not one of them.     

Strong metric subregularity of mappings in variational analysis and optimization

Although the property of strong metric subregularity of set-valued mappings has been present in the literature under various names and with various (equivalent) definitions for more than two decades, it has attracted much less attention than its older “siblings”, the metric regularity and the strong (metric) regularity. The purpose of this paper is to show that the strong metric subregularity shares the main features of these two most popular regularity properties and is not less instrumental in applications. We show that the strong metric subregularity of a mapping F acting between metric spaces is stable under perturbations of the form $f+F$, where f is a function with a small calmness constant. This result is parallel to the Lyusternik–Graves theorem for metric regularity and to the Robinson theorem for strong regularity, where the perturbations are represented by a function f with a small Lipschitz constant. Then we study perturbation stability of the same kind for mappings acting between Banach spaces, where f is not necessarily differentiable but admits a set-valued derivative-like approximation. Strong metric q-subregularity is also considered, where q is a positive real constant appearing as exponent in the definition. Rockafellar's criterion for strong metric subregularity involving injectivity of the graphical derivative is extended to mappings acting in infinite-dimensional spaces. A sufficient condition for strong metric subregularity is established in terms of surjectivity of the Fréchet coderivative, and it is shown by a counterexample that surjectivity of the limiting coderivative is not a sufficient condition for this property, in general. Then various versions of Newton's method for solving generalized equations are considered including inexact and semismooth methods, for which superlinear convergence is shown under strong metric subregularity. As applications to optimization, a characterization of the strong metric subregularity of the KKT mapping is obtained, as well as a radius theorem for the optimality mapping of a nonlinear programming problem. Finally, an error estimate is derived for a discrete approximation in optimal control under strong metric subregularity of the mapping involved in the Pontryagin principle.     

Algorithmic Aspects of Tree Amalgamation

The amalgamation of leaf-labeled trees into a single (super)tree that “displays” each of the input trees is an important problem in classification. We discuss various approaches to this problem and show that a simple and well-known polynomial-time algorithm can be used to solve this problem whenever the input set of trees contains a minimum size subset that uniquely determines the supertree. Our results exploit a recently established combinatorial property concerning the structure of such collections of trees.     

Decomposition of Green polynomials of type A and Springer modules for hooks and rectangles

This paper deals with graded representations of the symmetric group on the cohomology ring of flags fixed by a unipotent matrix. We consider a combinatorial property, called the “coincidence of dimension” of the graded representations, and give an interpretation in terms of representation theory of the symmetric group in the case where the corresponding partition of the unipotent matrix is a hook or a rectangle. The interpretation is equivalent to a recursive formula of Green polynomials at roots of unity.     

On regularity concepts in variational analysis

The paper offers a new approach that allows unifying various regularity concepts used in variational analysis: the most fundamental local regularity triad (openness at a linear rate – metric regularity – Aubin property), the calmness–subregularity pair, directional regularity, upper Lipschitz continuity etc. The main new element of the approach is the appearance of a new parameter which is a set to which regularity is related (whence the term “relative regularity” used in the paper to name the general property). The main emphasis is put on characterizations of relative regularity and its stability with respect to additive perturbations of the (generally set-valued) mapping. A discussion of a relative extension of strong regularity properties concludes the paper.     

The Combinatorics of a Class of Representation Functions

In the study of the irreducible representations of the unitary groupU(n), one encounters a class of polynomials defined onn²indeterminatesz_ij, 1i, jn, which may be arranged into ann×nmatrix arrayZ=(z_ij). These polynomials are indexed by double Gelfand patterns, or equivalently, by pairs of column strict Young tableaux of the same shape. Using the double labeling property, one may define a square matrixD(Z), whose elements are the double-indexed polynomials. These matrices possess the remarkable “group multiplication property”D(XY)=D(X) D(Y) for arbitrary matricesXandY, even though these matrices may be singular. ForZ=UU(n), these matrices give irreducible unitary representations ofU(n). These results are known, but not always fully proved from the extensive physics literature on representation of the unitary groups, where they are often formulated in terms of the boson calculus, and the multiplication property is unrecognized. The generality of the multiplication property is the key to understanding group representation theory from the purview of combinatorics. The combinatorial structure of the general polynomials is expected to be intricate, and in this paper, we take the first step to explore the combinatorial aspects of a special class which can be defined in terms of the set of integral matrices with given row and column sums. These special polynomials are denoted byL_{α, β}(Z), whereαandβare integral vectors representing the row sums and column sums of a class of integral matrices. We present a combinatorial interpretation of the multiplicative properties of these polynomials. We also point out the connections with MacMahon's Master Theorem and Schwinger's inner product formula, which is essentially equivalent to MacMahon's Master Theorem. Finally, we give a formula for the double Pfaffian, which is crucial in the studies of the generating function of the 3n−jcoefficients in angular momentum theory. We also review the background of the general polynomials and give some of their properties.