Sergi Elizalde

	Phone:	(603) 646-8191
	Dept. Fax:	(603) 646-1312
	Office:	332 Kemeny Hall
	Office Hours:	By appointment
	Email:
	US Mail:	Department of Mathematics 6188 Kemeny Hall Dartmouth College Hanover, NH 03755-3551

Welcome to my homepage!

I am an Assistant Professor in the Department of Mathematics at Dartmouth College.

I completed my Ph.D. at MIT in 2004 under the supervision of Richard Stanley. Afterwards I was a Postdoctoral Fellow at MSRI, and later a John Wesley Young instructor at Dartmouth.
My research interests are in enumerative and algebraic combinatorics, and applications to computational biology and other fields. I have worked on pattern-avoiding permutations, bijective proofs, lattice paths, algebraic statistics in computational biology, combinatorial commutative algebra, and number theory.

Here you can download my
    - CV
    - research statement (not up to date)

Last October we organized the Discrete Mathematics Day conference at Dartmouth.

---

Past teaching

• Winter 2008: Math 108. Topics in Combinatorics: The probabilistic method.
• Fall 2007: Math 68. Algebraic Combinatorics.
• Spring 2006: Math 38. Graph Theory.
• Fall 2006: Math 108. Topics in Combinatorics; Math 11. Multivariable Calculus.
• Summer 2006: Math 20. Discrete Probability.
• Spring 2006: Math 16. Linear Programming; Math 38. Graph Theory.
• Fall 2005: Math 68. Algebraic Combinatorics; Math 3. Introduction to Calculus.

---

List of publications and preprints

• Forbidden patterns and shift systems (with J.M. Amigó and M.B. Kennel), Journal of Combinatorial Theory - Series A 115 (2008), 485-504, arXiv:0707.4628.
  Abstract: The scope of this paper is two-fold. First, to present an interesting implementation of permutations avoiding generalized patterns in the framework of discrete-time dynamical systems. Indeed, the orbits generated by piecewise monotone maps on one-dimensional intervals have forbidden order patterns, which do not occur in any orbit. The allowed patterns are then those patterns avoiding the so-called forbidden root patterns and their translates. The second scope is to study forbidden patterns in shift systems, which are universal models in information theory, dynamical systems and stochastic processes. Due to its simple structure, shift systems are accessible to a more detailed analysis and, at the same time, exhibit all important properties of complex dynamical systems, allowing to export the results to other dynamical systems via order-isomorphisms.
  
  
• Generating trees for permutations avoiding generalized patterns, Annals of Combinatorics 11 (2007), 435—458, arXiv:0707.4633.
  Abstract: We construct generating trees with one and two labels for some classes of permutations avoiding generalized patterns of length 3 and 4. These trees are built by adding at each level an entry to the right end of the permutation, instead of inserting always the largest entry. This allows us to incorporate the adjacency condition about some entries in an occurrence of a generalized pattern. We find functional equations for the generating functions enumerating these classes of permutations with respect to different parameters, and in a few cases we solve them using some techniques of Bousquet-Mélou, recovering known enumerative results and finding new ones.
  
  
• A bijection between 2-triangulations and pairs of non-crossing Dyck paths, Journal of Combinatorial Theory - Series A 114/8 (2007), 1481-1503, arxiv:math.CO/0610235.
  Abstract: A k-triangulation of a convex polygon is a maximal set of diagonals so that no k+1 of them mutually cross in their interiors. We present a bijection between 2-triangulations of a convex n-gon and pairs of non-crossing Dyck paths of length 2(n-4). This solves the problem of finding a bijective proof of a result of Jonsson for the case k=2. We obtain the bijection by constructing isomorphic generating trees for the sets of 2-triangulations and pairs of non-crossing Dyck paths.
  
• Bounds on the number of inference functions of a graphical model (with K. Woods), Statistica Sinica 17 (2007), 1395--1415, arxiv:math.CO/0610233.
  Abstract: We give an upper bound on the number of inference functions of any directed graphical model. This bound is polynomial on the size of the model, for a fixed number of parameters, thus improving an exponential upper bound of Pachter and Sturmfels. We also show that our bound is tight up to a constant factor, by constructing a family of hidden Markov models whose number of inference functions agrees asymptotically with the upper bound. Finally, we apply this bound to a model for sequence alignment that is used in computational biology.
  
