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

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.

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.

### Organisations

- University College London, United Kingdom (Fellow, Lead Research Organisation)
- University of Oxford, United Kingdom (Collaboration)
- German Research Foundation (Collaboration)
- Charles III University of Madrid (Collaboration)
- Qufu Normal University (Collaboration)
- Liaoning Normal University (Collaboration)
- University of Regina, Canada (Collaboration)
- Dalian University of Technology, China (Collaboration)
- College of William and Mary, United States (Collaboration)
- University of Melbourne, Australia (Collaboration)
- Jiangsu Normal University (Collaboration)
- Claude Bernard University Lyon 1 (UCBL) (Collaboration)

## People |
## ORCID iD |

Alan David Sokal (Principal Investigator / Fellow) |

### Publications

Elvey Price A
(2020)

*Phylogenetic Trees, Augmented Perfect Matchings, and a Thron-type Continued Fraction (T-fraction) for the Ward Polynomials*in The Electronic Journal of Combinatorics
Elvey Price Andrew
(2020)

*Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials*in arXiv e-prints
Fallat S
(2017)

*Total positivity of sums, Hadamard products and Hadamard powers: Results and counterexamples*in Linear Algebra and its Applications
Fallat S
(2021)

*Corrigendum to "Total positivity of sums, Hadamard products and Hadamard powers: Results and counterexamples" [Linear Algebra Appl. 520 (2017) 242-259]*in Linear Algebra and its Applications
Lv JP
(2018)

*Duality and the universality class of the three-state Potts antiferromagnet on plane quadrangulations.*in Physical review. E
Pétréolle M
(2021)

*Lattice paths and branched continued fractions II. Multivariate Lah polynomials and Lah symmetric functions*in European Journal of Combinatorics
Sokal A
(2020)

*The Euler and Springer numbers as moment sequences*in Expositiones Mathematicae
Sokal A
(2019)

*How To Generalize (and Not To Generalize) the Chu-Vandermonde Identity*in The American Mathematical Monthly
Sokal A
(2020)

*A remark on the enumeration of rooted labeled trees*in Discrete Mathematics
Sokal A
(2020)

*Wall's continued-fraction characterization of Hausdorff moment sequences: A conceptual proof*in Proceedings of the American Mathematical SocietyDescription | 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 |