Schedule and Abstracts 2024/2025

If not stated otherwise, the talk will take place Wednesdays starting at 4:15pm in A3/SR 119
Date Speaker Title
10.07.2025
5:15 pm
T9, SR005 		Christoph Spiegel (ZIB) Infinitely Many Counterexamples to a Conjecture of Lovász
18.06.2025 Ander Lamaison (Daejeon University) Palettes determine uniform Turán density
12.06.2025
4:15 pm
A3, SR024 		Tibor Szabó (FU Berlin) Slow subgraph bootstrap percolation
04.06.2025 Larion Garaczi (FU Berlin) The Frankl-Pach upper bound for set systems with bounded VC-dimension is not tight
28.05.2025 César Zarco Romero (Weierstraß Institut) A large deviation principle for spatial dense random graphs
21.05.2025
4:15 pm
A14, 1.3.21 		Eva Schinzel (FU Berlin) Triangle Factors in the Semi-random Graph Process (II)
14.05.2025
2:15 pm
A14, 1.3.21 		Eva Schinzel (FU Berlin) Triangle Factors in the Semi-random Graph Process
07.05.2025 Silas Rathke (FU Berlin) Extra-tight Euler trails in hypergraphs (III)
30.04.2025 Silas Rathke (FU Berlin) Extra-tight Euler trails in hypergraphs (II)
23.04.2025
2:15 pm
A14, 1.3.48 		Silas Rathke (FU Berlin) Extra-tight Euler trails in hypergraphs
01.04.2025
4:15 pm
A6 SR007/008 		Peter Martin (FU Berlin) An exponential improvement of the Ramsey number (part II)
19.03.2025 Pascal Weinhart (FU Berlin) Embedding Spanning Trees in \((n,d,\lambda)\)-graphs via Sorting Networks
27.02.2025
12:15 pm
A6 SR007/008 		Peter Martin (FU Berlin) An exponential improvement of the Ramsey number
29.01.2025 Richard Lang (Polytechnic University of Catalonia) Simultaneous edge-colourings
22.01.2025
10:15 am
A3/SR024 		Jack Allsop (Monash University) Subsquares of Latin squares
16.01.2025 Dingding Dong (Harvard University) Uncommon linear systems of two equations
09.01.2025 Mehmet Akif Yildiz (University of Amsterdam) Path decompositions of oriented graphs
18.12.2024 Christoph Spiegel (Zuse-Institut Berlin) Coloring the plane with neural networks
04.12.2024 Milos Stojakovic (University of Novi Sad) Maker-Breaker games on random boards
28.11.2024 Christoph Spiegel (Zuse-Institut Berlin) An Unsure Talk on an Un-Schur Problem
14/21.11.2024 Aldo Kiem (Zuse-Institut Berlin) Forcing Graphs and Graph Algebra Operators
21.10.2024 Victor Falgas-Ravry (Umea University) 1-independent percolation on high dimensional lattices
17.10.2024 Joseph Fehribach (Worcester Polytechnic Institute) Families of Kirchhoff Graphs

Abstracts

