In a recent paper with Mark Dukes, we give a bijection between ascent sequences and a nice class of integer matrices. It was shown in another recent paper, of Bousquet-Mélou, Claesson, Dukes and Kitaev, that ascent sequences are in bijection with permutations avoiding a particular pattern of a new type. This new type of pattern have the extra restrictions of Babson and Steingrímsson's generalized patterns, but in "two dimensions" (both for indices and values).
I have completed the Wilf classification of all such patterns of lengths two and three, and will discuss the results and some interesting cases, in particular some that relate to ascent sequences and integer matrices.
We say that two finite words u and v are abelian equivalent if and only if they have the same number of occurrences of each letter, or equivalently if they define the same Parikh vector. I will discuss various abelian properties of words including abelian complexity, and abelian powers. As a consequence of van der Waarden's Theorem, we prove that any infinite word with bounded abelian complexity contains abelian k-powers for every positive integer k.
This is joint work with Gwénaël Richomme (Université de Montpellier) and Kalle Saari (University of Turku).
One way to measure the complexity of a partial ordering of a set X is to determine the number of total orderings of X that are compatible with that partial ordering. These total orderings are called linear extensions. In this talk we determine the minimum number of elements needed to create a poset having exactly n linear extensions. This number is always less than or equal to 2\sqrt{n}. Moreover, in some cases this number can actually be bounded by \sqrt{n}.
A classical problem in the field of face enumeration of simplicial complexes is the classification of special classes of simplicial complexes in terms of their h- and f-vectors, respectively. McMullen conjectured that the g-vector of the boundary complex of a simplicial polytope is an M-sequence and that, in particular, it is unimodal.
In 1971 this was shown to be true by Stanley. In his proof he used the Hard Lefschetz theorem for toric varieties. In the same year Billera and Lee succeeded in constructing a simplicial polytope whose boundary has as g-vector a given M-sequence. The result of Stanley and Billera/Lee is known as the g-theorem. McMullen's original conjecture was later generalized by himself and Björner/Swartz to simplicial spheres and homology spheres, respectively. This conjecture is known as the g-conjecture.
Brenti and Welker showed that the h-vector of the barycentric subdivision of a Cohen-Macaulay complex is unimodal which led to the conjecture that the g-vector of such a complex is an M-sequence. We verify this conjecture in the affirmative by showing that an 'almost strong Lefschetz' property holds for the barycentric subdivision of a shellable simplicial complex. From this we conclude that for the barycentric subdivision of a Cohen-Macaulay complex, the h-vector is unimodal, attains in maximum value in its middle degree (one of them if the dimension of the complex is even), and that its g-vector is an M-sequence. It is remarkable that those numerical results hold in the greater generality of Cohen-Macaulay complexes even though the algebraic result does only hold for the smaller class of shellable simplicial complexes.
Our result in particular shows the g-conjecture for barycentric subdivisions of homology spheres. Brenti and Welker further showed that the h-vector of the barycentric subdivision of a simplicial complex can be expressed as a positive linear combination of the h-vector of the original simplicial complex. The coefficients occurring in this representation are a refinement of the Eulerian statistics on permutations, where permutations are grouped by the number of descents and the image of 1.
Using the algebraic result, i.e., the almost strong Lefschetz property of the barycentric subdivision of a shellable simplicial complex, we derive new inequalities for those statistics on permutations. Algebraic and combinatorial notion and background, such as the notion of Lefschetz elements and M-sequences will be provided during the talk.
This is joint work with Eran Nevo, Cornell University.
Work in progress: A version of the Asymmetric Simple Exclusion Process, that can simply be described as a random stack model, turns out to have a simple solution. The stationary probabilities can be expressed using weighted binomial paths, or equivalently, by so called cap and cup permutations(*). (These permutations have one maximum or minimum, respectively.)
The important partition functions turns out to be just a q-series, the asymptotics of which I am interested in.
I will describe these results, open problems, and ideas for extensions of the results.
(*) In Goulden & Jackson's book - I'm sure there are other names as well.
It is well known that Hyperbolic automorphisms of the 2-torus admit a markov partition. This markov partition is closely related to 1 dimensional tilings of the line called Sturmian tilings. In the general case any hyperbolic toral automorphism of the d-torus admits a Markov partition, however a result of Bowen shows that, if d > 2 and the automorphism is algebraically irreducible, the elements of the Markov partition can never have a smooth boundary: this boundary is a non-trivial fractal set, and is difficult to construct in the general case.
In 1982 Gerard Rauzy found a method of constructing the markov partition of an irreducible Hyperbolic automorphisms of the 3-torus using a substitution rule on three letters. This work has been generalised to construct the Markov partition for many (conjectorally all) irreducible PV toral automorphisms.
Recent work of Arnoux, Furukado, Ito and H has opened up this geometric construction in the more complicated non-PV case, where there is more than 1 eigenvalue of absolute value greater than 1.
This talk will focus on the geometric construction of Rauzy fractals that give the Markov partitions and the related substitution tilings. Starting with the original example of Rauzy, and the general PV-case before showing how this construction can be generalised to the non-PV case.
Let G be a simple graph on d vertices. We define a monomial ideal K in the Stanley-Reisner ring A of the order complex of the Boolean algebra on d atoms. The monomials in K are in one-to-one correspondence with the proper colorings of G. In particular, the Hilbert polynomial of K equals the chromatic polynomial of G. The ideal K is generated by square-free monomials, so A/K is the Stanley-Reisner ring of a simplicial complex C. The h-vector of C is a certain transformation of the tail T(n) = n^d - X(n) of the chromatic polynomial X of G. The combinatorial structure of the complex C is described explicitly and it is shown that the Euler characteristic of C equals the number of acyclic orientations of G.
This time I will not present my own research, instead I will present a classic result of Guibas and Odlyzko. Here is one question you will be able to answer after attending my talk:
Given a binary string p, what is the expected position of the end of the first occurrence of p in a random binary string?
For a given graph we define a coloring ideal, which is a monomial ideal where each monomial corresponds to some coloring of the graph. We study the Groebner-basis of this ideal. Then we construct a so-called coloring complex of a graph. Finally we almost prove, using computer algebra, that distinct graphs with at least three edges produce distinct coloring complexes.
In this talk a new model of growing planar tree graphs will be presented. At each time step the tree separates into two components by splitting a vertex, and then connect the two pieces by inserting a new link between the daughter vertices. The selection process and splitting behaviour is governed by a matrix. I will present (and explain!) results such as a mean field theory for the vertex degree distribution and the behaviour of the Hausdorff dimension.
Amy will speak on Rich words, following on from her ICE-TCS talk in late September:
In 2001, Droubay, Justin, and Pirillo showed that any finite word w of length |w| contains at most |w| + 1 distinct palindromes (including the empty word). Inspired by this result, Jacques Justin and I recently initiated a unified study of finite and infinite words that are characterized by containing the maximal number of distinct palindromes, which we call "rich words" (in view of their palindromic richness). In this talk I will explore various properties of this intriguing class of words. In particular, I will show that a nice characteristic property of rich words is that all "complete returns" to any palindromic factor are palindromes. These words encompass the well-known family of episturmian words, originally introduced by Droubay et al. in 2001. Another special class of rich words consists of sequences with "abundant palindromic prefixes", which were introduced and studied by Fischler in 2006 in relation to Diophantine approximation. Other examples of rich words have appeared in many different contexts; they include complementation-symmetric Rote sequences, symbolic codings of trajectories of symmetric interval exchange transformations, trapezoidal words, and a certain class of words associated with $\beta$-expansions where $\beta$ is a simple Parry number. I will finish by presenting more recent results on rich words (particularly characterizations) obtained in collaboration with Michelangelo Bucci, Alessandro De Luca, Aldo de Luca, Steve Widmer, and Luca Q. Zamboni.
In a recent preprint (arXiv:0810.2916) Corteel and Williams show a connection between a special case of the Asymmetric Simple Exclusion Process and permutation tableaux.
Combining this with earlier results, which give a Motzkin path solution to the ASEP in the same case, I have found some interesting consequences. After giving the necessary background, I will discuss these new results. They include:
A Motzkin path representation of permutation tableaux, which encodes
a) the distribution of distinguished ones, or, number of ones in the first row
b) the distribution of distinguished zeros, or, number of unrestricted rows
c) the shape of the tableaux
In connection with c), a sequence of polynomials in two non-commutative variables, which when the variables are allowed to commute give the Eulerian polynomials. For example, for n=3, f(s,w)=sss + 3ss*w + sws+sww. A simple description using excedances can be given in the non-commutative case. Furthermore, the polynomial lists tableaux according to shape: Let the path from the north-east corner to the south-west corner be encoded by a word in s and w, with s at position i iff the path takes a south step, and w if it takes a west step. The 'sum' of the words gives the polynomial, e.g. there are three permutation tableaux whose path is ssw. This induces a bijection between permutation and permutation tableaux that appears to be new.
The number of permutation tableaux of size n with k distinguished entries (zeros or ones) are 2^{k+1} s(n-1,k), where s(n,k) are the unsigned Stirling cycle numbers
This is very much work in progress, and the results unpolished and proofs are either missing or sketchy.
I will define the concept of a "uniquely k-determined permutation" and will give two criteria for a permutation to be uniquely k-determined: one in terms of the distance between two consecutive elements in a permutation, and the other one in terms of directed hamiltonian paths in the certain graphs called path-schemes. Moreover, I will provide a finite set of prohibitions that gives the set of uniquely k-determined permutations. Those prohibitions make applying the transfer matrix method possible for determining the number of uniquely k-determined permutations.