Peak quasisymmetric functions and Eulerian enumeration

Via duality of Hopf algebras, there is a direct association between peak quasisymmetric functions and enumeration of chains in Eulerian posets. We study this association explicitly, showing that the notion of cd-index, long studied in the context of convex polytopes and Eulerian posets, arises as the dual basis to a natural basis of peak quasisymmetric functions introduced by Stembridge. Thus Eulerian posets having a nonnegative cd-index (for example, face lattices of convex polytopes) correspond to peak quasisymmetric functions having a nonnegative representation in terms of this basis. We diagonalize the operator that associates the basis of descent sets for all quasisymmetric functions to that of peak sets for the algebra of peak functions, and study the g-polynomial for Eulerian posets as an algebra homomorphism.     

Lifting inequalities for polytopes

We present a method of lifting linear inequalities for the flag f-vector of polytopes to higher dimensions. Known inequalities that can be lifted using this technique are the non-negativity of the toric g-vector and that the simplex minimizes the cd-index. We obtain new inequalities for six-dimensional polytopes. In the last section we present the currently best known inequalities for dimensions 5 through 8.     

Squarefree P-modules and the cd-index

In this paper, we introduce a new algebraic concept, which we call squarefree P-modules. This concept is inspired from Karu's proof of the non-negativity of the cd-indices of Gorenstein* posets, and supplies a way to study cd-indices from the viewpoint of commutative algebra. Indeed, by using the theory of squarefree P-modules, we give several new algebraic and combinatorial results on CW-posets. First, we define an analogue of the cd-index for any CW-poset and prove its non-negativity when a CW-poset is Cohen–Macaulay. This result proves that the h-vector of the barycentric subdivision of a Cohen–Macaulay regular CW-complex is unimodal. Second, we prove that the Stanley–Reisner ring of the barycentric subdivision of an odd dimensional Cohen–Macaulay polyhedral complex has the weak Lefschetz property. Third, we obtain sharp upper bounds of the cd-indices of Gorenstein* posets for a fixed rank generating function.     

A Lattice Path Interpretation of the Diamond Product

The diamond product is the poset operation that when applied to the face lattices of two polytopes results in the face lattice of the Cartesian product of the polytopes. Application of the diamond product to two Eulerian posets is a bilinear operation on the cd-indices of the two posets, yielding a product on cd-polynomials. A lattice path interpretation is provided for this product of two cd-monomials.     

On the complete cd-index of a Bruhat interval

We study the non-negativity conjecture of the complete cd-index of a Bruhat interval as defined by Billera and Brenti. For each cd-monomial M we construct a set of paths, such that if a “flip condition” is satisfied, then the number of these paths is the coefficient of the monomial M in the complete cd-index. When the monomial contains at most one d, then the condition follows from Dyer’s proof of Cellini’s conjecture. Hence the coefficients of these monomials are non-negative. We also relate the flip condition to shelling of Bruhat intervals.     

Monotonicity of the cd-index for polytopes

We prove that the cd-index of a convex polytope satisfies a strong monotonicity property with respect to the cd-indices of any face and its link. As a consequence, we prove for d-dimensional polytopes a conjecture of Stanley that the cd-index is minimized on the d-dimensional simplex. Moreover, we prove the upper bound theorem for the cd-index, namely that the cd-index of any d-dimensional polytope with n vertices is at most that of C(n,d), the d-dimensional cyclic polytope with n vertices. Received September 29, 1998; in final form February 8, 1999     

Inequalities for <Emphasis Type="Bold">cd</Emphasis>-Indices of Joins and Products of Polytopes

The cd-index is a polynomial which encodes the flag f-vector of a convex polytope. For polytopes U and V, we determine explicit recurrences for computing the cd-index of the free join and the cd-index of the Cartesian product U x V. As an application of these recurrences, we prove the inequality involving the cd-indices of three polytopes.     

Fundamental polytopes of metric trees via parallel connections of matroids

We tackle the problem of a combinatorial classification of finite metric spaces via their fundamental polytopes, as suggested by Vershik (2010).In this paper we consider a hyperplane arrangement associated to every split pseudometric and, for tree-like metrics, we study the combinatorics of its underlying matroid.

• •We give explicit formulas for the face numbers of fundamental polytopes and Lipschitz polytopes of all tree-like metrics.
• •We characterize the metric trees for which the fundamental polytope is simplicial.

     