10.07.2025
Christoph Spiegel (ZIB)
Infinitely Many Counterexamples to a Conjecture of Lovász
Abstract: Motivated by the well-known conjecture of Ryser which relates maximum matchings to minimum vertex covers in \(r\)-partite \(r\)-uniform hypergraphs, Lovász formulated a stronger conjecture. It states that one can always reduce the matching number by removing \(r-1\) vertices. This conjecture was very recently disproven for \(r=3\) by Clow, Haxell, and Mohar using the line graph of a \(3\)-regular graph of order \(102\). Building on this, we describe a simple infinite family of counterexamples based on generalized Petersen graphs for the case \(r=3\) and give specific counterexamples for \(r=4\). This is joint work with Aida Abiad, Frederik Garbe, and Xavier Povill.
18.06.2025
Ander Lamaison (Daejeon University)
Palettes determine uniform Turán density
Abstract: We study Turán problems for hypergraphs with an additional uniformity condition on the edge distribution. This kind of Turán problems was introduced by Erdős and Sós in the 1980s but it took more than 30 years until the first non-trivial exact results were obtained. Central to the study of the uniform Turán density of hypergraphs are palette constructions, which were implicitly introduced by Rödl in the 1980s. We prove that palette constructions always yield tight lower bounds, unconditionally confirming present empirical evidence. This results in new and simpler approaches to determining uniform turán densities, which completely bypass the use of the hypergraph regularity method.
12.06.2025
Tibor Szabó (FU Berlin)
Slow subgraph bootstrap percolation
Abstract: Given a graph \(H\), the \(H\)-bootstrap percolation process on graph \(G\) is a finite time deterministic process that at every time
step adds any edge missing on \(V(G)\) that completes a copy of \(H\). We are interested in the extremal question raised by Bollobás, of determining the maximum
number of time steps when this process stabilizes, over all possible choices of \(n\)-vertex starting graph \(G\). We initiate a systematic study of this parameter, denoted \(M_H(n)\), and its dependence on properties of the graph \(H\). In a series of works we determine the precise running time for cycles and asymptotic running time for several
other important classes. In general, we study necessary and sufficient conditions on \(H\) for fast, i.e. sublinear or linear \(H\)-bootstrap
percolation, and in particular explore the relationship between running time and minimum vertex degree and connectivity. Furthermore we also
obtain the running time of the process for typical \(H\) and discover several graphs exhibiting surprising behavior. The talk represents joint
work with David Fabian and Patrick Morris.
04.06.2025
Larion Garaczi (FU Berlin)
The Frankl-Pach upper bound for set systems with bounded VC-dimension is not tight
Abstract: The Vapnik–Chervonenkis (VC) dimension of a set system \(\mathcal{F} \subset 2^{[n]}\) is the largest integer \(k\), for which there is an \(S \subset [n]\) of size k, with the property that for every \(S' \subset S\) there is an \(F \in \mathcal{F}\) such that \(F \cap S = S'\) (in such a case we say the set \(S\) is \emph{shattered} by the set system \(\mathcal{F}\)). This concept is used in statistics (as a measure of complexity), machine learning, model theory and combinatorics, where it was mainly studied due to its connection to the Erdős-Ko-Radó theorem.

We will consider the following extremal question, which is still open. What is the maximum size of a \(d+1\)-uniform set system on \([n]\) of VC-dimension \(\le d\)? The best known lower bound is \({n-1 \choose d} + {n-4 \choose d-2}\), due to Ahlswede and Khachatrian (1997). On the other hand in 1984 Frankl and Pach provided the upper bound \({n \choose d}\) using a very elegant proof using the linear algebra method. But the main term in the gap between the lower and upper bounds stayed the same until this January. In December 2024 the Frankl-Pach bound was shown not to be tight for all \(d \ge 2\) and \(n \ge 2d + 2\) in a paper by Ge et al. (arXiv:2412.11901), which utilizes the polynomial method. Building upon this an overlapping set of authors improved the upper bound significantly, removing the main term in the gap between the best upper and lower bounds (arXiv:2501.13850). In this talk I will present the first of these papers, which is the main focus of my Bachelor thesis.
28.05.2025
César Zarco Romero (Weierstraß Institut)
A large deviation principle for spatial dense random graphs
Abstract: We present the large deviation approach to analyse the rare behaviour of a sequence of dense random graphs, applying the theory of graph limits and Szemerédi's regularity lemma.

We adapt the so-called cut metric to account for vertex positions and aim to extend previous results to spatially embedded graphs in a metric space, in a direction similar to that of Bollobás et al. (2005).

Our work builds on the large deviation principle for the Erdős–Rényi random graph, established by Chatterjee and Varadhan (2011).

