Positivity problems at the boundary between combinatorics and analysis

Lead Research Organisation: University College London
Department Name: Mathematics

Abstract

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.

Planned Impact

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.

Publications

10 25 50
 
Description Combinatorial problems from an analytical point of view -- Alex Dyachenko 
Organisation German Research Foundation
Country Germany 
Sector Charity/Non Profit 
PI Contribution I have discovered the phenomenon of coefficientwise Hankel-total positivity in many sequences of combinatorial polynomials, and I am trying to devise methods for proving it.
Collaborator Contribution Alexander Dyachenko received a fellowship from the German Research Foundation (Deutsche Forschungsgemeinschaft) to spend 2 years working with me at University College London. Dr. Dyachenko brings a background in analysis, and in particular a familiarity with moment problems, that will be very useful in our applications to combinatorial problems.
Impact None yet, but we have several projects in preparation.
Start Year 2018
 
Description Continued fractions and linear recurrences -- Jesus Salas 
Organisation Charles III University of Madrid
Country Spain 
Sector Academic/University 
PI Contribution I provided questions and methods concerning continued fractions and total positivity.
Collaborator Contribution Professor Jesus Salas provided expertise in computer algebra.
Impact None yet, but we have a paper in progress.
 
Description Continued fractions for combinatorial polynomials -- JIang Zeng 
Organisation Claude Bernard University Lyon 1 (UCBL)
Department Camille Jordan Institute
Country France 
Sector Academic/University 
PI Contribution I found empirically some new continued fractions for multivariate combinatorial polynomials.
Collaborator Contribution Jiang Zeng (Univ Lyon) contributed the methods that have allowed us to prove some of these continued fractions.
Impact None yet -- work still in progress. But one of our long articles is close to being finished.
Start Year 2014
 
Description Positivity for fractional powers of formal power series -- Alex Scott 
Organisation University of Oxford
Department Nuffield Department of Medicine
Country United Kingdom 
Sector Academic/University 
PI Contribution Alex Scott (Oxford) and I have continued our work on positivity for fractional powers of formal power series. We are currently proving positivity for some multivariate formal power series arising as fractional powers of determinants.
Collaborator Contribution We work together on all aspects, and it is difficult to disentangle our contributions.
Impact Paper still in preparation.
 
Description Total positivity and Hadamard products -- Shaun Fallat and Charles Johnson 
Organisation College of William & Mary
Country United States 
Sector Academic/University 
PI Contribution Shaun Fallat (U Regina), Charles Johnson (William and Mary) and I worked together to prove theorems about the total positivity of Hadamard products. I provided the initial conjecture, and I provided many counterexamples (found by computer search).
Collaborator Contribution Johnson contributed an important idea to the proof (the idea of using contiguous minors). Fallat and Johnson contributed other useful ideas as well.
Impact Total positivity of sums, Hadamard products and Hadamard powers: Results and counterexamples, Linear Algebra and Its Applications 520, 242--259 (2017)
Start Year 2014
 
Description Total positivity and Hadamard products -- Shaun Fallat and Charles Johnson 
Organisation University of Regina
Country Canada 
Sector Academic/University 
PI Contribution Shaun Fallat (U Regina), Charles Johnson (William and Mary) and I worked together to prove theorems about the total positivity of Hadamard products. I provided the initial conjecture, and I provided many counterexamples (found by computer search).
Collaborator Contribution Johnson contributed an important idea to the proof (the idea of using contiguous minors). Fallat and Johnson contributed other useful ideas as well.
Impact Total positivity of sums, Hadamard products and Hadamard powers: Results and counterexamples, Linear Algebra and Its Applications 520, 242--259 (2017)
Start Year 2014
 
Description Total positivity and combinatorics -- Andrew Elvey Price 
Organisation University of Melbourne
Country Australia 
Sector Academic/University 
PI Contribution I am providing ideas concerrning total positivity, and conjectures and open questions.
Collaborator Contribution Andrew Elvey Price (a PhD student of Professor Tony Guttmann) has already made several important contributions, concerning a T-fraction for the Ward polynomials and concerning functional equations for generalizations of the Bell polynomials.
Impact https://arxiv.org/abs/2001.01468
Start Year 2017
 
Description Total positivity and combinatorics -- Bao-Xuan Zhu 
Organisation Jiangsu Normal University
Country China 
Sector Academic/University 
PI Contribution Bao-Xuan Zhu is visiting me at UCL for approximately 12 months (September 2017 - August 2018) to collaborate on problems related to total positivity and combinatorics. This visit is partly funded by the China Scholarship Council and partly by this EPSRC grant. I am contributing many ideas concerning total positivity, and many conjectures and open problems.
Collaborator Contribution Professor Zhu is contributing his expertise in combinatorics, especially continued fractions, recurrences, etc.
Impact https://arxiv.org/abs/1807.03271 and other articles in progress
Start Year 2017
 
Description Total positivity and combinatorics -- Lili Mu 
Organisation Liaoning Normal University
Country China 
Sector Academic/University 
PI Contribution I provided questions and methods concerning total positivity.
Collaborator Contribution Dr. Lili Mu provided additional expertise concerning combinatorics, especially Riordan arrays.
Impact None yet, but we have some projects in progress.
Start Year 2019
 
Description Total positivity and combinatorics -- Lily Liu 
Organisation Qufu Normal University
Country China 
Sector Academic/University 
PI Contribution Professor Lily Li Liu (Qufu Normal University, China) was a visitor in my research group at UCL for 5 months (Sept 2018 - Jan 2019). We worked together on various problems related to combinatorics and total positivity.
Collaborator Contribution Professor Liu has an excellent facility for devising complicated algebraic proofs.
Impact We are currently working on a joint paper concerning linear transformations that preserve strong log-convexity or strong log-concavity.
Start Year 2018
 
Description Total positivity and combinatorics -- Xi Chen 
Organisation Dalian University of Technology
Country China 
Sector Academic/University 
PI Contribution I provided ideas and methods concerning total positivity.
Collaborator Contribution Dr. Chen provided expertise in combinatorics, especially concerning exponential Riordan arrays,
Impact None yet, but we have several projects in progress.
Start Year 2019