A classical problem in combinatorial geometry, posed by Erdős in 1946, asks to determine the maximum number of unit segments in a set of $n$ points in the plane. Since then a great variety of extremal problems in finite planar point sets have been studied. Here, we look at such questions concerning triangles. Among others we answer the following question asked by Erdős and Purdy almost 50 years ago: Given $n$ points in the plane, how many triangles can be approximate congruent to equilateral triangles? For our proofs we use hypergraph Turán theory. This is joint work with Balogh and Dumitrescu.

This talk will first introduce combinatorics on permutations and patterns, presenting the basic notions and some fundamental results: the Marcus-Tardos theorem which bounds the density of matrices avoiding a given pattern, and the Guillemot-Marx algorithm for pattern detection using the notion now known as twin-width. I will then present a decomposition result: permutations avoiding a pattern factor into bounded products of separable permutations. This can be rephrased in terms of twin-width: permutation with bounded twin-width are build from a bounded product of permutations of twin-width 0. Comparable results on graph encodings follow from this factorisation. This is joint work with Édouard Bonnet, Romain Bourneuf, and Stéphan Thomassé.

In general, random walks on fractal graphs are expected to exhibit anomalous behaviors, for example heat kernel is significantly different from that in the case of lattices. Alexander and Orbach in 1982 conjectured that random walks on critical percolation, a prominent example of fractal graphs, exhibit mean field behavior; for instance, its spectral dimension is 4/3. In this talk, I will talk about this conjecture for a canonical dependent percolation model.

Rödl and Ruciński established Ramsey’s theorem for random graphs. In particular, for fixed integers $r$, $\ell\geq 2$ they showed that $n^{-\frac{2}{\ell+1}}$ is a threshold for the Ramsey property that every $r$-colouring of the edges of the binomial random graph $G(n,p)$ yields a monochromatic copy of $K_\ell$. We investigate how this result extends to arbitrary colourings of $G(n,p)$ with an unbounded number of colours. In this situation Erdős and Rado showed that canonically coloured copies of $K_\ell$ can be ensured in the deterministic setting. We transfer the Erdős-Rado theorem to the random environment and show that for $\ell\geq 4$ both thresholds coincide. As a consequence the proof yields $K_{\ell+1}$-free graphs $G$ for which every edge colouring yields a canonically coloured $K_\ell$. This is joint work with Nina Kamčev.

We say that a 0-1 matrix A contains another such matrix (pattern) P if P can be obtained from a submatrix of A by possibly changing a few 1 entries to 0. The main question of this theory is to estimate the maximal number of 1 entries in an n by n 0-1 matrix NOT containing a given pattern P. This question has very close connections to Turan type extremal graph theory and also to the Devenport-Schinzel theory of sequences. Results in the extremal theory of 0-1 matrices proved useful in attacking problems in far away fields as combinatorial geometry and the analysis of algorithms. This talk will concentrate on acyclic patterns and survey some old and recent results in the area and will also contain several open problems.

We prove the following variant of Helly’s classical theorem for Hamming balls with a bounded radius. For $n > t$ and any (finite or infinite) set $X$, if in a family of Hamming balls of radius $t$ in $X$, every subfamily of at most $2^{t+1}$ balls have a common point, so do all members of the family. This is tight for all $|X| > 1$ and all $n > t$. The proof of the main result is based on a novel variant of the so-called dimension argument, which allows one to prove upper bounds that do not depend on the dimension of the ambient space. We also discuss several related questions and connections to problems and results in extremal finite set theory and graph theory. This is joint work with N. Alon and B. Sudakov.

An edge-colored graph $H$ is called rainbow if all of its edges are given distinct colors.  An edge-colored graph $G$ is then called rainbow $H$-free when no copy of $H$ in $G$ is rainbow.  With this, we define a graph $G$ to be rainbow $H$-saturated when there is some proper edge-coloring of $G$ which is rainbow $H$-free, but for every pair of non-adjacent vertices $x,y\in V(G)$, the graph $G+xy$ formed by adding the edge $xy$ to $G$ cannot be given a rainbow $H$-free coloring.  We think of these graphs as edge-maximal rainbow $H$-free graphs.  (We note that here we make no restrictions on the colorings of $G+xy$ whatsoever, except that they are proper colorings.  They may use any number of colors, and need not be extensions of the original rainbow $H$-free coloring of $G$.) With this framework in place, we define the rainbow saturation number and rainbow extremal number to be the largest and smallest number of edges, respectively, among all $n$ vertex rainbow $H$-saturated graphs.  The latter of these was defined by Keevash, Mubayi, Sudakov, and Verstraëte in 2007; the former was introduced by B., Johnston, and Rombach in 2019.  In this talk, we discuss recent progress on both the rainbow saturation numbers and rainbow extremal numbers.  We also give several broad generalizations of these concepts and discuss many open problems.  This talk contains joint work with Vic Bednar (Furman), Dan Johnston (Trinity College, CT), and Puck Rombach (Vermont).

In 1980, Burr conjectured that every directed graph with chromatic number $2k-2$ contains any oriented tree of order $k$ as a subdigraph. Burr showed that chromatic number $(k-1)^2$ suffices, which was improved in 2013 to $\frac{k^2}{2} – \frac{k}{2} + 1$ by Addario-Berry et al. In this talk, we give the first subquadratic bound for Burr’s conjecture, by showing that every directed graph with chromatic number $8\sqrt{\frac{2}{15}} k \sqrt{k} + O(k)$ contains any oriented tree of order $k$. Moreover, we provide improved bounds of $\sqrt{\frac{4}{3}} k \sqrt{k}+O(k)$ for arborescences, and $(b-1)(k-3)+3$ for paths on $b$ blocks, with $b\ge 2$.