Past Combinatorial Theory Seminar

Since the foundational works of Diaconis, pointwise character bounds of the form $\chi(\sigma) \le \chi(1)^\alpha$ have guided the study of growth in finite simple groups. However, this classical machinery hits an algebraic bottleneck when confronted with non-class functions and unstructured subsets.

In this talk, we bypass this barrier by replacing classical representation theory with discrete analysis. By decomposing functions as $f = \sum f_\rho$ and bounding the $L_2$ norm $\|f_\rho\|_2 \le \chi_\rho(1)^\alpha$ for each representation $\rho$, we develop a robust theory of Fourier anti-concentration. We will demonstrate how this resolves the Liebeck–Nikolov–Shalev (LNS) conjecture—proving a group can be expressed optimally as the product of conjugates of an arbitrary subset $A$—and discuss how applying Boolean function analysis tools like hypercontractivity pushes this philosophy even further.

Colour Refinement is a combinatorial method that distinguishes vertices in graphs based on their local neighborhood structure. By encoding these local properties into vertex colours that are refined iteratively, the process eventually stabilises into a final colouring which serves as an isomorphism test on a large class of graphs.

The central complexity parameter of the algorithm is the number of iterations required to reach stabilisation. For $n$-vertex graphs, the upper bound is $n−1$. We call graphs that attain this maximum long-refinement graphs. Their final colourings are discrete, meaning every vertex is uniquely identified by its colour.  For a long time, it was not clear whether such graphs actually exist. My talk provides an overview of the history of this graph class and reports on recent work towards a full characterisation of it.

By restricting our scope to graphs with small degrees, we have constructed infinite families of long-refinement graphs. Furthermore, by reverse-engineering connections between colour classes, we obtained a complete classification of long-refinement graphs with small (or, equivalently, large) degrees. This analysis offers deep insights into the dynamics of the refinement process, revealing that all long-refinement graphs with maximum degree 3 can be described by compact strings over a remarkably small alphabet.

The talk is based on collaborations with Brendan D. McKay and T. Devini de Mel.

Random walks on graphs can mix slowly. To speed it up, imagine that at each step instead of choosing the neighbor at random, there is a small probability $\varepsilon > 0$ that we can choose it. We show that in this case, at least for graphs of bounded degree, there is a way to steer the walk so that we visit every vertex in $n^{1+o(1)}$ many steps. The key to this result is a way to decompose arbitrary graphs into small-diameter pieces.

An edge-colouring of a graph $G$ can fail to be rainbow for two reasons: either it contains a monochromatic cherry (a pair of incident edges), or a monochromatic matching of size two. A colouring is a proper colouring if it forbids the first structure, and a star-colouring if it forbids the second structure. I will talk about the problem of determining the maximum number of colours in a star-colouring of a large complete graph which does not contain a rainbow copy of a given graph $H$. This problem is a special case of one studied by Axenovich and Iverson on generalised Ramsey numbers.

Joint work with Allan Lo, Klas Markström, Dhruv Mubayi, Maya Stein and Lea Weber.

I discuss two separate projects which evoke/strengthen connections between combinatorics and ideas from statistical physics.

The first concerns the minimum number of independent sets in triangle-free graphs of a given edge-density. We present a lower bound using a generalisation of the inductive method of Shearer (1983) for the sharpest-to-date off-diagonal Ramsey upper bound. This result is matched remarkably closely by the count in binomial random graphs.

The second sets out a qualitative generalisation of a well-known sharp result of Haxell (2001) for independent transversals in vertex-partitioned graphs of given maximum degree. That is, we consider the space of independent transversals under one-vertex modifications. We show it is connected if the parts are strictly larger than twice the maximum degree, and if the requirement is only at least twice the maximum degree we find an interesting sufficient condition for connectivity.

These constitute joint works with Pjotr Buys, Jan van den Heuvel, and Kenta Ozeki.

