Sergi Elizalde

	Phone:	(603) 646-8191
	Dept. Fax:	(603) 646-1312
	Office:	312 Bradley Hall
	Office Hours:	MW 9:50-10:50 M 2:00-3:00
	Email:
	US Mail:	Department of Mathematics 6188 Bradley Hall Dartmouth College Hanover, NH 03755-3551

Welcome to my homepage!

I am a John Wesley Young instructor in the Department of Mathematics at Dartmouth College.
This fall I am teaching Math 108. Topics in Combinatorics and Math 11. Multivariable Calculus.
Last summer I taught Math 20. Discrete Probability.
Last spring I taught Math 16. Linear Programming and Math 38. Graph Theory.
Last fall I taught Math 68. Algebraic Combinatorics and Math 3. Introduction to Calculus.

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

You can download my CV here, and also my list of publications, research statement, and teaching statement.

List of publications and preprints

• A bijection between 2-triangulations and pairs of non-crossing Dyck paths, preprint, 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), Proceedings of FPSAC 2006.
  
  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. [Download]
   
• The probability of choosing primitive sets (with K. Woods), Journal of Number Theory, to appear.
  
  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)). [Download]
   
• Restricted Dumont permutations, Dyck paths, and noncrossing partitions (with A. Burnstein and T. Mansour), Discrete Mathematics 306 (2006), 2851-2869.
  
  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. [Download]
   
• Combinatòria i biologia: funcions d'inferència i alineació de seqüències, Butlletí de la Societat Catalana de Matemàtiques, to appear.
   
• Asymptotic enumeration of permutations avoiding generalized patterns, Advances in Applied Mathematics 36 (2006), 138-155.
  
  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. [Download]
  
  
• 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.
  
  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. [Download]
  
  
• 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.

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. [Download]

• Restricted Motzkin permutations, Motzkin paths, continued fractions, and Chebyshev polynomials (with Toufik Mansour), Discrete Mathematics 305 (2005), 170-189.
  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. [Download]

• A simple and unusual bijection for Dyck paths and its consequences (with Emeric Deutsch), Annals of Combinatorics 7 (2003), 281-297.

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. [Download]
 
• Bijections for refined restricted permutations (with Igor Pak), Journal of Combinatorial Theory - Series A 105 (2004), 207-219.

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. [Download]
 
• Fixed points and excedances in restricted permutations, arxiv:math.CO/0212221, Proceedings of FPSAC 2003.

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

• 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 Boston, friends from back home, and my family
- 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 September 8, 2006 by Sergi Elizalde.