Springe direkt zu Inhalt

BPHW Seminar in Discrete Mathematics 2024

May 24-25, 2024
Freie Universität Berlin

This series of meetings was initiated in the mid 90's as a seminar between the research groups of Prof. Michał Karoński (Adam Mickiewicz University, Poznań) and Prof. Hans Jürgen Prömel ((at the time) Humboldt University Berlin). Since then the meeting has evolved into a yearly two-day joint workshop, and more recently groups from the University of Hamburg, TU Hamburg, and TU Warsaw have joined as well. The scope of the seminar covers a broad range of central topics in modern Discrete Mathematics, including random discrete structures and algorithms, extremal and probabilistic combinatorics, algorithmic discrete mathematics and related fields. This year the event takes place on May 24 and 25 at the Freie Universität Berlin.


This seminar is free and open to anyone interested. To register, please fill out the form which you can find via the following link:


List of Participants


Freie Universität Berlin
Institut für Mathematik
Arnimallee 3 (Room 001)
14195 Berlin

Programm Overview


Time   Title
13:30 - 13:55 Arrival of Participants  
13:55 - 14:00 Opening Remarks  
14:00 - 14:30 Małgorzata Śleszyńska-Nowak Strongly Proper Connected Coloring
14:30 - 15:00 Irene Muzi An elementary bound for the directed grid theorem
15:00 - 15:30 Sylwia Antoniuk Clique factors in randomly augmented graphs
15:30 - 16:00 Coffee Break  
16:00 - 16:45 Letícia Mattos Clique packings in random graphs
16:45 - 17:15 Yannick Mogge Creating a tree universal graph in Waiter-Client games
17:15 - 17:30 Coffee Break  
17:30 - 18:00 Alexandra Wesolek Subgraph-universal planar graphs for trees
18:00 - 18:30 Michał Dębski Avoiding Tangrams
19:30 - Dinner at Altensteiner Krug Altensteinstraße 42, 14195 Berlin


Time   Title
8:30 - 9:00 Katarzyna Rybarczyk-Krzywdzinska Small subgraphs in random intersection graphs
9:00 - 9:30 Hubert Grochowski Approximation algorithms for L(2,1)-labeling of unit disk graphs
9:30 - 10:00 Silas Rathke On the maximum diameter of d-dimensional simplicial complexes
10:00 - 10:30 Coffee Break  
10:30 - 11:15 Stefan Glock Tight Hamilton cycles with high discrepancy
11:15 - 11:45 Fabian Hamann Speed and size of dominating sets in domination games
11:45 - 12:00 Coffee Break  
12:00 - 12:30 Andrzej Rucinski Twins everywhere. How big is the problem.
12:30 - 13:00 Simón Piga Turán problems for simplicial complexes
13:00 - 13:05 Closing Remarks  

Strongly Proper Connected Coloring

Małgorzata Śleszyńska-Nowak (Warsaw University of Technology)

Abstract: In a strong edge coloring of a graph G, we require that each color class forms an induced matching in G, which means that not only every pair of adjacent edges is colored differently, but also every pair of edges adjacent to some other common edge. I will talk about a new variant of proper connected graph coloring, based on strong coloring.

An edge-colored graph is strongly proper connected if every two vertices are connected by at least one strongly colored path. We will consider how many colors are needed to color the edges of the graph to make it strongly proper connected. I will present the current state of knowledge on this subject. I will also show what we know about other variants of connected coloring.

This is joint work with Michał Dębski, Jarosław Grytczuk and Paweł Naroski.

Clique packings in random graphs

Letícia Mattos (University of Heidelberg)

Abstract: We consider the question of how many edge-disjoint near-maximal cliques may be found in the dense Erdős-Rényi random graph $G(n,p)$.  Recently Acan and Kahn showed that the largest such family contains only $O(n^2/(\log{n})^3)$ cliques, with high probability, which disproved a conjecture of Alon and Spencer.  We prove the corresponding lower bound, $\Omega(n^2/(\log{n})^3)$, by considering a random graph process which sequentially selects and deletes near-maximal cliques. To analyse this process we use the Differential Equation Method. We also give a new proof of the upper bound $O(n^2/(\log{n})^3)$ and discuss the problem of the precise size of the largest such clique packing.

Joint work with S. Griffiths.

Creating a tree universal graph in Waiter-Client games

Yannick Mogge (Technical University Hamburg)

Abstract: In this talk we consider positional games, where the winning sets are tree universal graphs, which contain copies of all spanning trees with a certain maximum degree. In particular, we show that in the unbiased Waiter-Client game on the complete graph $K_n$, Waiter has a strategy to occupy a graph which contains copies of all spanning trees with maximum degree at most $cn/\log(n)$, for a suitable constant $c$ and $n$ being large enough. This also shows that Waiter can play at least as good as suggested by the random graph intuition.