If time permits, I sketch some thoughts about a systematic pursuit of more connections of this flavour.

For a tree $T$ whose bipartition classes have sizes $t_1 \ge t_2$, two simple constructions shows that the Ramsey number of $T$ is at least $\max\{t_1+2t_2,2t_1\}-1$. In 1974, Burr conjectured that equality holds for every tree. It turns out that Burr’s conjecture is false for certain trees called the double stars, though all of the known counterexamples have large maximum degrees. In 2002, Haxell, Łuczak, and Tingley showed that Burr’s conjecture is approximately true if one imposes a maximum degree condition.

We show that Burr’s conjecture holds for all trees with up to small linear maximum degrees. That is, there exists $c>0$ such that for every $n$-vertex tree $T$ with maximum degree at most $cn$ and bipartition class sizes $t_1\ge t_2$, its Ramsey number $R(T)$ is exactly $\max\{t_1+2t_2,2t_1\}-1$. We also generalise this result to determine the exact asymmetric Ramsey number $R(T,S)$ of two trees $T$ and $S$ under certain additional conditions, and construct examples showing that these conditions are necessary. 

This talk is based on joint work with Richard Montgomery and Matías Pavez-Signé.

It is a classical result that a random permutation of $n$ elements has, on average, about $\log n$ cycles. We generalise this fact to all directed $d$-regular graphs on $n$ vertices by showing that, on average, a random cycle-factor of such a graph has $\mathcal{O}((n\log d)/d)$ cycles. This is tight up to the constant factor and improves the best previous bound of the form $\mathcal{O}({n/\sqrt{\log d}})$ due to Vishnoi. It also yields randomised polynomial-time algorithms for finding such a cycle-factor and for finding a tour of length $(1+\mathcal{O}((\log d)/d)) \cdot n$ if the graph is connected. The latter result makes progress on a restriction of the Traveling Salesman Problem to regular graphs, a problem studied by Vishnoi and by Feige, Ravi, and Singh. Our proof uses the language of entropy to exploit the fact that the upper and lower bounds on the number of perfect matchings in regular bipartite graphs are extremely close.

This talk is based on joint work with Micha Christoph, Nemanja Draganić, António Girão, Eoin Hurley, and Alp Müyesser.

A temporal graph $G$ is a sequence of graphs $G_1, G_2, \ldots, G_t$ on the same vertex set. In this talk, we are interested in the analogue of the Travelling Salesman Problem for temporal graphs. It is referred to in the literature as the Temporal Exploration Problem, and asks for the minimum length of an exploration of the graph, that is, a sequence of vertices such that at each time step $t$, one either stays at the same vertex or moves along a single edge of $G_t$.

One natural and still open case is when each graph $G_t$ is connected and has bounded maximum degree. We present a short proof that any such graph admits an exploration in $O(n^{3/2}\sqrt{\log n})$ time steps. In fact, we deduce this result from a more general statement by introducing the notion of average temporal maximum degree. This more general statement improves the previous best bounds, under a unified approach, for several studied exploration problems.

This is based on joint work with Carla Groenland, Lukas Michel and Clément Rambaud.

Basic Turán theory asks how many edges a graph can have, given certain restrictions such as not having a large clique. A more generalized Turán question asks how many copies of a fixed subgraph $H$ the graph can have, given certain restrictions. There has been a great deal of recent interest in the case where the restriction is planarity. In this talk, we will discuss some of the general results in the field, primarily the asymptotic value of ${\bf N}_{\mathcal P}(n,H)$, which denotes the maximum number of copies of $H$ in an $n$-vertex planar graph. In particular, we will focus on the case where $H$ is a cycle.

It was determined that ${\bf N}_{\mathcal P}(n,C_{2m})=(n/m)^m+o(n^m)$ for small values of $m$ by Cox and Martin and resolved for all $m$ by Lv, Győri, He, Salia, Tompkins, and Zhu.

