|
|||||
[PDF]
- MIREILLE BOUSQUET-MÉLOU, CNRS, Université de Bordeaux
Counting lattice walks confined to cones [PDF]
-
The study of lattice walks confined to cones is a lively topic in enumerative combinatorics, and has witnessed rich developments in the past 20 years. Typically, one is given a finite set of steps $S$ in $Z^d$, and a cone $C$ in $R^d$. Exactly $|S|^n$ walks of length $n$ start from the origin and take their steps in $S$. But how many remain in the cone $C$?
One of the motivations for studying such questions is that such walks encode many objects in discrete mathematics, statistical physics, probability theory, among other fields.
In the past 20 years, several approaches have been combined to understand how the choice of the steps and of the cone influence the nature of the counting sequence $a(n)$, or of the the associated series $A(t)=\sum a(n) t^n$. Is $A(t)$ rational, algebraic, or solution of a differential equation? This is now completely understood when $C$ is the first quadrant of the plane and $S$ only consists of "small" steps. This "simple" case involves tools coming from an attractive variety of fields: algebra on formal power series, complex analysis, computer algebra, differential Galois theory. Much remains to be done, for other cones and sets of steps.
- CAROLINE COLIJN, Simon Fraser University
Mathematics and policy in the COVID-19 pandemic [PDF]
-
Mathematics and modelling have had unprecedented levels of attention from policy makers, public health, the media and the public during the COVID-19 pandemic. While we always anticipated that another pandemic would come one day, we did not anticipate that R0, herd immunity, flattening the curve and other mathematical concepts would be so much in the public eye. In this talk I will describe some of the work our group has done on the COVID-19 pandemic, from deterministic to stochastic modelling, and I will make reference in particular to discrete mathematics and its growing role in evolving pandemics.
- NATASHA MORRISON, University of Victoria
Uncommon systems of equations [PDF]
-
A system of linear equations $L$ over $\mathbb{F}_q$ is common if the number of monochromatic solutions to $L$ in any two-colouring of $\mathbb{F}_q^n$ is asymptotically at least the expected number of monochromatic solutions in a random two-colouring of $\mathbb{F}_q^n$. Motivated by existing results for specific systems (such as Schur triples and arithmetic progressions), as well as extensive research on common and Sidorenko graphs, the systematic study of common systems of linear equations was recently initiated by Saad and Wolf. Building on earlier work of of Cameron, Cilleruelo and Serra, as well as Saad and Wolf, common linear equations have been fully characterised by Fox, Pham and Zhao.
In this talk I will discuss some recent progress towards a characterisation of common systems of two or more equations. In particular we prove that any system containing an arithmetic progression of length four is uncommon, confirming a conjecture of Saad and Wolf. This follows from a more general result which allows us to deduce the uncommonness of a general system from certain properties of one- or two-equation subsystems.
This is joint work with Nina Kam\v{c}ev and Anita Liebenau.
- SERGEY NORIN, McGill University
Recent progress towards Hadwiger's conjecture [PDF]
-
Hadwiger's conjecture from 1943 is a far-reaching strengthening of the Four Color Theorem. It states that every simple graph with no $K_t$ minor can be properly colored using $t-1$ colors. In this talk we will survey recent progress towards the conjecture, as well as the remaining (major) obstacles.
- WILLIAM T. TROTTER, Georgia Tech University
Posets with Planar Cover Graphs [PDF]
-
For nearly 50 years, my favorite research topic has been combinatorial problems for posets. Often, but not always, there are analogous problems in graph theory, but the poset versions are typically more challenging. A great example is bounding chromatic number and dimension in terms of maximum degree.
In the last five years, there has been increasing attention paid to problems that bound the dimension of a poset in terms of the largest standard example it contains. The analogous problem in graph theory is bounding chromatic number in terms of maximum clique size. Of course, in the most general setting, there is no such bound, but researchers have found many interesting classes where one can be shown to exist.
For posets, it has been conjectured for more than 40 years that dimension is bounded in terms of the largest standard example for posets with planar cover graphs, and there has been a sequence of results that hold promise to providing a pathway to the final resolution of the conjecture. Surveying these results will be the primary focus of this talk.
- LÁSZLÓ VÉGH, London School of Economics
The circuit imbalance measure and its role in linear programming [PDF]
-
The talk will give an overview of some recent progress on the strongly polynomial solvability of linear programs (LPs), extending classical results of Tardos, and Vavasis and Ye. A key concept turns out to be the `circuit imbalance measure' $\kappa_A$ of a matrix: this is the largest ratio between the absolute values between the nonzero entries of a support minimal vector in the kernel of the matrix. We explain different approaches to solve an LP given by an $n\times m$ constraint matrix $A$ in time poly$(n,m,\log\kappa_A)$ (but independent of the cost and right hand side vectors), based on proximity results as well using layered-least squares interior-point methods. We give a combinatorial characterization of the column rescaling that obtains the smallest possible circuit imbalance value, as well as an efficient algorithm to find an approximately optimal rescaling; this yields a new class of LPs that can be solved in strongly polynomial time.
The talk is based joint works with Daniel Dadush, Sophie Huiberts, and Bento Natura.
- YUFEI ZHAO, Massachusetts Institute of Technology
Extremal problems in discrete geometry [PDF]
-
I present recent progress on several problems in discrete geometry, including equiangular lines, joints, extension complexity, and transitive sets in high dimensions.