Growth of primary decompositions of Frobenius powers of ideals

It was previously known, by work of Smith–Swanson and of Sharp–Nossem, that the linear growth property of primary decompositions of Frobenius powers of ideals in rings of prime characteristic has strong connections to the localization problem in tight closure theory. The localization problem has recently been settled in negative by Brenner and Monsky, but the linear growth question is still open. We study growth of primary decompositions of Frobenius powers of dimension one homogeneous ideals in graded rings over fields. If the ring is positively graded we prove that the linear growth property holds. For non-negatively graded rings we are able to show that there is a “polynomial growth”. We present explicit primary decompositions of Frobenius powers of an ideal, which were known to have infinitely many associated primes, having this linear growth property. We also discuss some other interesting examples.     

Linear resolutions of quadratic monomial ideals

We study the minimal free resolution of a quadratic monomial ideal in the case where the resolution is linear. First, we focus on the squarefree case, namely that of an edge ideal. We provide an explicit minimal free resolution under the assumption that the graph associated with the edge ideal satisfies specific combinatorial conditions. In addition, we construct a regular cellular structure on the resolution. Finally, we extend our results to non-squarefree ideals by means of polarization.     

On the index of powers of edge ideals

The index of a graded ideal measures the number of linear steps in the graded minimal free resolution of the ideal. In this paper, we study the index of powers and squarefree powers of edge ideals. Our results indicate that the index as a function of the power of an edge ideal I is strictly increasing if I is linearly presented. Examples show that this needs not to be the case for monomial ideals generated in degree greater than two.     

Young-Fibonacci insertion, tableauhedron and Kostka numbers

This work is first concerned with some properties of the Young-Fibonacci insertion algorithm and its relation with Fomin's growth diagrams. It also investigates a relation between the combinatorics of Young-Fibonacci tableaux and the study of Okada's algebras associated to the Young-Fibonacci lattice. The original algorithm was introduced by Roby and we redefine it in such a way that both the insertion and recording tableaux of any permutation are conveniently interpreted as saturated chains in the Young-Fibonacci lattice. Using our conventions, we give a simpler proof of a property of Killpatrick's evacuation algorithm for Fibonacci tableaux. It also appears that this evacuation is no longer needed in making Roby's and Fomin's constructions coincide. We provide the set of Young-Fibonacci tableaux of size n with a structure of graded poset called tableauhedron, induced by the weak order of the symmetric group, and realized by transitive closure of elementary transformations on tableaux. We show that this poset gives a combinatorial interpretation of the coefficients of the transition matrix from the analogue of complete symmetric functions to analogue of the Schur functions in Okada's algebra associated to the Young-Fibonacci lattice. We prove a similar result relating usual Kostka numbers with four partial orders on Young tableaux, studied by Melnikov and Taskin.     

Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers

We use the correspondence between hypergraphs and their associated edge ideals to study the minimal graded free resolution of squarefree monomial ideals. The theme of this paper is to understand how the combinatorial structure of a hypergraph ℋ appears within the resolution of its edge ideal ℐ(ℋ). We discuss when recursive formulas to compute the graded Betti numbers of ℐ(ℋ) in terms of its sub-hypergraphs can be obtained; these results generalize our previous work (Hà, H.T., Van Tuyl, A. in J. Algebra 309:405–425, 2007) on the edge ideals of simple graphs. We introduce a class of hypergraphs, which we call properly-connected, that naturally generalizes simple graphs from the point of view that distances between intersecting edges are “well behaved.” For such a hypergraph ℋ (and thus, for any simple graph), we give a lower bound for the regularity of ℐ(ℋ) via combinatorial information describing ℋ and an upper bound for the regularity when ℋ=G is a simple graph. We also introduce triangulated hypergraphs that are properly-connected hypergraphs generalizing chordal graphs. When ℋ is a triangulated hypergraph, we explicitly compute the regularity of ℐ(ℋ) and show that the graded Betti numbers of ℐ(ℋ) are independent of the ground field. As a consequence, many known results about the graded Betti numbers of forests can now be extended to chordal graphs. Dedicated to Anthony V. Geramita on the occasion of his 65th birthday.     

Cohomology of Oriented Tree Diagram Lie Algebras