The case of $H=C_{2m+1}$ is more difficult and it is conjectured that ${\bf N}_{\mathcal P}(n,C_{2m+1})=2m(n/m)^m+o(n^m)$. 

We will discuss recent progress on this problem, including verification of the conjecture in the case where $m=3$ and $m=4$ and a lemma which reduces the solution of this problem for any $m$ to a so-called "maximum likelihood" problem. The maximum likelihood problem is, in and of itself, an interesting question in random graph theory.

How many vectors are needed to simultaneously generate $m$ complete flags in $\mathbb{R}^d$, in the worst-case scenario?  A classical linear algebra fact, essentially equivalent to the Bruhat cell decomposition for $\text{GL}_d$, says that the answer is $d$ when $m=2$.  We obtain a precise answer for all values of $m$ and $d$.  Joint work with Federico Glaudo and Chayim Lowen.

Given a finite poset $P$ we ask how small a family of subsets of $[n]$ can be such that it does not contain an induced copy of the poset, but adding any other subset creates such a copy. This number is called the saturation number of $P$, denoted by $\operatorname{sat}^*(n,P)$. Despite the apparent similarity to the saturation for graphs, this notion is vastly different. For example, it has been shown that the saturation numbers exhibit a dichotomy: for any poset, the saturation number is either bounded, or at least $2 n^{1/2}$. In fact, it is believed that the saturation number is always bounded or exactly linear. In this talk we will be discussing the most recent advances in this field, with the focus on the diamond poset, whose saturation number was unknown until recently.

Joint with Sean Jaffe.

What do the roots of random polynomials look like? Classical works of Erdős-Turán and others show that most roots are near the unit circle and they are approximately rotationally equidistributed. We will begin with an understanding of why this happens and see how ideas from extremal combinatorics can mix with analytic and probabilistic arguments to show this. Another main feature of random polynomials is that their roots tend to "repel" each other. We will see various quantitative statements that make this rigorous. In particular, we will study the smallest separation $m_n$ between pairs of roots and show that typically $m_n$ is on the order of $n^{-5/4}$. We will see why this reflects repulsion between roots and discuss where this repulsion comes from. This is based on joint work with Oren Yakir.

Consider a tail trivial, positively associated site percolation process such that the set of open vertices is stochastically dominated by the set of closed ones. We show that, for any planar graph $G$, such a process must contain zero or infinitely many infinite connected components. The assumptions cover Bernoulli site percolation at parameter $p$ less than or equal to one half, resolving a conjecture of Benjamini and Schramm. As a corollary, we prove that $p_c$ is greater than or equal to $1/2$ for any unimodular, invariantly amenable planar graphs.

We will then apply this percolation statement to the loop $O(n)$ model on the hexagonal lattice, and show that, whenever $n$ is between $1$ and $2$ and $x$ is between $1/\sqrt{2}$ and $1$, the model exhibits infinitely many loops surrounding every face of the lattice, giving strong evidence for conformally invariant behavior in the scaling limit (as conjectured by Nienhuis).

This is joint work with Alexander Glazman (University of Innsbruck) and Nathan Zelesko (Northeastern University).

Given a set $A$ and a scalar $\lambda$, how large must the sum of dilate $A+\lambda\cdot A=\{a+\lambda a'\mid a,a'\in A\}$ be in terms of $|A|$? In this talk, we will discuss two different settings of this problem, and how they relate to each other.

• For transcendental $\lambda\in \mathbb{C}$ and $A\subset \mathbb{C}$, how does $|A+\lambda\cdot A|$ grow with $|A|$?
• For a fixed large $\lambda\in \mathbb{Z}$ and even larger prime $p$, with $A\subset \mathbb{Z}/p\mathbb{Z}$, how does the density of $A+\lambda\cdot A$ depend on the density of $A$?

Joint with David Conlon.