This is a joint work with Grzegorz Adamski, Sylwia Antoniuk, Małgorzata Bednarska-Bzdęga, Dennis Clemens, and Fabian Hamann.

Subgraph-universal planar graphs for trees

Alexandra Wesolek (Technical University Berlin)

Abstract: Nash-Williams’ tree-covering theorem implies that every planar graph contains three spanning trees which cover all edges. Does the reverse hold? Given three trees on n vertices, does there exist a planar graph on n vertices containing all three as subgraph? And if not, then how many vertices does the planar graph need? Furthermore, this leads to the question for a tree universal planar graph. In the 60's many papers were published looking for graphs containing all graphs in a given class, such as a tree containing all trees or a graph with minimal number of edges containing all trees. We investigate the natural question for a planar graph containing all trees on n vertices and show that such a graph exists on a polynomial number of vertices in n.

Avoiding Tangrams

Michał Dębski (Warsaw University of Technology)

Abstract: We say that a word T is a tangram if each letter occurs in T an even number of times. A cut number of a tangram T is the minimum number of cuts needed to split T in such a way that the resulting fragments can be rearranged to form two identical words, i.e. it is the minimum k such that T is a concatenation of k+1 fragments and there exists a permutation P of the set [k+1] and a number j such that the concatenation of fragments with numbers P(1), P(2), ..., P(j) is equal to the concatenation of fragments with numbers P(j+1), P(j+2), ..., P(k+1).

We will look for infinite words over an alphabet A that do not contain tangrams of specified cut number, with the goal of minimizing the size of A. Let t(k) denote the minimum size of the alphabet A such that there is an infinite word over A that does not contain tangrams with cut number at most k. We show that t(k) is at most 1024(log k + log log k), which is tight up to a multiplicative constant.

Small subgraphs in random intersection graphs

Katarzyna Rybarczyk-Krzywdzińska (Adam Mickiewicz University Poznań)

Abstract: One of the first problems solved considering random intersection graphs was finding the threshold function for subgraph containment. Then the distribution of the number of copies on the threshold was determined. However the problem of the normal approximation of the number of copies of small subgraphs remained open. This is due to the fact that in random intersection graphs there is far larger dependency between subgraph appearances. Recently a result about triangles has appeared, but it fails to cover the whole range of parameters.

We will present a new method for proving normal approximation of the number of small subgraphs specially adapted to random intersection graphs. The virtue of our approach is that it gives tight estimates on the maximum of Kolmogorov and Wasserstein distances between the normalized distribution of the number of copies of a graph and N(0,1) distribution. We will show how it is applied to edge count in random intersection graphs and give a glimpse at our work in progress concerning clique count problem.

Approximation algorithms for L(2,1)-labeling of unit disk graphs

Hubert Grochowski (Warsaw University of Technology)

Abstract: The L(2,1)-labeling of a graph is an assignment of non-negative integers to the vertices such that labels of adjacent vertices differ by at least 2, and labels of vertices at a distance of two from each other are distinct. This model is inspired by the frequency assignment problem in radio networks, so a natural and interesting class of graphs are disk intersection graphs, especially unit disk graphs. Ono and Yamanaka proposed an 8-approximation algorithm for L(2,1)-labeling of unit disk graphs. Their algorithm bases on some coloring of the Euclidean plane, called shaded coloring. Inspired by their work, we have introduced a family of approximation algorithms for L(2,1)-labeling of unit disk graphs, which base on a fractional version of shaded coloring. The best of our algorithms achieves an asymptotic approximation ratio less than 6.

Joint work with Konstanty Junosza-Szaniawski.

On the maximum diameter of d-dimensional simplicial complexes

Silas Rathke (Free University Berlin)

Abstract: We will look at a problem of Santos about the largest possible diameter of a d-dimensional simplicial complex on n vertices. In dimension 2, we determine the exact value of the maximum for every n using an explicit construction. For d at least 3, we improve on a series of lower bounds using a novel randomized approach.

Joint work with Olaf Parczyk and Tibor Szabó.

Tight Hamilton cycles with high discrepancy

Stefan Glock (University of Passau)

Abstract: In discrepancy theory, the basic question is whether a structure can be partitioned in a balanced way, or if there is always some “discrepancy” no matter how the partition is made.

In the context of graph theory, a well-studied question is whether for a given host graph, any 2-colouring of its edges must contain a specified subgraph "with high discrepancy'', meaning that within this subgraph one of the colour classes is significantly larger than the other. We initiate the study of such questions for hypergraphs. Our main result is a discrepancy version of the celebrated theorem of Rödl, Ruciński and Szemerédi on tight Hamilton cycles in Dirac hypergraphs.
Joint work with Lior Gishboliner and Amedeo Sgueglia.