Xu introduced a family of root-tree-diagram nilpotent Lie algebras of differential operators, in connection with evolution partial differential equations. We generalized his notion to more general oriented tree diagrams. These algebras are natural analogues of the maximal nilpotent Lie subalgebras of finite-dimensional simple Lie algebras. In this article, we use Hodge Laplacian to study the cohomology of these Lie algebras. The “total rank conjecture” and “b ₂-conjecture” for the algebras are proved. Moreover, we find the generating functions of the Betti numbers by means of Young tableaux for the Lie algebras associated with certain tree diagrams of single branch point. By these functions and Euler–Poincaré principle, we obtain analogues of the denominator identity for finite-dimensional simple Lie algebras. The result is a natural generalization of the Bott's classical result in the case of special linear Lie algebras.     

Symmetry and Log-Concavity Results for Statistics on Fibonacci Tableaux

In this paper, we study the properties of the inversion statistic and the Fibonacci major index, Fibmaj, as defined on standard Fibonacci tableaux. We prove that these two statistics are symmetric and log-concave over all standard Fibonacci tableaux of a given shape μ and provide two combinatorial proofs of the symmetry result, one a direct bijection on the set of tableaux and the other utilizing 0, 1-fillings of a staircase shape. We conjecture that the inversion and Fibmaj statistics are log-concave over all standard Fibonacci tableaux of a given size n. In addition, we show a well-known bijection between standard Fibonacci tableaux of size n and involutions in S _n which takes the Fibmaj statistic to a new statistic called the submajor index on involutions.     

Primitive elements of the Hopf algebras of tableaux

The character theory of symmetric groups, and the theory of symmetric functions, both make use of the combinatorics of Young tableaux, such as the Robinson–Schensted algorithm, Schützenberger’s “jeu de taquin”, and evacuation. In 1995 Poirier and the second author introduced some algebraic structures, different from the plactic monoid, which induce some products and coproducts of tableaux, with homomorphisms. Their starting point are the two dual Hopf algebras of permutations, introduced by the authors in 1995. In 2006 Aguiar and Sottile studied in more detail the Hopf algebra of permutations: among other things, they introduce a new basis, by Möbius inversion in the poset of weak order, that allows them to describe the primitive elements of the Hopf algebra of permutations. In the present Note, by a similar method, we determine the primitive elements of the Poirier–Reutenauer algebra of tableaux, using a partial order on tableaux defined by Taskin.     

Greek letters in random staircase tableaux

In this paper we study a relatively new combinatorial object called staircase tableaux. Staircase tableaux were introduced by Corteel and Williams in the connection with Asymmetric Exclusion Process and has since found interesting connections with Askey–Wilson polynomials. We develop a probabilistic approach that allows us to analyze several parameters of a randomly chosen staircase tableau of a given size. In particular, we obtain limiting distributions for statistics associated with appearances of Greek letters in staircase tableaux. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Two criteria to check whether ideals are direct sums of cyclically presented modules

A famous theorem of commutative algebra due to I. M. Isaacs states that “if every prime ideal of R is principal, then every ideal of R is principal”. Therefore, a natural question of this sort is “whether the same is true if one weakens this condition and studies rings in which ideals are direct sums of cyclically presented modules?” The goal of this paper is to answer this question in the case R is a commutative local ring. We obtain an analogue of Isaacs's theorem. In fact, we give two criteria to check whether every ideal of a commutative local ring R is a direct sum of cyclically presented modules, it suffices to test only the prime ideals or structure of the maximal ideal of R. As a consequence, we obtain: if R is a commutative local ring such that every prime ideal of R is a direct sum of cyclically presented R-modules, then R is a Noetherian ring. Finally, we describe the ideal structure of commutative local rings in which every ideal of R is a direct sum of cyclically presented R-modules.     

Generic tropical initial ideals of Cohen-Macaulay algebras

We study the generic tropical initial ideals of a positively graded Cohen-Macaulay algebra R over an algebraically closed field k. Building on work of Römer and Schmitz, we give a formula for each initial ideal, and we express the associated quasivaluations in terms of certain I-adic filtrations. As a corollary, we show that in the case that R is a domain, every initial ideal coming from the codimension 1 skeleton of the tropical variety is prime, so “generic presentations of Cohen-Macaulay domains are well-poised in codimension 1.”     

Combinatorics of the K-theory of affine Grassmannians

We introduce a family of tableaux that simultaneously generalizes the tableaux used to characterize Grothendieck polynomials and k-Schur functions. We prove that the polynomials drawn from these tableaux are the affine Grothendieck polynomials and k-K-Schur functions – Schubert representatives for the K-theory of affine Grassmannians and their dual in the nil Hecke ring. We prove a number of combinatorial properties including Pieri rules.     

L1 cheapest paths in “Fjord Scenery”