Even in a totally discrete space $X$ you need to know how to move between distinct points. A path $P_{x,y}$ between two points $x,y \in X$ is a sequence of points in $X$ that starts with $x$ and ends with $y$. A path system is a collection of paths $P_{x,y}$, one per each pair of distinct points $x, y$ in $X$. We restrict ourselves to the undirected case where $P_{y,x}$ is $P_{x,y}$ in reverse.

Strictly metrical path systems are ubiquitous. They are defined as follows: There is some spanning, connected graph $(X, E)$ with positive edge weights $w(e)$ for all $e\in E$ and $P_{x,y}$ is the unique $w$-shortest $xy$ path. A metrical path system is defined likewise, but $w$-shortest paths need not be unique. Even more generally, a path system is called consistent  (no $w$ is involved here) if it satisfies the condition that when point $z$ is in $P_{x,y}$, then $P_{x,y}$ is $P_{x,z}$ concatenated with $P_{z,y}$. These three categories of path systems are quite different from each other and in our work we find quantitative ways to capture these differences.

Joint work with Daniel Cizma.

A 1977 conjecture of Erdős and Hajnal asserts that for every hereditary class of graphs not containing all graphs, every graph in the class has a polynomial-sized clique or stable set. Fox, Pach, and Suk and independently Chernikov, Starchenko, and Thomas asked whether this conjecture holds for every class of graphs of bounded VC-dimension. In joint work with Alex Scott and Paul Seymour, we resolved this question in the affirmative. The talk will introduce the Erdős–Hajnal conjecture and discuss some ideas behind the proof of the bounded VC-dimension case.

Permutons are a framework set up for understanding large permutations, and are instrumental in pattern densities. However, they miss most of the algebraic properties of permutations. I will discuss what can still be said in this direction, and some possible ways to move beyond permutons. Joint with Fiona Skerman and Peter Winkler.

Do there exist universal sequences for all mazes on the two-dimensional integer lattice? We will give background on this question, as well as some recent results. Joint work with Mariaclara Ragosta.

Semidefinite programming (SDP) is a powerful tool in the design of approximation algorithms. After providing a gentle introduction to the basics of this method, I will explore a different facet of SDP and show how it can be used to derive short and elegant proofs of both classical and new estimates related to the MaxCut problem and discrepancy theory in graphs and matrices.

Building on this, I will demonstrate how these results lead to an improved upper bound on the celebrated log-rank conjecture in communication complexity.

In this talk I will discuss a new lower bound for the off-diagonal Ramsey numbers $R(3,k)$. For this, we develop a version of the triangle-free process that is significantly easier to analyse than the original process. We then 'seed' this process with a carefully chosen graph and show that it results in a denser graph that is still sufficiently pseudo-random to have small independence number.

This is joint work with Marcelo Campos, Matthew Jenssen and Marcus Michelen.

A matroid is frame if it can be extended such that it possesses a basis $B$ (a frame) such that every element is spanned by at most two elements of $B$. Frame matroids extend the class of graphic matroids and also have natural graphical representations. We characterise the inequivalent graphical representations of 3-connected frame matroids that have a fixed element $\ell$ in their frame $B$. One consequence is a polynomial time recognition algorithm for frame matroids with a distinguished frame element.

Joint work with Jim Geelen and Cynthia Rodríquez.

At most how many edge-disjoint Hamilton cycles does a given directed graph contain? It is easy to see that one cannot pack more than the minimum in-degree or the minimum out-degree of the digraph. We show that in the random directed graph $D(n,p)$ one can pack precisely this many edge-disjoint Hamilton cycles, with high probability, given that $p$ is at least the Hamiltonicity threshold, up to a polylog factor.

Based on a joint work with Asaf Ferber.

Graphs (and structures) which have a linear ordering of their vertices with given local properties have a rich spectrum of complexities. Some have full power of class NP (and thus no dichotomy) but for biconnected patterns we get dichotomy. This also displays the importance of Sparse Incomparability Lemma. This is a joint work with Gabor Kun (Budapest).

