Positivity problems at the boundary between combinatorics and analysis

Combinatorics is the branch of mathematics concerned with counting finite
structures of various types (permutations, graphs, etc.); it has
applications in computer science, statistical physics, molecular biology,
and many other fields. Analysis, by contrast, is the branch of mathematics
concerned with continuous variation (i.e. functions of real or complex
numbers); it has applications in nearly all fields of science and engineering.
The proposed research lies at the interface between combinatorics and
analysis: it involves using combinatorial tools to study analytic problems,
and vice versa. More specifically, the proposed research comprises
three themes, all of which are aimed at exploring novel positivity properties
that arise at the interface between combinatorics and analysis.
The first theme involves studying situations in which inverse powers
of combinatorially important polynomials have Taylor expansions with
positive coefficients. The second theme involves studying situations
in which certain matrices formed from sequences of combinatorially
important polynomials have a property called "total positivity".
The third theme involves studying situations in which certain power
series formed from combinatorially important polynomials (for example,
the counting polynomials of connected graphs) have positive coefficients.
This latter property was discovered empirically by the PI in many
situations, but most of these have not yet been proven, and their deeper
meaning remains to be elucidated.

Economic and Societal Impacts:

The nature of research in pure mathematics is that it is traditionally
somewhat removed from direct commercial and governmental usage.
But since combinatorics is fundamental to computer science
and in particular to the study of algorithmic complexity,
advances in combinatorics can have unforeseen implications and applications
over the longer term.
For instance, the development of randomised algorithms
--- inspired in part by Monte Carlo algorithms from statistical physics ---
has radically altered the landscape of computational complexity,
because some problems that are intractable for exact computation (NP-hard)
can be tractable for approximate computation by a randomised algorithm (fpras).
In a similar way, ideas from the statistical mechanics
of phase transitions have clarified the distinction
between "difficult'' and "less-difficult'' instances
of NP-complete problems such as Boolean satisfiability (SAT).
Though it would be foolhardy to confidently predict similar practical
spin-offs from this (or any other) pure mathematical research,
it is not unreasonable to imagine that
the research programme proposed here could contribute in the long run,
in probably unpredictable ways, to EPSRC's Digital Economy strategic priority.
Over the shorter term it could very well also contribute to
EPSRC's priority area of New Connections between the Mathematical
and Computer Sciences, in such areas as
deterministic and random algorithms, computational complexity,
symbolic computation, and applications of graph theory and combinatorics.
In order to facilitate these potential spin-offs,
I propose to begin by giving seminars to computer scientists
on various aspects of this work:
for instance, at the annual Analysis of Algorithms (AofA) meeting,
at which my collaborator on theme #3, Jim Fill, is a regular participant.


Public Engagement:

Over the past two decades I have given numerous talks for the general public
--- in the UK, USA, Canada, and a dozen European and Latin American countries ---
aimed at raising public understanding of scientific methodology and scientific results.
I now propose to carry this experience over to popularisation
of my own (and my colleagues') mathematical research.
In fact, combinatorics is a subject area within mathematics
that is perhaps easier to popularise than other fields,
because many of its definitions are elementary and easily visualizable.
I have already given several such talks aimed at undergraduates,
so adaptation for a general educated public curious about mathematics
ought not be too difficult.

In addition, Alex Scott and I wrote a semi-popular article on the
mathematics of phase transitions, aimed at British high-school students
considering university study in mathematics;
this article was later translated into French and published in the magazine Quadrature.
I propose to write further articles of a similar nature, on subjects related to this research.