• The probability of choosing primitive sets (with K. Woods), Journal of Number Theory 125 (2007), 39--49, arxiv:math.NT/0607390.
  Abstract: We generalize a theorem of Nymann that the density of points in Z^d that are visible from the origin is 1/zeta(d), where zeta is the Riemann zeta function. A subset S of Z^d is called primitive if it can be completed to a Z-basis of Z^d. We prove that if m points in Z^d are chosen uniformly and independently at random from a large box, then as the size of the box goes to infinity, the probability that the points form a primitive set approaches
  1/(zeta(d) zeta(d-1) ... zeta(d-m+1)).
  
• Restricted Dumont permutations, Dyck paths, and noncrossing partitions (with A. Burnstein and T. Mansour), Discrete Mathematics 306 (2006), 2851-2869, arXiv:math/0610234.
  Abstract: We complete the enumeration of Dumont permutations of the second kind avoiding a pattern of length 4 which is itself a Dumont permutation of the second kind. We also consider some combinatorial statistics on Dumont permutations avoiding certain patterns of length 3 and 4 and give a natural bijection between 3142-avoiding Dumont permutations of the second kind and noncrossing partitions that uses cycle decomposition, as well as bijections between 132-, 231- and 321-avoiding Dumont permutations and Dyck paths. Finally, we enumerate Dumont permutations of the first kind simultaneously avoiding certain pairs of 4-letter patterns and another pattern of arbitrary length.
  
• Combinatòria i biologia: funcions d'inferència i alineació de seqüències, Butlletí de la Societat Catalana de Matemàtiques, vol. 21, núm. 1 (2006), 39–52. [Download]
  
• Asymptotic enumeration of permutations avoiding generalized patterns, Advances in Applied Mathematics 36 (2006), 138-155, arXiv:math/0505254.
  Abstract: Motivated by the recent proof of the Stanley-Wilf conjecture, we study the asymptotic behavior of the number of permutations avoiding a generalized pattern. Generalized patterns allow the requirement that some pairs of letters must be adjacent in an occurrence of the pattern in the permutation, and consecutive patterns are a particular case of them. We determine the asymptotic behavior of the number of permutations avoiding a consecutive pattern, showing that they are an exponentially small proportion of the total number of permutations. For some other generalized patterns we give partial results, showing that the number of permutations avoiding them grows faster than for classical patterns but more slowly than for consecutive patterns.
• Inference functions, chapter of the book Algebraic Statistics for Computational Biology, edited by Lior Pachter and Bernd Sturmfels, Cambridge University Press, 2005.
• Bounds for optimal sequence alignment (with Fumei Lam), chapter of the book Algebraic Statistics for Computational Biology, edited by Lior Pachter and Bernd Sturmfels, Cambridge University Press, 2005.
• Old and young leaves on plane trees (with Bill Chen and Emeric Deutsch),  European Journal of Combinatorics 27 (2006), Issue 3, 414-427, arXiv:math/0410127.
  Abstract: We introduce the notion of old and young leaves of a plane tree. We find the multivariate generating function for plane trees with respect to the number of old leaves and the number of young leaves, and give other enumerative formulas. Then we present two bijections between plane trees and 2-Motzkin paths mapping young leaves to red horizontal steps, and old leaves to up steps plus one. We conclude with some implications to the enumeration of restricted permutations with respect to certain statistics such as pairs of consecutive deficiencies, double descents, and ascending runs.
• Statistics on Pattern-avoiding Permutations, Ph.D. thesis, MIT, 2004. [Download pdf, ps]

• Multiple pattern-avoidance with respect to fixed points and excedances, Electronic Journal of Combinatorics 11 (2004), #R51, arXiv:math/0311211.
  Abstract: We study the distribution of the statistics `number of fixed points' and `number of excedances' in permutations avoiding subsets of patterns of length 3. We solve all the cases of simultaneous avoidance of more than one pattern, giving generating functions enumerating these two statistics. Some cases are generalized to patterns of arbitrary length. For avoidance of one single pattern we give partial results. We also describe the distribution of these statistics in involutions avoiding any subset of patterns of length 3.  The main technique is to use bijections between pattern-avoiding permutations and certain kinds of Dyck paths, in such a way that the statistics in permutations that we study correspond to statistics on Dyck paths that are easy to enumerate.