The class of $t$-perfect graphs consists of graphs whose stable set polytopes are defined by their non-negativity, edge inequalities, and odd circuit inequalities. These were first studied by Chvátal in 1975, motivated by the related and well-studied class of perfect graphs. While perfect graphs are easy to colour, the same is not true for $t$-perfect graphs; numerous questions and conjectures have been posed, and even the most basic, on whether there exists some $k$ such that every $t$-perfect graph is $k$-colourable, has remained open since 1994. I will talk about joint work with Maria Chudnovsky, Linda Cook, James Davies, and Sang-il Oum in which we establish the first finite bound and show that a little less than 200 000 colours suffice.

I will discuss various results and conjectures about off-diagonal hypergraph Ramsey numbers, focusing on recent developments.

A set in the Euclidean plane is called an integer distance set if the distance between any pair of its points is an integer.  All so-far-known integer distance sets have all but up to four of their points on a single line or circle; and it had long been suspected, going back to Erdős, that any integer distance set must be of this special form. In a recent work, joint with Marina Iliopoulou and Sarah Peluse, we developed a new approach to the problem, which enabled us to make the first progress towards confirming this suspicion.  In the talk, I will discuss the study of integer distance sets, its connections with other problems, and our new developments.

Upper bounds on the number of incidences between points and lines, tubes, and other geometric objects, have many applications in combinatorics and analysis. On the other hand, much less is known about lower bounds. We prove a general lower bound for the number of incidences between points and tubes in the plane under a natural spacing condition. In particular, if you take $n$ points in the unit square and draw a line through each point, then there is a non-trivial point-line pair with distance at most $n^{-2/3+o(1)}$. This quickly implies that any $n$ points in the unit square define a triangle of area at most $n^{-7/6+o(1)}$, giving a new upper bound for the Heilbronn's triangle problem.

Joint work with Alex Cohen and Cosmin Pohoata.

The normal covering number $\gamma(G)$ of a finite group $G$ is the minimal size of a collection of proper subgroups whose conjugates cover the group. This definition is motivated by number theory and related to the concept of intersective polynomials. For the symmetric and alternating groups we will see how these numbers are closely connected to some elementary (as in "relating to basic concepts", not "easy") problems in additive combinatorics, and we will use this connection to better understand the asymptotics of $\gamma(S_n)$ and $\gamma(A_n)$ as $n$ tends to infinity.

Paraphrasing the title of Riemann’s famous lecture of 1854 I ask: What is the most rudimentary notion of a geometry? A possible answer is a path system: Consider a finite set of “points” $x_1,…,x_n$ and provide a recipe how to walk between $x_i$ and $x_j$ for all $i\neq j$, namely decide on a path $P_{ij}$, i.e., a sequence of points that starts at $x_i$ and ends at $x_j$, where $P_{ji}$ is $P_{ij}$, in reverse order. The main property that we consider is consistency. A path system is called consistent if it is closed under taking subpaths. What do such systems look like? How to generate all of them? We still do not know. One way to generate a consistent path system is to associate a positive number $w_{ij}>0$ with every pair and let $P_{ij}$ be the corresponding $w$-shortest path between $x_i$ and $x_j$. Such a path system is called metrical. It turns out that the class of consistent path systems is way richer than the metrical ones.

My main emphasis in this lecture is on what we don’t know and wish to know, yet there is already a considerable body of work that we have done on the subject.

The new results that I will present are joint with my student Daniel Cizma as well as with him and with Maria Chudnovsky.

I'll discuss how a certain notion of symmetry captures the computational complexity of approximating homomorphism problems between relational structures, also known as constraint satisfaction problems. I'll present recent results on inapproximability of conflict-free and linearly-ordered hypergraph colourings and solvability of systems of equations.

