We are going to survey some recent and less recent results pertaining to the study of finite point configurations in Euclidean space and vector spaces over finite fields, centred around the Erdős/Falconer distance problems. We shall place particular emphasis on number-theoretic ideas and obstructions that arise in this area.
A non-technical journey through the basic structure and results on higher-rank graphs.
Many familiar finite games admit natural infinitary analogues, which may captivate and challenge us with sublime complexity. Shall we have a game of infinite chess? Or how about infinite draughts, infinite Hex, infinite Wordle, or infinite Sudoku? In the Chocolatier’s game, the Chocolatier serves up an infinite stream of delicious morsels, while the Glutton aims to eat every one. These games and others illustrate the often subtle strategic aspects of infinite games, and sometimes their downright logical peculiarity. Does every infinite game admit of a winning strategy? Must optimal play be in principle computable? Let us discover the fascinating nature of infinitary strategic thinking.
Let SO3(ℝ) be the 3D-rotation group equipped with the real-manifold topology and the normalized Haar measure μ. Confirming a conjecture by Breuillard and Green, we show that if A is an open subset of SO3(ℝ) with sufficiently small measure, then μ(A2) > 3.99 μ(A).
Suppose that N is large and that A is a subset of {1,..,N} which does not contain two elements x, y with x - y equal to p-1, p a prime. Then A has cardinality at most N1 - c, for some absolute and positive c. I will discuss the history of this kind of question as well as some aspects of the proof of the stated result.
Ruzsa asked whether there exist Fourier-uniform subsets of ℤ/Nℤ with very few 4-term arithmetic progressions (4-AP). The standard pedagogical example of a Fourier-uniform set with a "wrong" density of 4-APs actually has 4-AP density much higher than random. Can it instead be much lower than random? Gowers constructed Fourier uniform sets with 4-AP density at most α4+c. It remains open whether a superpolynomial decay is possible. We will discuss this question and some variants. We relate it to an arithmetic Ramsey question: can one No(1)-color of [N] avoiding symmetrically-colored 4-APs?
In the last few years, expanders have been used in fast graph algorithms in different models, including static, dynamic, and distributed algorithms. I will survey these applications of expanders, explain the expander-related tools behind this development, then give a tutorial on how to construct some of these tools, such as expander decomposition.
In a vertex expanding graph, every small subset of vertices neighbors many different vertices. Random graphs are near-optimal vertex expanders; however, it has proven difficult to create families of deterministic near-optimal vertex expanders, as the connection between vertex and spectral expansion is limited. We discuss successful attempts to create unique neighbour expanders (a weak version of vertex expansion), as well as limitations in using common combinatorial methods to create stronger expanders.
The boundary algebra of a dimer model derived from a Postnikov diagram may be used to obtain an additive categorification of the cluster algebra of the associated positroid variety. The boundary algebra has an explicit description in the case of Grassmannians but not for more general positroids. It is known that every Postnikov diagram is move equivalent to one which comes from a Le-diagram and has an isomorphic boundary algebra. We use the perfect matching structure of a dimer model derived from a Le-diagram to provide an algorithm for computing the Gabriel quiver and relations of its boundary algebra.
In 2015, Brosnan and Chow, and independently Guay-Paquet, proved the Shareshian-Wachs conjecture, which links the combinatorics of chromatic symmetric functions to the geometry of Hessenberg varieties via a permutation group action on the cohomology ring of regular semisimple Hessenberg varieties. This talk will give a brief overview of that story and discuss how the dot action can be computed in all Lie types using the Betti numbers of certain nilpotent Hessenberg varieties. As an application, we obtain new geometric insight into certain linear relations satisfied by chromatic symmetric functions, known as the modular law.
Algebraic Combinatorics originated in Algebra and Representation Theory, studying their discrete objects and integral quantities via combinatorial methods which have since developed independent and self-contained lives on their own and brought us some beautiful formulas and combinatorial interpretations.
The flagship hook-length formula counts the number of standard Young tableaux, which also give the dimension of the irreducible Specht modules of the symmetric group. The elegant Littlewood-Richardson rule gives the multiplicities of irreducible GL-modules in the tensor products of GL-modules. Such formulas and rules have inspired large areas of study and development beyond Algebra and Combinatorics, becoming applicable to Integrable Probability and Statistical Mechanics, and Computational Complexity Theory.
We will see what lies beyond the reach of such nice product formulas and combinatorial interpretations and enter the realm of Computational Complexity Theory, which can formally explain the beauty we see and the difficulties we encounter in finding further formulas and "combinatorial interpretations". In the opposite direction, the 85 year old open problem on Kronecker coefficients of the symmetric group lead to the disproof of the wishful approach of Geometric Complexity Theory (GCT) towards the resolution of the algebraic P vs NP Millennium problem, the VP vs VNP problem. In order to make GCT work and establish computational complexity lower bounds, we need to understand representation-theoretic multiplicities in further detail, possibly asymptotically.
Algebraic Combinatorics originated in Algebra and Representation Theory, studying their discrete objects and integral quantities via combinatorial methods which have since developed independent and self-contained lives on their own and brought us some beautiful formulas and combinatorial interpretations.
The flagship hook-length formula counts the number of standard Young tableaux, which also give the dimension of the irreducible Specht modules of the symmetric group. The elegant Littlewood-Richardson rule gives the multiplicities of irreducible GL-modules in the tensor products of GL-modules. Such formulas and rules have inspired large areas of study and development beyond Algebra and Combinatorics, becoming applicable to Integrable Probability and Statistical Mechanics, and Computational Complexity Theory.
We will see what lies beyond the reach of such nice product formulas and combinatorial interpretations and enter the realm of Computational Complexity Theory, which can formally explain the beauty we see and the difficulties we encounter in finding further formulas and "combinatorial interpretations". In the opposite direction, the 85 year old open problem on Kronecker coefficients of the symmetric group lead to the disproof of the wishful approach of Geometric Complexity Theory (GCT) towards the resolution of the algebraic P vs NP Millennium problem, the VP vs VNP problem. In order to make GCT work and establish computational complexity lower bounds, we need to understand representation-theoretic multiplicities in further detail, possibly asymptotically.
Given a group G and two vectors v and w in a representation V, one can ask: do v and w lie in the same orbit? This is what we call the orbit problem. For the action of GLn on m-tuples of n × n matrices, the orbit problem translates to the module isomorphism problem for which there is a known polynomial time algorithm. In joint work with Visu Makam, we also gave a polynomial time algorithm for deciding whether the orbit closures of v and w intersect. We also have similar results for the left-right action of SLn × SLn on the space of m-tuples of matrices. These results are related to interesting problems in algebraic complexity theory, such as non-commutative rational identity testing. The graph isomorphism problem can also formulated as an orbit problem. No polynomial time algorithm for the graph isomorphism problem is known. I will discuss an algorithm for the graph isomorphism problem that is more powerful than the higher-dimensional Weisfeiler-Leman algorithm when it comes to distinguishing pairs of non-isomorphic graphs in polynomial time. (This algorithm could potentially be polynomial time, but we will not make such a bold claim.)
Erdős-style geometry is concerned with combinatorial questions about simple geometric objects, such as counting incidences between finite sets of points, lines, etc. These questions can be typically viewed as asking for the possible number of intersections of a given (semi-)algebraic variety with large finite grids of points. An influential theorem of Elekes and Szabó indicates that such intersections have maximal size only for varieties that are closely connected to algebraic groups. Techniques from model theory - Hrushovski's group configuration and its variants - are very useful in recognizing these groups, and allow to obtain higher arity and dimension generalizations of the Elekes-Szabó theorem. In fact, all of this is not just about polynomials and works in the larger setting of definable sets in o-minimal structures.
We will discuss a version of the Green-Tao arithmetic regularity lemma and counting lemma which works in the generality of all linear forms. In this talk we will focus on the qualitative and algebraic aspects of the result.
We show that for every positive integer k there are positive constants C and c such that if A is a subset of {1, 2, ..., n} of size at least C n1/k, then, for some d ≤ k-1, the set of subset sums of A contains a homogeneous d-dimensional generalized arithmetic progression of size at least c|A|d+1. This strengthens a result of Szemerédi and Vu, who proved a similar statement without the homogeneity condition. As an application, we make progress on the Erdős-Straus non-averaging sets problem, showing that every subset A of {1, 2, ..., n} of size at least n√2 - 1 + o(1) contains an element which is the average of two or more other elements of A. This gives the first polynomial improvement on a result of Erdős and Sárközy from 1990.
It is an open question as to whether the prime numbers contain the sum A+B of two infinite sets of natural numbers A, B (although results of this type are known assuming the Hardy-Littlewood prime tuples conjecture). Using the Maynard sieve and the Bergelson intersectivity lemma, we show the weaker result that there exist two infinite sequences a1 < a2 < ... and b1 < b2 < ... such that ai + bj is prime for all i < j. Equivalently, the primes are not 'translation-finite' in the sense of Ruppert. As an application of these methods we show that the orbit closure of the primes is uncountable.
It is an open question as to whether the prime numbers contain the sum A+B of two infinite sets of natural numbers A, B (although results of this type are known assuming the Hardy-Littlewood prime tuples conjecture). Using the Maynard sieve and the Bergelson intersectivity lemma, we show the weaker result that there exist two infinite sequences a 1 < a 2 < ... and b 1 < b 2 < ... such that ai + bj is prime for all i < j. Equivalently, the primes are not "translation-finite" in the sense of Ruppert. As an application of these methods we show that the orbit closure of the primes is uncountable.
To study polynomial representations of general and special linear groups in characteristic zero one can use formal characters to work with symmetric functions instead. The situation gets more complicated when working over a field k of non-zero characteristic. However, by describing the representation ring of kSL2(𝔽p) modulo projective modules appropriately we are able to use symmetric functions with a suitable specialisation to study a family of polynomial representations of kSL2(𝔽p) in the stable category. In this talk we describe how this introduction of symmetric functions works and how to compute various modular plethysms of the natural kSL2(𝔽p)-module in the stable category. As an application we classify which of these modular plethysms are projective and which are 'close' to being projective. If time permits, we describe how to generalise these classifications using a rule for exchanging Schur functors and tensoring with an endotrivial module.
Finding the smallest integer N=ESd(n) such that in every configuration of N points in ℝd in general position there exist n points in convex position is one of the most classical problems in extremal combinatorics, known as the Erdős-Szekeres problem. In 1935, Erdős and Szekeres famously conjectured that ES2(n)=2n−2+1 holds, statement which was nearly confirmed in 2016 by Suk, who showed that ES2(n)=2n+o(n). In higher dimensions, on the other hand, it has been unclear even what kind of asymptotic behaviour to expect from ESd(n), with conflicting predictions arising over the years. In this talk, we will discuss a recent proof that ESd(n)=2o(n) holds for all d≥3. Joint work with Dmitrii Zakharov.
