Joint FU Berlin-UPC Workshop on Extremal and Probabilistic Combinatorics

Webpage of the 1-day joint workshop between the Freie Universität Berlin and Universitat Politècnica de Catalunya, held on 10th December 2025 at UPC, in the context of the bilateral project PCI2024-155080-2: SRC-ExCo- Structure, Randomness and Computational Methods in Extremal Combinatorics

10 December 2025, Campus Nord, Barcelona, Catalunya

Joint workshop organised by the research group GAPCOMB at UPC and the Combinatorics and Graph Theory group at FU Berlin.

Local Organising Committee (UPC):

Simeon Ball, Richard Lang, Patrick Morris, Tássio Naia, Guillem Perarnau, Juanjo Rué (chair), Lluis Vena.

Location: C3-005 room, Campus Nord, Barcelona, Catalunya.

Registration: Registration mandatory via the following form (Deadline 01/12/25). Coffee breaks and lunch are provided by the organisation.

Schedule: Tentative

10:30:11:15 - Simon Griffiths
11:15-11:45 - Coffee break
11:45-12:30 - Zhuo Wu
12:30-14:15 - lunch
14:15-15:00 - Alberto Espuny
15:00-15:45 - problem session
15:45-16:15 - Coffee break
16:15-17:00 - Jack Allsop

Speakers:

Speaker: Jack Allsop (FU Berlin)

Title: Subsquares in random Latin squares

Abstract: A Latin square of order $n$ is an $n \times n$ matrix of $n$ symbols, each of which occurs exactly once in each row and column. A subsquare is a submatrix of a Latin square that is itself a Latin square. Much is known about subsquares of order $2$ in random Latin squares, but far less is known about subsquares of order $3$ or more. In this talk, we prove that the probability that a random Latin square of order $n$ contains a subsquare of order $4$ or more tends to $0$ as $n$ tends to infinity, resolving a 1999 conjecture of McKay and Wanless. We also prove that the expected number of subsquares of order $3$ is bounded.

Speaker: Alberto Espuny (UB)

Title: Counting Euler tours in dense hypergraphs

Abstract: A graph is Eulerian if one can find a walk which traverses every edge of the graph exactly once and finishes at the starting point. The problem of whether a graph is Eulerian is one of the classical problems in graph theory, with a simple well-known solution: a graph is Eulerian if and only if it is connected and the degrees of all its vertices are even. Given this simple solution, there has been much work into understanding different properties of Eulerian graphs, and also into counting the number of different Euler tours in a given graph. The counting problem even has a simple, explicit solution for directed graphs.

In contrast, the question of whether a given $r$-uniform hypergraph contains a (tight) Euler tour is much harder to solve, and indeed, even the answer for whether the complete $r$-uniform hypergraph is Eulerian was open until quite recently. Since then, a few papers have appeared providing proofs of existence of Euler tours for different dense hypergraphs. In this talk, I will present these developments, giving some of the ideas of their proofs, and present a common gneralisation where we obtain a counting result for the number of distinct Euler tours in hypergraphs, obtaining a lower bound which is essentially tight for some hypergraphs.

This talk is based on joint work with Felix Joos and Jonathan Schrodt.

Speaker: Simon Griffiths (PUC-Rio)

Title: Giant components in directed graphs

Abstract: A seminal work of Molloy and Reed in 1995 established a natural sufficient condition for the existence of a giant component in a random graph with a given degree sequence. That condition:
$$\sum_{v} d_v(d_v-2) \ge \eps e(G)$$
corresponds to the supercriticality of a certain related branching process. That said, a number of technical conditions were also imposed on the degree sequence, and these conditions were subsequently weakened by Janson and Luczak and further by Bollobás and Riordan. A true, necessary and sufficient condition for essentially all feasible degree sequences was obtained only in the last decade by Joos, Perarnau, Rautenbach and Reed. They gave an alternative condition, based on the sum of degrees of vertices which come \emph{after} the moment of criticality. In a parallel history, in 2004 Cooper and Frieze explored similar results for digraphs with a fixed degree sequence. Their technical conditions were subsequently weakened by Graf and Cai and Perarnau. We discuss the significant new challenges for the digraph case and progress towards a true necessary and sufficient condition in this context.

Speaker: Zhou Wu (UPC-FU Berlin)

Title: About uniform Turán density

Abstract: The concept of Turán density has been a central topic in extremal combinatorics. To strengthen its structural guarantees, the notion of uniform Turán density was introduced, requiring density conditions to hold across all large subsets of vertices. Recently, Ander Lamaison proposed a palette-based framework that establishes deep connections between Turán density and uniform Turán density, resolving several long-standing problems. In this talk, we will introduce the development of uniform Turán density, survey key techniques in the area, and present some recent results from my own work. These include determining the uniform Turán density of stars, exploring the relationship between Turán density and uniform Turán density, and proving the existence of infinitely many accumulation points.

Participants:

Albert Atserias, Yamaan Attwa, Ilario Bonacina, Richard Coll Josifov, de Panafieu Élie, Alberto Espuny Díaz, Víctor Franco-Sánchez, Simon Griffiths, Georgios Nikolaos Karelas, Richard Lang, Roger Lidón, Darío Martínez Ramírez, Felix Moreno Peñarrubia, Patrick Morris, Tássio Naia, Marc Noy, Guillem Perarnau, Aneta Pokorná, Xavier Povill, Silas Rathke, Clément Requilé, Juanjo Rue, Oriol Serra, Rodrigo Silveira, Robin Simoens, Lluis Vena, Zhuo Wu.

The event is sponsored by the grant PCI2024-155080-2: SRC-ExCo- Structure, Randomness and Computational Methods in Extremal Combinatorics, by the Department of Mathematics at UPC, and by the grant AGRUPS-2024 of UPC.