In 1975, Bollobás, Erdős, and Szemerédi asked the following Zarankiewicz-type problem. What is the smallest $\tau$ such that an $n \times n \times n$ tripartite graph with minimum degree $n + \tau$ must contain $K_{t, t, t}$? They further conjectured that $\tau = O(n^{1/2})$ when $t = 2$.

I will discuss our proof that $\tau = O(n^{1 - 1/t})$ (confirming their conjecture) and an infinite family of extremal examples. The bound $O(n^{1 - 1/t})$ is best possible whenever the Kővári-Sós-Turán bound $\operatorname{ex}(n, K_{t, t}) = O(n^{2 - 1/t})$ is (which is widely-conjectured to be the case).

This is joint work with Francesco Di Braccio (LSE).

In a recent breakthrough Campos, Griffiths, Morris and Sahasrabudhe obtained the first exponential improvement of the upper bound on the classical Ramsey numbers since 1935. I will outline a reinterpretation of their proof, replacing the underlying book algorithm with a simple inductive statement. In particular, I will present a complete proof of an improved upper bound on the off-diagonal Ramsey numbers and describe the main steps involved in improving their upper bound for the diagonal Ramsey numbers to $R(k,k)\le(3.8)^k$ for sufficiently large $k$.

Based on joint work with Parth Gupta, Ndiame Ndiaye, and Louis Wei.

Let $(V(u))$ be a branching random walk and $(\eta(u))$ be i.i.d marks on the vertices. To each path $\xi$ of the tree, we associate the discounted sum $D(\xi)$ which is the sum of the $\exp(V(u))\eta_u$ along the path. We study conditions under which $\sup_\xi D(\xi)$ is finite, answering an open question of Aldous and Bandyopadhyay. We will see that this problem is related to the study of the local time process of the branching random walk along a path. It is a joint work with Yueyun Hu and Zhan Shi.

A zero-one matrix $M$ is said to contain another zero-one matrix $A$ if we can delete some rows and columns of $M$ and replace some 1-entries with 0-entries such that the resulting matrix is $A$. The extremal number of $A$, denoted $\operatorname{ex}(n,A)$, is the maximum number of 1-entries that an $n\times n$ zero-one matrix can have without containing $A$. The systematic study of this function for various patterns $A$ goes back to the work of Furedi and Hajnal from 1992, and the field has many connections to other areas of mathematics and theoretical computer science. The problem has been particularly extensively studied for so-called acyclic matrices, but very little is known about the general case (that is, the case where $A$ is not necessarily acyclic). We prove the first asymptotically tight general result by showing that if $A$ has at most $t$ 1-entries in every row, then $\operatorname{ex}(n,A)\leq n^{2-1/t+o(1)}$. This verifies a conjecture of Methuku and Tomon.

Our result also provides the first tight general bound for the extremal number of vertex-ordered graphs with interval chromatic number two, generalizing a celebrated result of Furedi, and Alon, Krivelevich and Sudakov about the (unordered) extremal number of bipartite graphs with maximum degree $t$ in one of the vertex classes.

Joint work with Barnabas Janzer, Van Magnan and Abhishek Methuku.

The celebrated Szemeredi-Trotter theorem states that the maximum number of incidences between $n$ points and $n$ lines in the plane is $\mathcal{O}(n^{4/3})$, which is asymptotically tight.

Solymosi conjectured that this bound drops to $o(n^{4/3})$ if we exclude subconfigurations isomorphic to any fixed point-line configuration. We describe a construction disproving this conjecture. On the other hand, we prove new upper bounds on the number of incidences for configurations that avoid certain subconfigurations. Joint work with Martin Balko.

In a graph $H$ whose edges are coloured (not necessarily properly) a rainbow copy of a graph $G$ is a (not necessarily induced) subgraph of $H$ that is isomorphic to $G$ and whose edges are all coloured differently. In this talk I will explain why the problem of finding such rainbow copies is interesting, survey what we know, concentrating mainly on the case where $G$ is a Hamilton cycle, and then tell you a bit about a new result about finding rainbow Hamilton cycles resiliently in random graphs (which is joint work with Peter Allen and Liana Yepremyan).