We show a simple proof of the existence of a path on the “border of water and rocks” based on combinatorial induction procedure and we present an algorithm for computing L₁ shortest path in “Fjord Scenery”. The proposed algorithm is a version of the Dijkstra technique adapted to a rectangle map with a square network. A few pre-processing modifications of the algorithm following from the combinatorial procedure are included. The validity of this approach is shown by numerical calculations for an example.     

Filter-linkedness and its effect on preservation of cardinal characteristics

We introduce the property “F-linked” of subsets of posets for a given free filter F on the natural numbers, and define the properties “μ-F-linked” and “θ-F-Knaster” for posets in a natural way. We show that θ-F-Knaster posets preserve strong types of unbounded families and of maximal almost disjoint families.Concerning iterations of such posets, we develop a general technique to construct θ-Fr-Knaster posets (where Fr is the Frechet ideal) via matrix iterations of <θ-ultrafilter-linked posets (restricted to some level of the matrix). This is applied to prove consistency results about Cichoń's diagram (without using large cardinals) and to prove the consistency of the fact that, for each Yorioka ideal, the four cardinal invariants associated with it are pairwise different.At the end, we show that three strongly compact cardinals are enough to force that Cichoń's diagram can be separated into 10 different values.     

Slow convergence of sequences of linear operators II: Arbitrarily slow convergence

We study the rate of convergence of a sequence of linear operators that converges pointwise to a linear operator. Our main interest is in characterizing the slowest type of pointwise convergence possible. This is a continuation of the paper Deutsch and Hundal (2010) [14]. The main result is a “lethargy” theorem (Theorem 3.3) which gives useful conditions that guarantee arbitrarily slow convergence. In the particular case when the sequence of linear operators is generated by the powers of a single linear operator, we obtain a “dichotomy” theorem, which states the surprising result that either there is linear (fast) convergence or arbitrarily slow convergence; no other type of convergence is possible. The dichotomy theorem is applied to generalize and sharpen: (1) the von Neumann–Halperin cyclic projections theorem, (2) the rate of convergence for intermittently (i.e., “almost” randomly) ordered projections, and (3) a theorem of Xu and Zikatanov.     

Touchard–Riordan formulas, T-fractions, and Jacobi’s triple product identity

Touchard–Riordan-like formulas are certain expressions appearing in enumeration problems and as moments of orthogonal polynomials. We begin this article with a new combinatorial approach to prove such formulas, related to integer partitions. This gives a new perspective on the original result of Touchard and Riordan. But the main goal is to give a combinatorial proof of a Touchard–Riordan-like formula for q-secant numbers discovered by the first author. An interesting limit case of these objects can be directly interpreted in terms of partitions, so that we obtain a connection between the formula for q-secant numbers, and a particular case of Jacobi’s triple product identity. Building on this particular case, we obtain a “finite version” of the triple product identity. It is in the form of a finite sum which is given a combinatorial meaning, so that the triple product identity can be obtained by taking the limit. Here the proof is non-combinatorial and relies on a functional equation satisfied by a T-fraction. Then from this result on the triple product identity, we derive a whole new family of Touchard–Riordan-like formulas whose combinatorics is not yet understood. Eventually, we prove a Touchard–Riordan-like formula for a q-analog of Genocchi numbers, which is related with Jacobi’s identity for (q;q)³ rather than the triple product identity.     

Éclosions combinatoires appliquées à l'inversion multidimensionnelle des séries formelles

Using general methods from the theory of combinatorial species, in the sense of A. Joyal (Adv. in Math.42 (1981), 1–82), symmetric powers of suitably chosen differential operators are interpreted combinatorially in terms of “éclosions” (bloomings) of certain kinds of points, called “bourgeons” (buds), into certain kinds of structures, called “gerbes” (bundles). This gives rise to a combinatorial setting and simple proof of a general multidimensional power series reversion formula of the Lie-Gröbner type (14., 15.). Some related functional equations are also treated and an adaptation of the results to the reversion of cycle index (indicatrix) series, in the sense of Pólya-Joyal (Joyal, loc. cit.), is given.     

Effective scalar products of D-finite symmetric functions

Many combinatorial generating functions can be expressed as combinations of symmetric functions, or extracted as sub-series and specializations from such combinations. Gessel has outlined a large class of symmetric functions for which the resulting generating functions are D-finite. We extend Gessel's work by providing algorithms that compute differential equations, these generating functions satisfy in the case they are given as a scalar product of symmetric functions in Gessel's class. Examples of applications to k-regular graphs and Young tableaux with repeated entries are given. Asymptotic estimates are a natural application of our method, which we illustrate on the same model of Young tableaux. We also derive a seemingly new formula for the Kronecker product of the sum of Schur functions with itself.