\(\quad\)In 1973, Brown, Erdős and Sós initiated the study of the maximum number of edges in an \(n\)-vertex \(r\)-graph such that no \(k\) edges span at most \(s\) vertices. If \(s=rk-2k+2\), then this function is quadratic in \(n\). I will present various results, joint with Stefan Glock, Felix Joos, Jaehoon Kim, Marcus Kühn, Lyuben Lichev and Shumin Sun, on this case.

\(\quad\)In this talk, we will discuss the probability of substructures occurring in uniformly random Latin squares. Our main result states that if \(P\) is a partial Latin square of order \(n\) with \(k\) non-empty cells that has \(an\) non-empty rows and \(bn\) non-empty columns where \(2a+b<1\), then the probability of a uniformly random Latin square containing \(P\) lies between \((c/n)^k\) and \((C/n)^k\) for some constants \(c\) and \(C\) which depend on \(a\) and \(b\). We apply this result to subsquares in random Latin squares to obtain the first proof of the fact that the expected number of subsquares of order \(3\) in a random Latin square of order \(n\) is non-vanishing as \(n\) grows.

\(\quad\)The random graph process on vertex set \([n]\) is a sequence of graphs \((G_0,G_1,\ldots,G_M)\), \(M=\binom{n}{2}\), all on vertex set \([n]\), where \(G_0\) is the empty graph and, for each \(i\in[M]\), an edge \(e_i\) is chosen uniformly at random from \(\binom{[n]}{2}\setminus E(G_{i-1})\) before setting \(G_i := G_{i-1}\cup\{e_i\}\). We study the budget-constrained random graph process introduced by Frieze, Krivelevich and Michaeli, where each time an edge is offered through the random graph process, we must irrevocably decide whether to "purchase" this edge or not, with our goal being to construct a graph which satisfies some property within a given time \(t\) and while purchasing at most \(b\) edges. We consider the problem of constructing graphs containing certain fixed small subgraphs.

We provide an optimal strategy for building a graph which contains a copy of \(K_4\). This resolves a problem raised by Iľkovič, León and Shu.

More generally, we obtain analogously tight results for containing a wheel of any fixed size, or a graph consisting of a tree plus one additional universal vertex.

We also tackle the problem of constructing graphs containing a copy of \(K_5\), obtaining both lower and upper bounds on the optimal budget, though a gap remains in this case.

This is a joint work with Alberto Espuny Díaz, Kalina Petrova and Miloš Stojakovič.

\(\quad\)Let \(\mathcal{F}=\{A_1,A_2,\ldots,A_k\}\) be a collection of finite arithmetic progressions, where each \(A_d\) is an initial segment of the set \(D_d=\{d,2d,3d,\ldots\}\) of consecutive multiples of a positive integer \(d\). Let \(m(\mathcal{F})\) denote the minimum length of an interval containing pairwise disjoint shifted copies of all members of the family \(\mathcal{F}\).

We study this parameter in the following two cases: for a fixed positive integer \(n\), (1) each progression in \(\mathcal{F}\) has the form \(A_d=D_d\cap\{1,2,\ldots,n\}\), and (2) all progressions \(A_d\) of \(\mathcal{F}\) have the same size \(n\), that is, \(A_d=D_d\cap\{1,2,\ldots,nd\}\). We in particular derive the following asymptotic estimates. In case (1), when \(k=n\), we get \(m(\mathcal{F})=\Theta(n^{3/2}/\ln n)\). In case (2), when \(k=n\), we get \(m(\mathcal{F})=\Theta(n^3/\ln n)\), while if \(k>k_0(n)\), then \(m(\mathcal{F})<3kn\). In both cases, we additionally determine \(m(\mathcal{F})\) asymptotically or settle its order of magnitude for all \(k<n\).

Joint work with Noga Alon, Michał Dębski, Jarosław Grytczuk.

\(\quad\)A word over an alphabet \(A\) contains a square if it has a subword of the form \(XX\) where \(X\) is a word. A word \(W\) is extremal square-free if it does not contain a square, but it contains a square as soon as any letter of \(A\) is inserted at any position of \(W\). Grytczuk, Kordulewski, and Niewiadomski conjectured that there are no extremal square-free words over alphabets of size at least \(4\). We prove this conjecture for alphabets of size at least \(5\). Our proof also implies that the sequence of nonchalant words defined by Grytczuk, Kordulewski, and Niewiadomski is infinite and converges to an infinite word for all alphabets of size at least \(5\). Joint work with Eng Keat Hng.

\(\quad\)We study biased Maker-Breaker games on a graph system \(\{G_1,G_2,\ldots,G_s\}\), in which Maker's goal is to claim certain rainbow structures, i.e., specified subgraphs consisting of at most one edge from each graph \(G_i\). We consider the rainbow-connectivity game, in which Maker wants to claim a rainbow path between every pair of vertices.