The classical lower-tail problem for triangles in random graphs asks the following: given $\eta\in[0,1)$, what is the probability that $G(n,p)$ contains at most $\eta$ times the expected number of triangles?  When $p=o(n^{-1/2})$ or $p = \omega(n^{-1/2})$ the asymptotics of the logarithm of this probability are known via Janson's inequality in the former case and regularity or container methods in the latter case.

We prove for the first time asymptotic formulas for the logarithm of the lower tail probability when $p=c n^{-1/2}$ for $c$ constant.  Our results apply for all $c$ when $\eta \ge 1/2$ and for $c$  small enough when $\eta < 1/2$.  For the special case $\eta=0$ of triangle-freeness, our results prove that a phase transition occurs as $c$ varies (in the sense of a non-analyticity of the rate function), while for $\eta \ge 1/2$ we prove that no phase transition occurs.

Our method involves ingredients from algorithms and statistical physics including rapid mixing of Markov chains and the cluster expansion.  We complement our asymptotic formulas with efficient algorithms to approximately sample from $G(n,p)$ conditioned on the lower tail event.

Joint work with Will Perkins, Aditya Potukuchi and Michael Simkin.

We give an exponential improvement on the upper bound for the $r$-colour diagonal Ramsey number for all $r$. The proof relies on geometric insights and offers a simplified proof in the case of $r=2$.

Joint Work with: Paul Ballister, Béla Bollobás, Marcelo Campos, Simon Griffiths, Rob Morris, Julian Sahasrabudhe and Marius Tiba.

We show that an $n$-vertex $k$-uniform hypergraph, where all $(k-1)$-subsets that are supported by an edge are in fact supported by at least $n/2+o(n)$ edges, contains a spanning $(k-1)$-dimensional sphere. This generalises Dirac's theorem, and confirms a conjecture of Georgakopoulos, Haslegrave, Montgomery, and Narayanan. Unlike typical results in the area, our proof does not rely on the absorption method or the regularity lemma. Instead, we use a recently introduced framework that is based on covering the vertex set of the host hypergraph with a family of complete blow-ups.

This is joint work with Freddie Illingworth, Richard Lang, Olaf Parczyk, and Amedeo Sgueglia.

The study of counting point-hyperplane incidences in the $d$-dimensional space was initiated in the 1990's by Chazelle and became one of the central problems in discrete geometry. It has interesting connections to many other topics, such as additive combinatorics and theoretical computer science. Assuming a standard non-degeneracy condition, i.e., that no $s$ points are contained in the intersection of $s$ hyperplanes, the currently best known upper bound on the number of incidences of $m$ points and $n$ hyperplanes in $\mathbb{R}^d$ is $O((mn)^{1-1/(d+1)}+m+n)$. This bound by Apfelbaum and Sharir is based on geometrical space partitioning techniques, which apply only over the real numbers.

In this talk, we discuss a novel combinatorial approach to study such incidence problems over arbitrary fields. Perhaps surprisingly, this approach matches the best known bounds for point-hyperplane incidences in $\mathbb{R}^d$ for many interesting values of $m, n, d$. Moreover, in finite fields our bounds are sharp as a function of $m$ and $n$ in every dimension. This approach can also be used to study point-variety incidences and unit-distance problem in finite fields, giving tight bounds for both problems under a similar non-degeneracy assumption. Joint work with A. Milojevic and I. Tomon.