Small Chvátal Rank

We propose a variant of the Chvátal-Gomory procedure that will produce a sufficient set of facet normals for the integer hulls of all polyhedra {x : A x ≤ b} as b varies. The number of steps needed is called the small Chvátal rank (SCR) of A. We characterize matrices for which SCR is zero via the notion of supernormality which generalizes unimodularity. SCR is studied in the context of the stable set problem in a graph, and we show that many of the well-known facet normals of the stable set polytope appear in at most two rounds of our procedure. Our results reveal a uniform hypercyclic structure behind the normals of many complicated facet inequalities in the literature for the stable set polytope. Lower bounds for SCR are derived both in general and for polytopes in the unit cube.     

Euler flag enumeration of Whitney stratified spaces

The flag vector contains all the face incidence data of a polytope, and in the poset setting, the chain enumerative data. It is a classical result due to Bayer and Klapper that for face lattices of polytopes, and more generally, Eulerian graded posets, the flag vector can be written as a cd$\mathbf{c}\mathbf{d}$-index, a non-commutative polynomial which removes all the linear redundancies among the flag vector entries. This result holds for regular CW complexes.     

Some explicit solutions of the additive Deligne-Simpson problem and their applications

In this paper we construct three infinite series and two extra triples (E₈ and ) of complex matrices B, C, and A=B+C of special spectral types associated to Simpson's classification in Amer. Math. Soc. Proc. 1 (1992) 157 and Magyar et al. classification in Adv. Math. 141 (1999) 97. This enables us to construct Fuchsian systems of differential equations which generalize the hypergeometric equation of Gauss-Riemann. In a sense, they are the closest relatives of the famous equation, because their triples of spectral flags have finitely many orbits for the diagonal action of the general linear group in the space of solutions. In all the cases except for E₈, we also explicitly construct scalar products such that A, B, and C are self-adjoint with respect to them. In the context of Fuchsian systems, these scalar products become monodromy invariant complex symmetric bilinear forms in the spaces of solutions.When the eigenvalues of A, B, and C are real, the matrices and the scalar products become real as well. We find inequalities on the eigenvalues of A, B, and C which make the scalar products positive-definite.As proved by Klyachko, spectra of three hermitian (or real symmetric) matrices B, C, and A=B+C form a polyhedral convex cone in the space of triple spectra. He also gave a recursive algorithm to generate inequalities describing the cone. The inequalities we obtain describe non-recursively some faces of the Klyachko cone.     

The main invariants of a complex finsler space

In this paper we extend the results obtained in [3], where are investigated the general settings of the two-dimensional complex Finsler manifolds, with respect to a local complex Berwald frame. The geometry of such manifolds is controlled by three real invariants which live on T'M: two horizontal curvature invariants K and W and one vertical curvature invariant I. By means of these invariants are defined both the horizontal and the vertical holomorphic sectional curvatures. The complex Landsberg and Berwald spaces are of particular interest. Complex Berwald spaces coincide with Kähler spaces, in the two – dimensional case. We establish the necessary and sufficient condition under which K is a constant and we obtain a characterization for the Kähler purely Hermitian spaces by the fact K = W = constant and I = 0. For the class of complex Berwald spaces we have K = W = 0. Finally, a classification of two-dimensional complex Finsler spaces for which the horizontal curvature satisfies a special property is obtained.     

Simplex—Karyon Algorithm of Multidimensional Continued Fraction Expansion

A simplex–karyon algorithm for expanding real numbers α = (α₁,..., α _d ) in multidimensional continued fractions is considered. The algorithm is based on a (d + 1)-dimensional superspace S with embedded hyperplanes: a karyon hyperplane K and a Farey hyperplane F. The approximation of numbers α by continued fractions is performed on the hyperplane F, and the degree of approximation is controlled on the hyperplane K. A local ?(r)-strategy for constructing convergents is chosen, with a free objective function ?(r) on the hyperplane K.     

Polytopes of Minimum Positive Semidefinite Rank

The positive semidefinite (psd) rank of a polytope is the smallest $k$ k for which the cone of $k \times k$ k × k real symmetric psd matrices admits an affine slice that projects onto the polytope. In this paper we show that the psd rank of a polytope is at least the dimension of the polytope plus one, and we characterize those polytopes whose psd rank equals this lower bound. We give several classes of polytopes that achieve the minimum possible psd rank including a complete characterization in dimensions two and three.     

