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.

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.

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.

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.

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.

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.

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.

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ó.

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.

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.

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.

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.

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.

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.