An interesting twist on classical subgraph containment problems in graph theory is the following: given a graph $H$ and a collection $\{G_1, \dots , G_m\}$ of graphs on a common vertex set $[n]$, what conditions on $G_i$ guarantee a copy of $H$ using at most one edge from each $G_i$? Such a subgraph is called transversal, and the above problem is closely related to the study of temporal graphs in Network Theory. In 2020 Joos and Kim showed that if $\delta(G_i)\geq n/2$, the collection contains a transversal Hamilton cycle. We improve on their result by showing that it actually contains every transversal Hamilton cycle if $\delta(G_i)\geq (1/2+o(1))n$. That is, for every function $\chi:[n]\to[m]$, there is a Hamilton cycle whose $i$-th edge belongs to $G_{\chi(i)}$.

This is joint work with Candida Bowtell, Patrick Morris and Katherine Staden.

The organizing principle of Ramsey theory is that in large mathematical structures, there are relatively large substructures which are homogeneous. This is quantified in combinatorics by the notion of Ramsey numbers $r(s,t)$, which denote the minimum $N$ such that in any red-blue coloring of the edges of the complete graph on $N$ vertices, there exists a red complete graph on $s$ vertices or a blue complete graph on $t$ vertices.

While the study of Ramsey numbers goes back almost one hundred years, to early papers of Ramsey and Erdős and Szekeres, the long-standing conjecture of Erdős that $r(s,t)$ has order of magnitude close to $t^{s-1}$ as $t \to \infty$ remains open in general. It took roughly sixty years before the order of magnitude of $r(3,t)$ was determined by Jeong Han Kim, who showed $r(3,t)$ has order of magnitude $t^2/\log t$ as $t \to \infty$. In this talk, we discuss a variety of new techniques, including the modern method of containers, which lead to a proof of the conjecture of Erdős that $r(4,t)$ is of order close to $t^3$.

One of the salient philosophies in our approach is that good Ramsey graphs hide inside pseudorandom graphs, and the long-standing emphasis of tackling Ramsey theory from the point of view of purely random graphs is superseded by pseudorandom graphs. Via these methods, we also come close to determining the well-studied related quantities known as Erdős-Rogers functions and discuss related hypergraph coloring problems and applications.

Joint work in part with Sam Mattheus, Dhruv Mubayi and David Conlon.

Models for networks that evolve and change over time are ubiquitous in a host of domains including modeling social networks, understanding the evolution of systems in proteomics, the study of the growth and spread of epidemics etc.

This talk will give a brief summary of three recent findings in this area where stochastic approximation techniques play an important role:

1. Understanding the effect and detectability of change point in the evolution of the system dynamics.
2. Reconstructing the initial "seed" that gave rise to the current network, sometimes referred to as Network Archeology.
3. The disparity in the behavior of different centrality measures such as degree and page rank centrality for measuring popularity in settings where there are vertices of different types such as majorities and minorities as well as insight analyzing such problems give for at first sight unrelated issues such as sampling rare groups within the network.

The main goal will to be convey unexpected findings in each of these three areas and in particular the "unreasonable effectiveness" of continuous time branching processes.

Let $G$ be a $d$-regular graph of growing degree on $n$ vertices. Form a random subgraph $G_p$ of $G$ by retaining edge of $G$ independently with probability $p=p(d)$. Which conditions on $G$ suffice to observe a phase transition at $p=1/d$, similar to that in the binomial random graph $G(n,p)$, or, say, in a random subgraph of the binary hypercube $Q^d$?

We argue that in the supercritical regime $p=(1+\epsilon)/d$, $\epsilon>0$ a small constant, postulating that every vertex subset $S$ of $G$ of at most $n/2$ vertices has its edge boundary at least $C|S|$, for some large enough constant $C=C(\epsilon)>0$, suffices to guarantee likely appearance of the giant component in $G_p$. Moreover, its asymptotic order is equal to that in the random graph $G(n,(1+\epsilon)/n)$, and all other components are typically much smaller.

We also give examples demonstrating tightness of our main result in several key senses.

A joint work with Sahar Diskin, Joshua Erde and Mihyun Kang.