Speed and size of dominating sets in domination games

Fabian Hamann (Technical University Hamburg)

Abstract: We consider Maker-Breaker domination games, a variety of positional games, in which two players (Dominator and Staller) alternately claim vertices of a given graph. Dominator's goal is to fully claim all vertices of a dominating set, while Staller tries to prevent Dominator from doing so, or at least tries to delay Dominator's win for as long as possible.

We prove a variety of results about domination games, including the number of turns Dominator needs to win and the size of a smallest dominating set that Dominator can occupy, when considering e.g. random graphs, powers of paths, and trees. We could also show that speed and size can be far apart, and we prove further non-intuitive statements about the general behaviour of such games.

The talk is based on joint work with Ali Deniz Bagdas, Dennis Clemens and Yannick Mogge.

Twins everywhere. How big is the problem.

Andrzej Ruciński (Adam Mickiewicz University Poznań)

Abstract: I will present the current state of art with respect to the size of the largest homogeneous substructures, as well as twins, in various combinatorial structures (words over finite alphabets, permutations, ordered [hyper]matchings). Both, the worst case (extremal) and the average case (random) will be discussed and several open problems will be stated.

Turán problems for simplicial complexes

Simón Piga (University of Hamburg)

Abstract: A simplicial complex H consists of a pair of sets (V,E) where V is a set of vertices and $E\subseteq\mathscr{P}(V)$ is a collection of subsets of V closed under taking subsets.

Given a simplicial complex F and $n\in \mathds N$, the extremal number ex(n,F) is the maximum number of edges that a simplicial complex on n vertices can have without containing a copy of F. We initiate the systematic study of extremal numbers in this context by asymptotically determining the extremal numbers of several natural simplicial complexes. In particular, we asymptotically determine the extremal number of a simplicial complex where the problem does not ultimately reduce to solving the Turán problem for a related family of uniform hypergraphs.

An elementary bound for the directed grid theorem

Irene Muzi (University of Hamburg)

Abstract: In 2015, Kawarabayashi and Kreutzer proved the directed grid theorem confirming a conjecture by Reed, Johnson, Robertson, Seymour, and Thomas from the mid-nineties. The theorem states the existence of a function f such that every digraph of directed tree-width f(k) contains a cylindrical grid of order k as a butterfly minor, but the given function grows non-elementarily with the size of the grid minor.

In this talk I will present an alternative proof of the directed grid theorem which is conceptually much simpler, more modular in its composition and also improves the upper bound for the function f to a power tower of height 22. Our proof is inspired by the breakthrough result of Chekuri and Chuzhoy, who proved a polynomial bound for the excluded grid theorem for undirected graphs. We translate a key concept of their proof to directed graphs by introducing cycles of well-linked sets (CWS), and show that any digraph of high directed tree-width contains a large CWS, which in turn contains a large cylindrical grid, improving the result due to Kawarabayashi and Kreutzer from an non-elementary to an elementary function.

An immediate application of our result is an improvement of the bound for Younger's conjecture proved by Reed, Robertson, Seymour and Thomas (1996) from a non-elementary to an elementary function. The same improvement applies to other types of Erdős-Pósa style problems on directed graphs.

This is joint work with Meike Hatzel, Stephan Kreutzer, and Marcelo Garlet Milani.

Clique factors in randomly augmented graphs

Sylwia Antoniuk (Adam Mickiewicz University Poznań)

Abstract: A randomly augmented graph $G^p = G_\alpha \cup G_{n,p}$ is obtained by taking a deterministic $n$-vertex graph $G_\alpha$ with minimum degree $\delta(G)\geq \alpha n$ and adding the edges of the binomial random graph $G_{n,p}$ defined on the same vertex set. For which value $p$ does the graph $G^p$ contain a $K_r$-factor w.h.p.?

The  order of magnitude of the minimal value of $p$ has been determined  whenever $\alpha \neq 1- \frac{s}{r}$ for an integer $s$ (see Han, Morris, and Treglown [RSA, 2021] and Balogh, Treglown, and Wagner [CPC, 2019]).

We establish the minimal probability $p_s$ (up to a constant factor) for all values of $\alpha = 1-\frac{s}{r} \leq \frac 12$, and show that the threshold exhibits a polynomial jump at $\alpha = 1-\frac{s}{r}$ compared to the surrounding intervals. An extremal example $G_{\alpha}$ which shows that $p_s$ is optimal up to a constant factor differs from the previous (usually multipartite) examples in containing a pseudorandom subgraph.


Olaf Parczyk, Silas Rathke, Tibor Szabó, Alexandra Wesolek

Supported by