This talk is based on ongoing work with Wolfgang König
21.05.2025
Eva Schinzel (FU Berlin)
Triangle Factors in the Semi-random Graph Process (II)
Abstract: The semi-random graph process is an enticing new single player game which starts with an empty graph on \(n\) vertices and then in each round adds an edge \(uv\) in the following way: The first endpoint \(u\) is offered to the player independently and uniformly at random. The second endpoint \(v\) is selected by the player according to some strategy. The goal is to arrive in as few rounds as possible at a graph that w.h.p. satisfies some increasing graph property. Properties studied so far include the containment of a Hamiltonian cycle or a perfect matching. In our talk, we will add a new puzzle piece to this research by presenting a strategy that w.h.p. creates a triangle factor in at most \(2.843971\cdot n\) rounds. The main tool used in the analysis of our strategy will be the differential equation method.

Joint work with Olaf Parczyk.
14.05.2025
Eva Schinzel (FU Berlin)
Triangle Factors in the Semi-random Graph Process
Abstract: The semi-random graph process is an enticing new single player game which starts with an empty graph on \(n\) vertices and then in each round adds an edge \(uv\) in the following way: The first endpoint \(u\) is offered to the player independently and uniformly at random. The second endpoint \(v\) is selected by the player according to some strategy. The goal is to arrive in as few rounds as possible at a graph that w.h.p. satisfies some increasing graph property. Properties studied so far include the containment of a Hamiltonian cycle or a perfect matching. In our talk, we will add a new puzzle piece to this research by presenting a strategy that w.h.p. creates a triangle factor in at most \(2.843971 \cdot n\) rounds. The main tool used in the analysis of our strategy will be the differential equation method.

Joint work with Olaf Parczyk.
07.05.2025
Silas Rathke (FU Berlin)
Extra-tight Euler trails in hypergraphs (III)
Abstract: Last time, we saw the proof of the Absorbing Lemma up to constructing an \(E_1\)-\(E_2\)-switcher. This time, we will construct such a switcher using the same design result we saw last week. Afterwards, we will see an overview of the proof of the Cover Down Lemma.
30.04.2025
Silas Rathke (FU Berlin)
Extra-tight Euler trails in hypergraphs (II)
Abstract: This time, we will look at the Absorbing Lemma which we used last time to prove the main theorem. The proof of the Absorbing Lemma uses some results from design theory which we will apply on some carefully chosen graphs. That way, we will build some "switchers" which will make up our absorber. This is still a joint work with Stefan Glock, Olaf Parczyk, and Tibor Szabó.
23.04.2025
Silas Rathke (FU Berlin)
Extra-tight Euler trails in hypergraphs
Abstract: An extra-tight trail in a hypergraph is like a normal tight trail in a hypergraph, but where you also consider the edges that "skip" exactly one vertex of the trail. We will consider the question which hypergraphs contain extra-tight Euler trails. We will show that large graphs with high minimum degree always have an extra-tight Euler trail if certain "trivial" degree divisibility constraints are satisfied. The proof uses the technique of absorption. Joint work with Stefan Glock, Olaf Parczyk, and Tibor Szabó
01.04.2025
Peter Martin (FU Berlin)
An exponential improvement of the Ramsey number (part II)
Abstract: In this talk, we will explore a paper from 2024 by Gupta, Ndiaye, Norin and Wei (GNNW) in which they prove \(R(k)\leq3.8^{k+o(k)}\). This further improves the breakthrough result of Campos, Griffiths, Morris and Sahasrabudhe (CGMS) from 2023. The CGMS paper is the first exponential improvement of \(R(k)\leq\frac{1}{\sqrt k}4^k\) (which was famously proven by Erdős and Szekeres in 1935). They introduce the so-called \textit{book algorithm} to achieve this. GNNW managed to reformulate this proof as an induction, in a simpler way.
19.03.2025
Pascal Weinhart (FU Berlin)
Embedding Spanning Trees in \((n,d,\lambda)\)-graphs via Sorting Networks
Abstract: My bachelor thesis analyses the paper by Joseph Hyde, Natasha Morrison, Alp Müyesser and Matías Pavez-Signé (arXiv:2311.03185v1). The aim is to find arbitrary spanning trees in pseudorandom graphs. This is done by first identifying a large number of long paths within the tree, then embedding the remaining vertices of the tree, then using perfect matchings to embed large parts of the paths and finally using a sorting network to connect the correct ends of the paths. The focus is on the extendability technique, construction of a sorting network and embedding trees.
27.02.2025
Peter Martin (FU Berlin)
An exponential improvement of the Ramsey number
Abstract: In this talk, we will explore a paper from 2024 by Gupta, Ndiaye, Norin and Wei (GNNW) in which they prove \(R(k)\leq3.8^{k+o(k)}\). This further improves the breakthrough result of Campos, Griffiths, Morris and Sahasrabudhe (CGMS) from 2023. The CGMS paper is the first exponential improvement of \(R(k)\leq\frac{1}{\sqrt k}4^k\) (which was famously proven by Erdős and Szekeres in 1935). They introduce the so-called book algorithm to achieve this. GNNW managed to reformulate this proof as an induction, in a simpler way.
29.01.2025
Richard Lang (Polytechnic University of Catalonia)
Simultaneous edge-colourings
Abstract: A classic result of Vizing tells us the number of colours required for a proper edge-colouring of a graph. More recently, a related problem has been proposed, where the goal is to simultaneously colour the edges of multiple graphs. In this talk, I will give an introduction to the general topic and then present some new bounds for simultaneous edge-colourings.

