Combinatorics on Words. New Aspects on Avoidability, Defect Effect, Equations and Palindromes

In this thesis we examine four well-known and traditional concepts of combinatorics on words. However the contexts in which these topics are treated are not the traditional ones. More precisely, the question of avoidability is asked, for example, in terms of k-abelian squares. Two words are said to be k-abelian equivalent if they have the same number of occurrences of each factor up to length k. Consequently, k-abelian equivalence can be seen as a sharpening of abelian equivalence. This fairly new concept is discussed broader than the other topics of this thesis. The second main subject concerns the defect property. The defect theorem is a well-known result for words. We will analyze the property, for example, among the sets of 2-dimensional words, i.e., polyominoes composed of labelled unit squares. From the defect effect we move to equations. We will use a special way to define a product operation for words and then solve a few basic equations over constructed partial semigroup. We will also consider the satisfiability question and the compactness property with respect to this kind of equations. The final topic of the thesis deals with palindromes. Some finite words, including all binary words, are uniquely determined up to word isomorphism by the position and length of some of its palindromic factors. The famous Thue-Morse word has the property that for each positive integer n, there exists a factor which cannot be generated by fewer than n palindromes. We prove that in general, every non ultimately periodic word contains a factor which cannot be generated by fewer than 3 palindromes, and we obtain a classification of those binary words each of whose factors are generated by at most 3 palindromes. Surprisingly these words are related to another much studied set of words, Sturmian words.

Density profiles in the raise and peel model with and without a wall; physics and combinatorics

We consider the raise and peel model of a one-dimensional fluctuating interface in the presence of an attractive wall. The model can also describe a pair annihilation process in disordered unquenched media with a source at one end of the system. For the stationary states, several density profiles are studied using Monte Carlo simulations. We point out a deep connection between some profiles seen in the presence of the wall and in its absence. Our results are discussed in the context of conformal invariance ( c = 0 theory). We discover some unexpected values for the critical exponents, which are obtained using combinatorial methods. We have solved known ( Pascal`s hexagon) and new (split-hexagon) bilinear recurrence relations. The solutions of these equations are interesting in their own right since they give information on certain classes of alternating sign matrices.

Henon-like maps with arbitrary stationary combinatorics

We extend the renormalization operator introduced in [A. de Carvalho, M. Martens and M. Lyubich. Renormalization in the Henon family, I: universality but non-rigidity. J. Stat. Phys. 121(5/6) (2005), 611-669] from period-doubling Henon-like maps to Henon-like maps with arbitrary stationary combinatorics. We show that the renonnalization picture also holds in this case if the maps are taken to be strongly dissipative. We study infinitely renormalizable maps F and show that they have an invariant Cantor set O on which F acts like a p-adic adding machine for some p > 1. We then show, as for the period-doubling case in the work of de Carvalho, Martens and Lyubich [Renormalization in the Henon family, I: universality but non-rigidity. J. Stat. Phys. 121(5/6) (2005), 611-669], that the sequence of renormalizations has a universal form, but that the invariant Cantor set O is non-rigid. We also show that O cannot possess a continuous invariant line field.

Eits: Combinatorics, Potential and Genre

Eits is a work of fiction, a non-traditional novel whose structure is largely determined by an Oulipian-style constraint. The constraint in Eits is culled from the album names and song titles of the band Explosions in the Sky. Each album corresponds to a chapter in the novel, and the language of each album title must be used in some way as an introduction to each chapter. Within each chapter (album), song titles correspond to numbered sections where each title must appear as is in the first sentence of that section. This not only dictates, to some degree, the direction of the text that will follow, but, looking ahead, the title of the next section will dictate where this section must arrive. From this, a narrative naturally takes shape. Albums/chapters appear chronologically, according to each album's release date, and within each album/chapter, songs/sections appear in the order they do on the album. This is, perhaps, the most straightforward way of ordering the received language of the constraint, the possibilities beyond this exponential. Eits is a novel that shifts in form, providing a texture to the space and reading experience of the novel, all in hopes of creating a space in which content and form inform and push each other to new limits. Eits is never satisfied to settle on one form for too long, and it is in the movement between forms that the narrative develops in interesting ways. Eits demonstrates the combinatoric possibilities inherent in language, and this exploration of potential highlights the reciprocal relationship between writing and reading. As Eits builds upon a limited language set, it explores and exploits the combinatory possibilities that language allows for both writer and reader. It demonstrates that all combinatoric potentialities, visible or not, always co-exist in the same time and space, and in this infinite space, individuals are invited to be writers and readers in simultaneity.

The combinatorics of Hilbert-Poincaré series of matroids

In this thesis we explore the combinatorial properties of several polynomials arising in matroid theory. Our main motivation comes from the problem of computing them in an efficient way and from a collection of conjectures, mainly the real-rootedness and the monotonicity of their coefficients with respect to weak maps. Most of these polynomials can be interpreted as Hilbert--Poincaré series of graded vector spaces associated to a matroid and thus some combinatorial properties can be inferred via combinatorial algebraic geometry (non-negativity, palindromicity, unimodality); one of our goals is also to provide purely combinatorial interpretations of these properties, for example by redefining these polynomials as poset invariants (via the incidence algebra of the lattice of flats); moreover, by exploiting the bases polytopes and the valuativity of these invariants with respect to matroid decompositions, we are able to produce efficient closed formulas for every paving matroid, a class that is conjectured to be predominant among all matroids. One last goal is to extend part of our results to a higher categorical level, by proving analogous results on the original graded vector spaces via abelian categorification or on equivariant versions of these polynomials.

An algorithmic Friedman-Pippenger theorem on tree embeddings and applications

An (n, d)-expander is a graph G = (V, E) such that for every X subset of V with vertical bar X vertical bar <= 2n - 2 we have vertical bar Gamma(G)(X) vertical bar >= (d + 1) vertical bar X vertical bar. A tree T is small if it has at most n vertices and has maximum degree at most d. Friedman and Pippenger (1987) proved that any ( n; d)- expander contains every small tree. However, their elegant proof does not seem to yield an efficient algorithm for obtaining the tree. In this paper, we give an alternative result that does admit a polynomial time algorithm for finding the immersion of any small tree in subgraphs G of (N, D, lambda)-graphs Lambda, as long as G contains a positive fraction of the edges of Lambda and lambda/D is small enough. In several applications of the Friedman-Pippenger theorem, including the ones in the original paper of those authors, the (n, d)-expander G is a subgraph of an (N, D, lambda)-graph as above. Therefore, our result suffices to provide efficient algorithms for such previously non-constructive applications. As an example, we discuss a recent result of Alon, Krivelevich, and Sudakov (2007) concerning embedding nearly spanning bounded degree trees, the proof of which makes use of the Friedman-Pippenger theorem. We shall also show a construction inspired on Wigderson-Zuckerman expander graphs for which any sufficiently dense subgraph contains all trees of sizes and maximum degrees achieving essentially optimal parameters. Our algorithmic approach is based on a reduction of the tree embedding problem to a certain on-line matching problem for bipartite graphs, solved by Aggarwal et al. (1996).