On the uniqueness of overcomplete dictionaries, and a practical way to retrieve them

A full-rank under-determined linear system of equations Ax = b has in general infinitely many possible solutions. In recent years there is a growing interest in the sparsest solution of this equation—the one with the fewest non-zero entries, measured by ∥x∥₀. Such solutions find applications in signal and image processing, where the topic is typically referred to as “sparse representation”. Considering the columns of A as atoms of a dictionary, it is assumed that a given signal b is a linear composition of few such atoms. Recent work established that if the desired solution x is sparse enough, uniqueness of such a result is guaranteed. Also, pursuit algorithms, approximation solvers for the above problem, are guaranteed to succeed in finding this solution.Armed with these recent results, the problem can be reversed, and formed as an implied matrix factorization problem: Given a set of vectors {b_i}, known to emerge from such sparse constructions, Ax_i = b_i, with sufficiently sparse representations x_i, we seek the matrix A. In this paper we present both theoretical and algorithmic studies of this problem. We establish the uniqueness of the dictionary A, depending on the quantity and nature of the set {b_i}, and the sparsity of {x_i}. We also describe a recently developed algorithm, the K-SVD, that practically find the matrix A, in a manner similar to the K-Means algorithm. Finally, we demonstrate this algorithm on several stylized applications in image processing.     

More on the combinatorial invariance of Kazhdan-Lusztig polynomials

We prove that the Kazhdan-Lusztig polynomials are combinatorial invariants for intervals up to length 8 in Coxeter groups of type A and up to length 6 in Coxeter groups of type B and D. As a consequence of our methods, we also obtain a complete classification, up to isomorphism, of Bruhat intervals of length 7 in type A and of length 5 in types B and D, which are not lattices.     

Real quadrics in C n , complex manifolds and convex polytopes

In this paper, we investigate the topology of a class of non-Kähler compact complex manifolds generalizing that of Hopf and Calabi-Eckmann manifolds. These manifolds are diffeomorphic to special systems of real quadrics C ⁿ which are invariant with respect to the natural action of the real torus (S ¹) ⁿ onto C ⁿ . The quotient space is a simple convex polytope. The problem reduces thus to the study of the topology of certain real algebraic sets and can be handled using combinatorial results on convex polytopes. We prove that the homology groups of these compact complex manifolds can have arbitrary amount of torsion so that their topology is extremely rich. We also resolve an associated wall-crossing problem by introducing holomorphic equivariant elementary surgeries related to some transformations of the simple convex polytope. Finally, as a nice consequence, we obtain that affine non-Kähler compact complex manifolds can have arbitrary amount of torsion in their homology groups, contrasting with the Kähler situation.     

Level Eulerian Posets

The notion of level posets is introduced. This class of infinite posets has the property that between every two adjacent ranks the same bipartite graph occurs. When the adjacency matrix is indecomposable, we determine the length of the longest interval one needs to check to verify Eulerianness. Furthermore, we show that every level Eulerian poset associated to an indecomposable matrix has even order. A condition for verifying shellability is introduced and is automated using the algebra of walks. Applying the Skolem–Mahler–Lech theorem, the ab-series of a level poset is shown to be a rational generating function in the non-commutative variables a and b. In the case the poset is also Eulerian, the analogous result holds for the cd-series. Using coalgebraic techniques a method is developed to recognize the cd-series matrix of a level Eulerian poset.     

Two local operators and the BLUE

For a given matrix A, a matrix P such that PA = A is said to be a local identity, and such that P²A = PA is said to be a local idempotent. In the paper, some simple properties of such operators are presented. Their relation to the best linear unbiased estimation in the general Gauss-Markov model is also demonstrated.     

Laudal-type theorems in P

In this paper we classify all integral, non-degenerate, locally Cohen-Macaulay subvarieties in P^N, whose general complementary section is a complete intersection set of points: they are either complete intersections or curves on a quadric surface in P³ or degree 4 arithmetically Buchsbaum surfaces in P⁴ (i.e. the Veronese surface or a degeneration of it). As a consequence we show that every locally Cohen-Macaulay threefold in P^S of degree 4 is a complete intersection.Moreover, we obtain a generalization of Laudal's Lemma to threefolds in P⁵ and fourfolds in P⁶, which gives a bound on the degree of a codimension 2, integral subvariety X in P^N, depending both on N and a non-lifting level s of X.