Based on joint work with Simona Boyadzhiyska, Allan Lo and Michael Molloy.
22.01.2025
Jack Allsop (Monash University)
Subsquares of 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 of a Latin square is a submatrix which is itself a Latin square. Any Latin square of order \(n\) has \(n^2\) subsquares of order \(1\) and a single subsquare of order \(n\). Any other subsquare is called proper. In this talk we discuss a number of problems regarding subsquares. Given integers \(n\) and \(m\), what is the maximum number of subsquares of order \(m\) in a Latin square of order \(n\)? What is the expected number of subsquares of order \(m\) in a uniformly random Latin square of order \(n\)? For what orders do there exist Latin squares without any proper subsquares?
16.01.2025
Dingding Dong (Harvard University)
Uncommon linear systems of two equations
Abstract: A system of linear equations \(L\) is common over \(F_p\) if any 2-coloring of \(F_p^n\) gives at least as many monochromatic solutions to it as a random 2-coloring, asymptotically as \(n\to\infty\). It is an open question which linear systems are common. When \(L\) is a single equation, Fox, Pham and Zhao gave a complete characterization of common linear equations. When \(L\) consists of two equations, Kamčev, Liebenau and Morrison showed that all irredundant 2*4 linear systems are uncommon. In joint work with Anqi Li and Yufei Zhao, we: (1) determine commonness of all 2*5 linear systems up to a small number of cases; (2) show that all \(2*k\) linear systems with \(k\) even and girth (length of the shortest equation) \(k-1\) are uncommon, answering a question of Kamčev-Liebenau-Morrison.
09.01.2025
Mehmet Akif Yildiz (University of Amsterdam)
Path decompositions of oriented graphs
Abstract: We consider the problem of decomposing the edges of a directed graph into as few paths as possible. There is a natural lower bound for the number of paths in any path decomposition dictated by vertex degree imbalances, and any directed graph that meets this bound is called consistent.
In 1976, Alspach, Mason, and Pullman conjectured that (as a generalization of Kelly's conjecture on Hamilton decompositions of regular tournaments) every tournament of even order is consistent. This conjecture was recently verified for large tournaments by Girão, Granet, Kühn, Lo, and Osthus. A stronger conjecture, proposed by Pullman in 1980, states that every orientation of every regular graph with odd degree is consistent.
In this talk, I will present our recent work (joint with Viresh Patel) that establishes Pullman’s conjecture for random regular graphs and regular graphs without short cycles.
18.12.2024
Christoph Spiegel (Zuse-Institut Berlin)
Coloring the plane with neural networks
Abstract: We present two novel six-colorings of the Euclidean plane that avoid monochromatic pairs of points at unit distance in five colors and monochromatic pairs at another specified distance din the sixth color. Such colorings have previously been known to exist for \(0.41 < \sqrt 2−1 \le d \le 1/\sqrt 5 < 0.45\). Our results significantly expand that range to \(0.354 \le d \le0.657\), the first improvement in 30 years. The constructions underlying this notably were derived by formalizing colorings suggested by a custom machine learning approach. This is joint work with Sebastian Pokutta, Konrad Mundiger, and Max Zimmer.
04.12.2024
Milos Stojakovic (University of Novi Sad)
Maker-Breaker games on random boards
Abstract: In Maker-Breaker games played on edge sets of graphs, two players, Maker and Breaker, alternately claim unclaimed edges of a given graph until all of its edges are claimed. Maker wins the game if he claims all edges of one representative of a prescribed graph-theoretic structure (e.g. a Hamiltonian cycle, or a fixed graph \(H\)). Breaker wins otherwise.
We take a closer look at various Maker-Breaker games played on the edge sets of random graphs.
28.11.2024
Christoph Spiegel (Zuse-Institut Berlin)
An Unsure Talk on an Un-Schur Problem
Abstract: Graham, Rödl, and Ruciński originally posed the problem of determining the minimum number of monochromatic Schur triples that must appear in any 2-coloring of the first \(n\) integers. This question was subsequently resolved independently by Datskovsky, Schoen, and Robertson and Zeilberger. In this talk we will study a natural anti-Ramsey variant of this question and establish the first non-trivial bounds by proving that the maximum fraction of Schur triples that can be rainbow in a given \(3\)-coloring of the first \(n\) integers is at least \(0.4\) and at most \(0.66656\). We conjecture the lower bound to be tight. This question is also motivated by a famous analogous problem in graph theory due to Erdős and Sós regarding the maximum number of rainbow triangles in any \(3\)-coloring of \(K_n\), which was settled by Balogh et al. The contents of this talk are joint work with Olaf Parczyk.
14/21.11.2024
Aldo Kiem (Zuse-Institut Berlin)
Forcing Graphs and Graph Algebra Operators
Abstract: We report on recent progress on Sidorenko's conjecture and the forcing conjecture. Our main observation is that graph operators such as subdivisions, blow-ups or adding disjoint vertices correspond to order-preserving operators on Graph Algebras. This way we easily obtain some new results, in particular that the proper balanced blow-ups of Sidorenko graphs are forcing. This is joint work with Olaf Parczyk and Christoph Spiegel. The talk will survey our results and assume no prerequisites with graph algebras and categories.
21.10.2024
Victor Falgas-Ravry (Umea University)
1-independent percolation on high dimensional lattices
Abstract: The celebrated Harris-Kesten theorem states that if each edge of the square integer lattice is open with probability \(p\), independently of all other edges, then for \(p\) at most \(1/2\) almost surely all connected components of open edges are finite, while if \(p>1/2\) almost surely there exists a unique infinite connected component of open edges.
What if one allows the state of an edge (open or closed) to depend on that of neighbouring edges? Could one use such local dependencies to delay the emergence of an infinite component? Such questions lead to fascinating problems at the interface between extremal combinatorics and percolation theory. In this talk, I will present recent work related to one such decade-old and still open problem of Balister and Bollobás on 1-independent percolation on high-dimensional integer lattices.
Joint work with Vincent Pfenninger (TU Graz)
17.10.2024
Joseph Fehribach (Worcester Polytechnic Institute)
Families of Kirchhoff Graphs
Abstract: Given a set of \(n\) vectors in any vector space over the rationals, suppose that \(k<n\) are linear independent. Kirchhoff graphs are vector graphs (graphs whose edges are these vectors), whose cycles represent the dependencies of these vectors and whose vertex cuts are orthogonal to these cycles. This presentation discusses the uniformity of vector 2-connected Kirchhoff graphs, and how graph tiling can generate families of Kirchhoff graphs. These families are composed of prime graphs (those having no Kirchhoff subgraphs), and composite graphs (not prime), all generated by a set of fundamental Kirchhoff graphs (smallest prime Kirchhoff graphs that can generate other prime and composite graphs for our set of vectors).

Links

Archives