Berlin-Poznań-Hamburg-Warsaw Seminar in Discrete Mathematics 2025
May 16-17, 2025
Faculty of Mathematics and Information Science, Warsaw University of Technology
The seminar has a long-standing tradition. It was initiated in the mid-1990s by Prof. Michał Karoński from Adam Mickiewicz University in Poznań and Prof. Hans Jürgen Prömel, then at Humboldt University in Berlin. The seminar covers a broad range of topics in extremal and probabilistic combinatorics, algorithmic discrete mathematics, and related fields. Its location alternates between Berlin, Poznań, Hamburg, and Warsaw. This year, the event will take place on May 16–17 at the Warsaw University of Technology.
Locations
Seminar Location
Faculty of Mathematics and Information Science (Room 103), Warsaw University of Technology, Koszykowa 75, Warsaw
Dinner Location
Genatsvale Georgian Restaurant, Plac Konstytucji 1, Warsaw
Hotel
Hotel MDM, Plac Konstytucji 1, Warsaw
Programme
Friday, 16.05
Saturday, 17.05
Abstracts
| 16.05.2025 |
Alexander Allin |
TU Hamburg |
| Randomly perturbing graphs with a given degree sequence: Hamiltonicity and pancyclicity |
| \(\quad\)We consider Hamilton cycles in randomly perturbed graphs, that is, graphs obtained as the union of a deterministic graph \(H\) and a random graph. For this random perturbation we consider both the binomial random graph \(G(n,p)\) and the geometric random graph \(G(n,r)\).
While most research into randomly perturbed graphs assumes a minimum degree condition on \(H\), here we consider other conditions on its degree sequence.
Under the assumption of a degree sequence of \(H\) that is comparable with the classical condition of Posa (dependent on a parameter \(\alpha\) analogous to the minimum degree condition in typical results in the area), we prove that there exists some constant \(C=C(\alpha)\) such that taking \(p=C/n\) suffices to obtain a.a.s. a Hamilton cycle in \(H\cup G(n,p)\). Under the same conditions on \(H\) we further prove that there is a constant \(K=K(\alpha)\) such that \(r=\sqrt{K/n}\) ensures a.a.s. that \(H\cup G(n,r)\) is Hamiltonian.
Our results are best possible both in terms of the degree sequence condition and the asymptotic value of \(p\) and \(r\), and extend the known results about Hamiltonicity in randomly perturbed graphs.
This is joint work with Alberto Espuny Díaz. |
| 16.05.2025 |
Bartłomiej Bosek |
JU |
| Alon-Tarsi for hypergraphs |
| \(\quad\)Given a hypergraph \(H=(V,E)\), define for every edge \(e\in E\) a linear expression with arguments corresponding with the vertices. Next, let the polynomial \(p_H\) be the product of such linear expressions for all edges. Our main goal was to find a relationship between the Alon--Tarsi number of \)p_H\) and the edge density of \(H\). We prove that \(AT(p_H)=\lceil ed(H)\rceil+1\) if all the coefficients in \(p_H\) are equal to \(1\). Our main result is that, no matter what those coefficients are, they can be permuted within the edges so that for the resulting polynomial \(p_H^\prime\), \(AT(p_H^\prime)\leq 2\lceil ed(H)\rceil+1\) holds. We conjecture that, in fact, permuting the coefficients is not necessary. If this were true, then in particular a significant generalization of the famous 1-2-3 Conjecture would follow. This is a joint work with Marcin Anholcer, Grzegorz Gutowski, Michał Lasoń, Jakub Przybyło, Oriol Serra, Michał Tuczyński, Lluis Vena, Mariusz Zając. |
| 17.05.2025 |
Matías Azócar Carvajal |
UH |
| Canonical Ramsey numbers for partite hypergraphs |
| \(\quad\)Ramsey theory is an area of study in combinatorics which can be briefly summarized as “large enough structures, now matter how chaotic, will always contain an organized substructure“. The cornerstone of the area is Ramsey’s theorem, which states that for sufficiently large n, any r-colouring of the edges of the complete k-uniform hypergraph on n vertices contains a monochromatic copy of the complete k-uniform hypergraph on t vertices.
\(\quad\)Erdős and Rado thought about extending this result to an unbounded number of colours. They characterised all canonical colour patterns that are unavoidable in edge colourings of sufficiently large complete hypergraphs. We consider quantitative aspects of this result. For Erdős and Rado's theorem, both the lower and upper bound on n grow as (k-1)-times iterated exponentials polynomials of t.
\(\quad\)We show that for k-partite k-uniform hypergraphs the upper bound on n grows single exponentially.
This is joint work with Giovanne Santos and Mathias Schacht. |
| 16.05.2025 |
Jarosław Grytczuk |
WUT |
| The magic of rhythm |
| \(\quad\)I will present several problems and results concerning the phenomenon of repetition in combinatorial structures. The starting point of our expedition will be the well-known theorem of Thue on sequences without repetition. Where we will sail, what we will see along the way, it is difficult to predict... |
| 16.05.2025 |
Konstanty Junosza-Szaniawski |
WUT |
| Coloring mixed graphs |
| \(\quad\)A mixed graph is defined as a triple (V, E, A), where V is the set of vertices, E is the set of undirected edges, and A is the set of directed edges (arcs). A proper coloring of a mixed graph is an assignment of positive integers to the vertices such that adjacent vertices connected by an undirected edge receive distinct numbers (colors), and for every directed edge (u,v)∈A, the color assigned to vertex v (the head) is strictly greater than that assigned to u (the tail).
\(\quad\)In this talk, we present two algorithms for computing the minimal number of colors required to properly color a mixed graph. We further analyze the computational complexity of these algorithms, revealing connections to some interesting problems in extremal graph theory. |
| 17.05.2025 |
Tomasz Kościuszko |
AMU |
| Schur-like numbers and a lemma of Shearer |
| \(\quad\)Suppose that each number \(1,2,\cdots, N\) has one of \(n\) colours assigned. We show that if there are no monochromatic solutions to the equation \(x_1+x_2+x_3=y_1+y_2\), then \(N=O(\sqrt{n!})\), improving upon a result of Cwalina and Schoen. Further, a stronger bound of \(N=O(\sqrt{(n-k)!})\), where \(k\gg\frac{\log n}{\log\log n}\) is shown for colourings avoiding solutions to the equation \(x_1+x_2+\cdots+x_{60}=y_1+y_2+\cdots+y_{45}\). |
| 16.05.2025 |
Tomasz Krawczyk |
WUT |
| An Approach to Characterizing Minimal Non-Circular-Arc Graphs |
| \(\quad\)One of the main problems on a hereditary class of graphs is to characterize all minimal graphs that are not in this class (as induced subgraphs). For some well-known intersection graph classes (interval graphs, permutation graphs, function graphs, or chordal graphs) the list of all minimal forbidden graphs has been compiled, but for some (circular-arc graphs, circle graphs) it is still unknown.
\(\quad\)In my talk I will present a method that allows us to identify all minimal graphs that are not circular-arc graphs within the class of chordal graphs. Surprisingly, such graphs turn out to have very simple structures: all the nontrivial ones belong to a single family.
I will also discuss the recent progress and the obstacles that must be overcome to obtain a complete list of minimal non circular-arc graphs.\(\quad\) |
| 16.05.2025 |
Jakub Przybyło |
AGH |
| Unified approach to majority colourings |
| \(\quad\)A majority coloring of a directed graph, first studied by Kreutzer, Oum, Seymour, van der Zypen, and Wood, is a vertex coloring in which each vertex has the same color as at most half of its out-neighbors. It is conjectured that every directed graph is majority 3-colorable. Within the talk we shall discuss a few known results concerning this and related concepts, and present how to simplify some proof techniques and generalize previously known results on various generalizations of majority coloring. In particular, our unified and simplified approach works for paintability – an on-line analog of the list coloring. |
| 16.05.2025 |
Silas Rathke |
FU Berlin |
| The maximum diameter of \(d\)-dimensional simplicial complexes |
| \(\quad\)We consider the problem of Santos about finding the largest possible diameter of a strongly connected \(d\)-dimensional simplicial complex on \(n\) vertices. For each \(d\), we find the optimum value for every \(n\) that is large enough using the technique of absorption. The underlying theorem can be seen as a generalization of finding a tight Euler trail in a \(d\)-uniform hypergraph. Joint work with Stefan Glock, Olaf Parczyk, and Tibor Szabó. |
| 16.05.2025 |
Andrzej Ruciński |
AMU |
| Graphic Images of Wordy Twins |
| \(\quad\)No abstract - the title speaks for itself. |
| 17.05.2025 |
Katarzyna Rybarczyk |
AMU |
| Modularity of preferential attachment graphs |
| \(\quad\)We study the preferential attachment model \(G_n^h\). A graph \(G_n^h\) is generated from a finite initial graph by adding new vertices one at a time. Each new vertex connects to \(h\ge 1\) already existing vertices, and these are chosen with probability proportional to their current degrees. We are particularly interested in the community structure of \(G_n^h\), which is expressed in terms of the so--called modularity. We prove that the modularity of \(G_n^h\) is with high probability upper bounded by a function that tends to 0 as \(h\) tends to infinity. This resolves the conjecture of Prokhorenkova, Prałat, and Raigorodskii from 2016.
\(\quad\)As a byproduct, we obtain novel concentration results (which are interesting in their own right) for the volume and edge density parameters of vertex subsets of \(G_n^h\). The key ingredient here is the definition of the function \(\mu\), which serves as a natural measure for vertex subsets, and is proportional to the average size of their volumes. This extends previous results on the topic by Frieze, Prałat, Pérez-Giménez, and Reiniger from 2019. |
| 16.05.2025 |
Giovanne Santos |
UH |
| Spanning trees in dense oriented graphs |
| \(\quad\)We prove that for any \(\gamma > 0\), there exists \(n_0\) such that every oriented graph on \(n \geq n_0\) vertices with minimum semidegree at least \((3/8 + \gamma)n\) contains every bounded-degree tree on \(n\) vertices in any orientation. This is asymptotically best possible.
\(\quad\)In this talk, we focus on the case of almost-spanning trees and show how mixing properties of random walks, combined with Szemerédi's regularity lemma, can be used to embed oriented trees.
\(\quad\)This is joint work with Pedro Araújo and Maya Stein. |
| 17.05.2025 |
Eva Schinzel |
FU Berlin |
| Triangle factors in the semi-random graph process |
| \(\quad\)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 monotonically 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 · n rounds. The main tool used in the analysis of our strategy will be the differential equation method. |
| 16.05.2025 |
Alexandra Wesolek |
TU Berlin |
| Asymptotic dimension and distributed algorithms |
| \(\quad\) Imagine you play a colouring game on a metric space with k colours. Your opponent picks some distance r>0 and you colour the metric space into regions such that two regions of the same colour are at least at distance r from each other. If the regions have bounded diameter and each point of the metric space is coloured, you win, otherwise you lose. The asymptotic dimension of a metric space is the largest k at which your opponent has a winning strategy. For example, the asymptotic dimension of an infinite line is 1. The concept of asymptotic dimension can be applied to graph classes and the shortest path metric. Recently it was shown that H-minor-free graphs have asymptotic dimension at most 2. I will discuss how this result can be used for distributed algorithms. Joint work with Bonamy, Gavoille and Picavet. |
Organizers
Zbigniew Lonc, Paweł Rzążewski, Paweł Naroski, Hubert Grochowski