• Restricted Motzkin permutations, Motzkin paths, continued fractions, and Chebyshev polynomials (with Toufik Mansour), Discrete Mathematics 305 (2005), 170-18, arXiv:math/0610237.
  Abstract: We say that a permutation p is a Motzkin permutation if it avoids 132 and there do not exist a<b such that p_a<p_b<p_{b+1}. We study the distribution of several statistics in Motzkin permutations, including the length of the longest increasing and decreasing subsequences and the number of rises and descents. We also enumerate Motzkin permutations with additional restrictions, and study the distribution of occurrences of fairly general patterns in this class of permutations.

• A simple and unusual bijection for Dyck paths and its consequences (with Emeric Deutsch), Annals of Combinatorics 7 (2003), 281-297, arXiv:math/0306125.
  Abstract: In this paper we introduce a new bijection from the set of Dyck paths to itself. This bijection has the property that it maps statistics that appeared recently in the study of pattern-avoiding permutations into classical statistics on Dyck paths, whose distribution is easy to obtain. We also present a generalization of the bijection, as well as several applications of it to enumeration problems of statistics in restricted permutations.
  
• Bijections for refined restricted permutations (with Igor Pak), Journal of Combinatorial Theory - Series A 105 (2004), 207-219, arXiv:math/0212328.
  Abstract: We present a bijection between 321- and 132-avoiding permutations that preserves the number of fixed points and the number of excedances. This gives a simple combinatorial proof of recent results of Robertson, Saracino and Zeilberger, and the first author. We also show that our bijection preserves additional statistics, which extends the previous results.
  
• Fixed points and excedances in restricted permutations, Proceedings of FPSAC 2003, arxiv:math.CO/0212221.
  Abstract: In this paper we prove that among the permutations of length n with i fixed points and j excedances, the number of 321-avoiding ones equals the number of 132-avoiding ones, for all given i,j <= n. We use a new technique involving diagonals of non-rational generating functions. [Download]
• Consecutive patterns in permutations (with Marc Noy), proceedings of FPSAC 2001, Advances in Applied Mathematics 30 (2003), 110-125.
  Abstract: In this paper we study the distribution of the number of occurrences of a permutation s as a subword among all permutations in S_n. We solve the problem in several cases depending on the shape of s by obtaining the corresponding bivariate exponential generating functions as solutions of certain linear differential equations with polynomial coefficients. Our method is based on the representation of permutations as increasing binary trees and on symbolic methods. [Download]

Some slides of talks I have given

• Discrete Mathematics Day, Middlebury College, September 2007, Forbidden patterns in telling random from deterministic time series. [Slides]
• MIT Combinatorics Seminar, September 2006, A bijection between 2-triangulations and pairs of non-crossing Dyck paths. [Slides]
• International Conference on Permutation Patterns, PP'06, Reykjavik, Iceland, June 2006, Generating trees for permutations avoiding generalized patterns. [Slides]
• Institut Mittag-Leffler Seminar, Djursholm, Sweden, May 2005, Combinatorics from biology: inference functions and sequence alignment. [Slides]
• International Conference on Permutation Patterns, PP'05, Gainesville, Florida, March 2005, Asymptotic enumeration of permutations avoiding generalized patterns. [Slides]
• MIT Combinatorics Seminar, February 2005. Inference functions and sequence alignment. [Slides]
• Stanford University Representation Theory Seminar, December 2004, Refined enumeration of pattern-avoiding permutations. [Slides]
• International Conference on Permutation Patterns, PP'04, Nanaimo, Canada, July 2004, Simultaneous pattern-avoidance with respect to fixed points and excedances. [Slides]
• Thesis defense, MIT, April 2004, Statistics on Pattern-avoiding Permutations. [Slides]
• UC Berkeley Combinatorics Seminar, February 2004, Refined enumeration of pattern-avoiding permutations. [Slides]
• MIT Combinatorics Seminar, November 2003. Pattern-avoiding permutations: old results and new developments. [Slides]
• FPSAC 2003, Vadstena, Sweden, June 2003. Fixed points and excedances in restricted permutations. [Slides]
• MIT Simple Person's Applied Math Seminar, November 2002. What pattern avoidance shouldn't have avoided. [Slides]

---

Some links

- Pictures of my friends in Dartmouth, friends in Berkeley, friends in Boston, friends from back home.
- Pictures of my family (older, more recent).
- Pictures from the FPSAC'03 conference in Vadstena, Sweden.
- My dad's Homepage.
- Iberia: asociación de españoles en Boston.
- Iberia: asociación de españoles en Berkeley.

Last modified on March 30, 2008 by Sergi Elizalde.