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
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.