Research
My research centres on algebraic and enumerative combinatorics. I have
worked on topics such as combinatorial representation theory, factorizations
problems in the symmetric group, lattice paths and integer partitions.
Publications
- Combinatorial enumeration of lattice paths by flaws with respect to a linear boundary of rational slope (with F. Firoozi and J. Jedwab)
- Abstract:
Let a,b be fixed positive coprime integers. For a positive integer g, write Nk(g) for the set of lattice paths from the startpoint (0,0) to the endpoint (ga,gb) with steps restricted to {(1,0),(0,1)}, having exactly k flaws (lattice points lying above the linear boundary). We wish to determine |Nk(g)|. The enumeration of lattice paths with respect to a linear boundary while accounting for flaws has a long and rich history, dating back to the 1949 results of Chung and Feller. The only previously known values of |Nk(g)| are the extremal cases k=0 and k=g(a+b)−1, determined by Bizley in 1954. Our main result is that a certain subset of Nk(g) is in bijection with Nk+1(g). One consequence is that the value |Nk(g)| is constant over each successive set of a+b values of k. This in turn allows us to derive a recursion for |Nk(g)| whose base case is given by Bizley's result for k=0. We solve this recursion to obtain a closed form expression for |Nk(g)| for all k and g. Our methods are purely combinatorial.
- Centrality of star and monotone factorisations (with J. Campion Loth)
- Abstract:
A factorisation problem in the symmetric group is central if any two permutations in the same conjugacy class have the same number of factorisations. We give the first fully combinatorial proof of the centrality of transitive star factorisations that is valid in all genera, which answers a natural question of Goulden and Jackson from 2009. Our proof is through a bijection to a class of monotone double Hurwitz factorisations. These latter factorisations are also not obviously central, so we also give a combinatorial proof of their centrality. As a corollary we obtain new formulae for some monotone double Hurwitz numbers, and a new relation between Hurwitz and monotone Hurwitz numbers. We also generalise a theorem of Goulden and Jackson from 2009 that states that the transitive power of Jucys-Murphy elements are central. Our theorem states that the transitive image of any symmetric function evaluated at Jucys-Murphy elements is central, which gives a transitive version of Jucys' original result from 1974.
- On the average number of
cycles in conjugacy class products (with J. Campion Loth)
- Abstract:
We show that for the product of two fixed point free conjugacy classes,
the average number of cycles is always very similar. Specifically, our
main result is that for a randomly chosen pair of fixed point free
permutations of cycle types α and β, the average number of cycles in
their product is between Hn−3 and Hn+1, where
Hn is the harmonic number.
- A comparison of integer
partitions based on smallest part (with D. Binner)
- Electon. J. Combin. Vol. 31(1), 2024.
- Abstract:
For positive integers n,L and s, consider the following two sets that both
contain partitions of n with the difference between the largest and smallest
parts bounded by L: the first set contains partitions with smallest part s,
while the second set contains partitions with smallest part at least s+1. Let
GL,s(q) be the generating series whose coefficient of qn is
difference between the sizes of the above two sets of partitions. This
generating series was introduced by Berkovich and Uncu (2019). Previous results
concentrated on the nonnegativity of GL,s(q) in the cases s=1 and
s=2. In the present paper, we show the eventual positivity of GL,s(q) for general s and also find a precise nonnegativity result for the case s=3.
- k-Factorizations of
the full cycle and generalized Mahonian statistics on k-forests (arxiv version) (with J. Irving)
-
Adv. Appl. Math. 151, 2023 (journal version).
- Abstract:
We develop direct bijections between the set Fnk
of minimal factorizations of the long cycle (0,1,...,kn)
into (k+1)-cycle factors and the set
of rooted labelled forests on vertices
with edges coloured with {0,1,...,k-1}
that map natural statistics on the former to generalized Mahonian statistics on the latter. In particular, we examine the generalized major index on forests
and show that it has a simple and natural interpretation in the context of
factorizations. Our results extend our own results (2021), which treated the
case k=1
through a different approach, and provide a bijective proof of the
equidistribution observed by Yan (1997) between displacement of k-parking functions and generalized inversions of k-forests.
- Combinatorial and
Algebraic Enumeration: a survey of the work of Ian P. Goulden
and David M. Jackson (with A.
Foley, A.
Morales and K. Yeats)
-
Algebr. Comb. 5(6):1205-1226, 2022.
- Abstract:
In this survey we discuss some of the significant contributions of Ian Goulden and David Jackson in the areas of classical enumeration, symmetric functions, factorizations of permutations, and algebraic foundations of quantum field theory. Through their groundbreaking textbook, {\em Combinatorial Enumeration}, and their numerous research papers, both together and with their many students, they have had an influence in areas of bioinformatics, mathematical chemistry, algorithmic computer science, and theoretical physics. Here we review and set in context highlights of their 40 years of collaborative work.
- Trees, parking
functions and factorizations of full cycles (arxiv version) (with J. Irving)
- European
J. Combin. 93, 2021 (journal version).
- Abstract: Parking functions of length n
are well known to be in correspondence with both labelled trees on n+1
vertices and factorizations of the full cycle (0, 1, ... n)
into
transpositions. In fact, these correspondences can be refined: Kreweras equated the area enumerator of parking functions with the inversion enumerator of labelled trees, while an elegant bijection of Stanley maps the area of parking functions to a natural statistic on factorizations of
. We extend these relationships in two principal ways. First, we introduce a bivariate refinement of the inversion enumerator of trees and show that it matches a similarly refined enumerator for factorizations. Secondly, we characterize all full cycles
such that Stanley’s function remains a bijection when the canonical cycle
is replaced by
. We also exhibit a connection between our refined inversion enumerator and Haglund’s bounce statistic on parking functions.
- On
products of long cycles: short cycle dependence and separation
probabilities (with V.
Féray)
- J. Algebraic. Combin. 42(1):183-224, 2015.
- Abstract: We present various results on multiplying cycles in the symmetric group. One result is a generalisation of the following theorem of Boccara (Discret Math 29:105–134, 1980): the number of ways of writing an odd permutation in the symmetric group on
symbols as a product of an (n)-cycle and an (n-1)-cycle is independent of the permutation chosen. We give a number of different approaches of our generalisation. One partial proof uses an inductive method which we also apply to other problems. In particular, we give a formula for the distribution of the number of cycles over all products of cycles of fixed lengths. Another application is related to the recent notion of separation probabilities for permutations introduced by Bernardi et al. (Comb Probab Comput 23:201–222, 2014).
- Enumeration of
noncrossing pairings on bit strings (with T. Kemp, K. Mahlburg and C.
Smyth)
-
J. Combin. Theory Ser. A 118(1):129-151, 2011.
- Abstract: A non-crossing pairing on a bitstring
matches 1s and 0s in a manner such that the pairing diagram is
nonintersecting. By considering such pairings on arbitrary bitstrings we
generalize classical problems from the theory of Catalan structures. In
particular, it is very difficult to find useful explicit formulas for the
enumeration function which counts the number of pairings as a function of
the underlying bitstring. We determine explicit formulas for enumeration
function for bit strings, and also prove general upper bounds in terms of
Fuss-Catalan numbers by relating non-crossing pairings to other
generalized Catalan structures (that are in some sense more natural).
This enumeration problem arises in the theory of random matrices and free
probability.
- The number of lattice paths below
a cyclically shifting boundary (with J. Irving)
- J. Combin. Theory Ser. A, 116(3):499--514, April 2009
- Abstract: We count the number of lattice paths lying under a cyclically shifting piecewise linear boundary of varying slope. Our main result extends well known enumerative
formulae concerning lattice paths, and its derivation involves a classical reflection argument. A refinement allows for the counting of paths with a specified number of corners.
We also apply the result to examine paths dominated by periodic boundaries.
- Minimal factorizations of permutations into
star transpositions (with J.
Irving)
- Discrete Math, 309(6):1435--1442, April 2009.
- Abstract: We give a compact expression for the number of factorizations of any
permutation into a minimal number of transpositions of the form (1 i). Our result
generalizes earlier work of Pak in which substantial restrictions were placed on the
permutation being factored.
- Upper bound on the characters of the
symmetric groups for balanced Young diagrams and a generalized Frobenius
formula (with P.
Śniady)
- Adv. Math, 218(3):673--695, 2008
- Abstract: We study asymptotics of an irreducible representation of the
symmetric group Sn corresponding to a balanced Young
diagram λ (a Young diagram with at most C√n rows and
columns, for some constant C) in the
limit as n tends to infinity. We find an asymptotic bound for characters in
terms of a parameter D, whicn only depends on C. The main tool we introduce is a generalization of the Frobenius character
formula, which holds true not only for cycles but for arbitrary
permutations.
- Stanley's character polynomials
and coloured factorizations in the symmetric group
- J. Combin. Theory Ser. A, 115(4):535--546, May 2008.
- Abstract: Stanley introduces polynomials which help evaluate symmetric group
characters and conjectures that the coefficients of the polynomials are positive. He
later gives a conjectured combinatorial interpretation for the coefficients of the
polynomials. Here, we prove the conjecture for the terms of highest degree.
- Positivity
results for Stanley's character polynomials
- J. Algebra, 308(1):26-47, Feb. 2007.
- Abstract: Stanley introduced expressions for the normalized characters of the
symmetric group and stated some positivity conjectures for these expressions. Here,
we give an affirmative partial answer to Stanley’s positivity
conjectures about the expressions using results on Kerov polynomials. In
particular, we use new positivity results by Goulden and Rattan. We shall see
that the generating series C(t) introduced by Goulden and Rattan is critical to
our discussion.
- An explicit form for Kerov's character polynomials (with I.P.
Goulden)
- Trans. Amer. Math. Soc., 359:3669-3685, 2007.
- Abstract: Kerov considered the normalized
characters of irreducible representations of the symmetric group,
evaluated on a cycle, as a polynomial in free cumulants. Biane has
proved that this polynomial has integer coefficients, and made various
conjectures. Recently, Śniady has proved Biane's conjectured
explicit form for the first family of nontrivial terms in this polynomial.
In this paper, we give an explicit expression for all terms in Kerov's
character polynomials. Our method is through Lagrange inversion.
- Permutation
factorizations and prime parking functions
- Ann. Comb., 10(2):237-254, Sept. 2006.
- Abstract: Permutation factorizations and parking
functions have some parallel properties. Kim and Seo exploited these parallel
properties to count the number of ordered, minimal factorizations of permutations of
cycle type (n) and (1, n-1). In this paper, we use parking functions, new tree
enumerations and other necessary tools, to extend the techniques of Kim and Seo to
permutations with cycle type (2, n-2) and (3, n-3).
- Goldbach's conjecture in Z[X]. (with C.
Stewart)
- C. R. Math. Acad. Sci. Soc. R. Can., 20(3):83-85,
1998.
- Abstract: In this paper, we prove that given any
polynomial F(X) in Z[X], there exist two irreducible polynomials P(X), Q(X)
in Z[X] such that F = P + Q. This is the analogue for Z[X] of the famous Goldbach conjecture for integers. The proof uses a combination of the Euclidean algorithm and the Eisenstein irreducibility criterion. Using
the Eisenstein criterion, we also prove that there exist infinitely many
polynomials F(X) in
Z[X] such that F2(X) + 1 is irreducible.