We analyse this game in detail, essentially determining the threshold bias when played on the system of complete graphs, and observing that whether the random graph intuition holds depends on the size of \(s\). The key ingredient of our result is the analysis of a Maker's strategy that combines randomized strategies with an appropriately designed balancing game. As a byproduct, we find the order of the threshold bias for the Maker-Breaker diameter game, and disprove a conjecture by Balogh, Martin and Pluhár.

This is joint work with Bruno Borchardt, Dennis Clemens, Milica Maksimović, Mirjana Mikalački, Miloš Stojaković.

\(\quad\)In many real-world problems, when making decisions we need to think about the fact that the data can be imprecise or uncertain. Such situations can be modeled using two-player games. In this talk, we present a min-max two-player game called Shortest Path under Attacks, played on a weighted graph, between two players: the Pather, whose target is to choose a path between two fixed vertices, and the Attacker, whose target is to distribute a given budget over the edges and consequently, increase the weights of some of them.

We consider the game in two variants: a pure (deterministic) one, and a mixed one, where each player wants to find an optimal probability distribution over their possible actions. We present results about the computational complexity of the problem for both players in both variants, as well as an efficient algorithm based on Mixed Integer Linear Programming and the double oracle approach.

Joint work with Armin Fügenschuh (Brandenburg University of Technology) and Konstanty Junosza-Szaniawski (Warsaw University of Technology).

\(\quad\)Following the steps of Folkman, Burr, Erdős, and Lovász (BEL) started the systematic study of extremal parameters of Ramsey graphs. We are interested in the smallest possible minimum degree in graphs that are minimal \(r\)-color Ramsey for a \(k\)-clique. In the two color case, BEL determined the quantity to be quadratic in \(k\). In this talk, we provide upper bounds that are essentially quadratic in both \(r\) and \(k\) in most of the cases when the number of colors is larger than the size of the clique. The argument relies on a semi-random semi-algebraic packing of special graphs sharing the same vertex set. Joint work with Sam Mattheus, Tibor Szabó, and Jacques Verstraete.

\(\quad\)The canonical Ramsey theorem, originating in the foundational work of Erdős and Rado, seeks to find, for a given graph \(F\), a graph \(G\) such that every colouring of the edges of \(G\) contains a canonically coloured copy of \(F\). Extending results of Nešetřil and Rödl and of Prömel and Voigt on canonical Ramsey properties for ordered graphs, we prove that for any sufficiently connected ordered graph \(F\), there exists an ordered graph \(G\) such that \(G\) has the canonical Ramsey property for \(F\) and any two copies of \(F\) in \(G\) intersect either in a single vertex, a single edge, or not at all. We refer to this condition on the copies of \(F\) as the clean intersection property. As a consequence this allows us to construct canonical Ramsey graphs \(G\) for a given ordered graph \(F\) enjoying additional structural properties. In particular, \(G\) can have the same odd girth and clique number as \(F\), and the copies of \(F\) in \(G\) are not only induced but also preserve the same distances.

\(\quad\)Maximum Weight Independent Set is one of the fundamental algorithmic problems in graph theory. We consider its complexity in the classes of ordered graphs that exclude a single ordered graph as an induced subgraph. In particular, we manage to extract significant algorithmic advantage by excluding any one of the three possible permutations of \(2K_2\), and likewise for \(P_3\) and \(K_2\). On the other hand, we obtain NP-hardness results for any meaningfully larger forbidden induced subgraph. In the end, we formulate a near-complete complexity dichotomy.

\(\quad\)Since suggested by Turán in 1941, determining the Turán density of hypergraphs has been a notoriously difficult problem at the center of extremal combinatorics. Roughly speaking, the Turán density \(\pi(F)\) of a hypergraph \(F\) is the threshold of the edge density above which large hypergraphs are guaranteed to contain a copy of \(F\). Over the past decade, some progress was made in understanding the set of all Turán densities, i.e., \(\Pi(k)=\{\pi(F): F \text{ is a } k\text{-uniform hypergraph}\}\), as well as its variants. In this talk, we discuss recent results and methods that are part of this development.

Based on several joint works with different subsets of Conlon, Lamaison, Li, Liu, Liu, King, Piga, Sales, Sun, Wang, Wu, Yang, and Zhang.

\(\quad\)The inverted Ramsey number \(R(H_1,H_2,\ldots,H_k)\) is the minimum number \(n\) such that any colouring of \(K_n\) with \(k\) colours leads to a copy of \(H_i\) which contains no edges of the \(i\)-th colour for some \(i=1,2,\ldots,k\). In the special case where \(H_1=H_2=\cdots=H_k\), we use \(R_k(H_1)\). We find the value of \(R_k(C_\ell)\), \(k\ge 3\), where \(C_\ell\) is a cycle of length \(\ell\) and \(\ell\) is large.