Tag - Combinatorics

Lianna Hambardzumyan: Larger Corner-free Sets in High Dimensions

24th July, 2023

A central question in additive combinatorics is to understand how large arithmetic progression-free sets can be. In this talk, I will focus on this question for high-dimensional generalization of arithmetic progressions (AP) known as corners. A (2-dimensional) corner is a triple of the form (x,y),(x+d,y),(x,y+d) for some d>0 in [N] × [N]. Extending this definition to higher dimensions, a k-dimensional corner in [N]k is a (k+1)-tuple defined similarly for some d. While it is known that corner-free sets have a vanishingly small density, the precise bounds on their size remain unknown. Until recently, the best-known corner-free sets were derived from constructions of AP-free sets: a construction of a 3-term AP-free set by Behrend from 1946, and a generalization by Rankin for k-term APs in 1961. New results by Linial and Shraibman (CCC 2021) and Green (New Zealand Journal of Mathematics 2021) changed this picture; they improved the upper bound for k=2 by adopting a communication complexity point of view.

I will discuss our recent work where we employ the same perspective of communication complexity and obtain the first improvement on the upper bound of the size of high-dimensional (k>2) corner-free sets since the original construction of Rankin.

Alex Iosevich: Some number-theoretic aspects of finite point configurations

29th June, 2023

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.

Joel David Hamkins: Infinite Games – Strategies, Logic, Theory, and Computation

16th June, 2023

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.

Yifan Jing: Measure Doubling for Small Sets in SO3(ℝ)

30th May, 2023

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

Ben Green: On Sarkozy’s theorem for shifted primes

11th May, 2023

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.

Yufei Zhao: Uniform Sets with Few Progressions via Colorings

9th May, 2023

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?

Thatchaphol Saranurak: Using Expanders for Fast Graph Algorithms

9th May, 2023

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.

Theo McKenzie: Graph Vertex Expansion

8th May, 2023

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.

Jonah Berggren: Boundary algebras of positroids

27th April, 2023

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.