Yannick Mogge
(TUHH)

Michael Krivelevich
(Tel Aviv University)

Peter Martin
(FU Berlin)

Alexandra Wesolek
(TU Berlin)

Michael Krivelevich
(Tel Aviv University)

Raphael Steiner
(ETH Zürich)

Jan Volec
(Czech Technical University in Prague)

Yannick Mogge (TUHH)

Creating a tree universal graph in positional games

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 Maker-Breaker and Waiter-Client game on the complete graph $K_n$, Maker/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. Both of our results show that the building player 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.   

Michael Krivelevich (Tel Aviv University)

Improving graph's parameters through random perturbation

Abstract: Let G be a graph on n vertices, and assume that its minimum degree is at least k, or its independence number is at most t. What can be said then about various graph-theoretic parameters of G, such as connectivity, large minors and subdivisions, diameter, etc.? Trivial extremal examples (disjoint cliques, unbalanced complete bipartite graphs, random graphs and their disjoint unions) supply rather prosaic bounds for these questions. We show that the situation is bound to change dramatically if one adds relatively few random edges on top of G (the so called randomly perturbed graph model, launched in a paper by Bohman, Frieze and Martin from 2003). Here are representative results, in a somewhat approximate form:
- Assuming delta(G)>=k, and for s<ck, adding about Cns*log (n/k)/k random edges to G results with high probability in an s-connected graph;
- Assuming alpha(G)<= t and adding cn random edges to G typically produces a graph containing a minor of a graph of average degree of order n/sqrt{t}.

In this talk I will introduce and discuss the model of randomly perturbed graphs, and will present our results.

A joint work with Elad Aigner-Horev and Dan Hefetz.

Peter Martin (FU Berlin)

Lower bounds on Ramsey multiplicity of cliques..

Abstract: Ramsey theory asks how many vertices a complete graph needs to have to guarantee a monochromatic (m.c.) clique of size t in any 2-colouring of the edges. Ramsey multiplicity studies how many of such m.c. cliques are guaranteed beyond that. In this talk we will see central definitions and simple bounds by Erdős. Conlon improved the asymptotic (w.r.t. n) lower bound on the guaranteed number of m.c. cliques of size t in a complete graph of size n (together with any edge 2-colouring) from being a 4^{-t^2(1+o(1))} fraction of all t-sets to being a (2\sqrt(2))^{-(t^2(1+o(1)))} fraction and further to a C^{-(t^2(1+o(1)))} fraction, where C is around 2.18.

Alexandra Wesolek (TU Berlin)

Cops and Robber Game on Surfaces.

Abstract: The Cops and Robber game on geodesic spaces is a pursuit-evasion game with discrete steps which captures the behavior of the game played on graphs, as well as that of continuous pursuit-evasion games. In this talk we discuss the rules of the game and strategies for the players when the game is played on compact surfaces. We obtain the surprising result that on surfaces of constant curvature two cops have a strategy to come arbitrarily close to the robber, independently of the genus of the surface.
Joint work with Vesna Iršič and Bojan Mohar.

Michael Krivelevich (Tel Aviv University)

Percolation through isoperimetry.

Abstract: Let G be a d-regular graph of growing degree on n vertices, and form a random subgraph G_p of G by retaining edge of G independently with probability p=p(d). Which conditions on G suffice to observe a phase transition at p=1/d, similar to that in the binomial random graph G(n,p), or, say, in a random subgraph of the binary hypercube Q^d?
We argue that in the supercritical regime p=(1+epsilon)/d, epsilon>0 being a small constant, postulating that every vertex subset S of G of at most n/2 vertices has its edge boundary at least C|S|, for some large enough constant C=C(\epsilon)>0, suffices to guarantee likely appearance of the giant component in G_p. Moreover, its asymptotic order is equal to that in the random graph G(n,(1+\epsilon)/n), and all other components are typically much smaller.
We also give examples demonstrating tightness of our main result in several key senses.

A joint work with Sahar Diskin, Joshua Erde and Mihyun Kang.

Raphael Steiner (ETH Zürich)

Hadwiger's conjecture and topological bounds.

Abstract: The Odd Hadwiger's conjecture, formulated by Gerards and Seymour in 1995, is a substantial strengthening of Hadwiger's famous coloring conjecture from 1943. We investigate whether the hierarchy of topological lower bounds on the chromatic number, introduced by Matoušek and Ziegler (2003) and refined recently by Daneshpajouh and Meunier (2023), forms a potential avenue to a disproof of Hadwiger's conjecture or its odd-minor variant.
In this direction, we prove that, in a very general sense, every graph G that admits a topological lower bound of t on its chromatic number, contains K⌊t/2⌋+1 as an odd-minor. This solves a problem posed by Simonyi and Zsbán [European Journal of Combinatorics, 31(8), 2110--2119 (2010)]. We also prove that if for a graph G the Dol'nikov-Kříž lower bound on the chromatic number (one of the lower bounds in the aforementioned hierarchy) attains a value of at least t, then G contains Kt as a minor.
Finally, extending results by Simonyi and Zsbán, we show that the Odd Hadwiger's conjecture holds for Schrijver and Kneser graphs for any choice of the parameters. The latter are canonical examples of graphs for which topological lower bounds on the chromatic number are tight.

Jan Volec (Czech Technical University in Prague)

On the minimum eigenvalue of regular triangle-free graphs.

Abstract: Motivated by two well-known conjectures of Erdős on triangle-free graphs, Brandt asked in 1994 whether the smallest eignvalue of an n-vertex d-regular triangle-free graph is at most 4n/25 - d. In this talk, we confirm the conjecture of Brandt in a stonger sense: we show that the smallest eigenvalue of the signless Laplacian of any n-vertex triangle-free graph G is at most 15n/94 < 0.1596n. In particular, if G is d-regular, then its smallest eigenvalue is at most 15n/94 - d.
This is a joint work with Jozsi Balogh, Felix Clemen, Bernard Lidický and Sergey Norin.

Yamaan Attwa (FU Berlin)

Erdős-Hajnal is true for an infinite family of prime graphs.

Abstract: We say that a graph H has the Erdős-Hajnal property if there exists some ε = ε(H)>0 such that every H-free graph G has a homogeneous set of size at least |G|^ε. Erdős and Hajnal conjectured that every graph H has the EH-property. The conjecture is known to be true for the set F of graphs on at most 5 vertices except P₅ and its complement. Alon, Pach and Solymosi proved that if H₁ and H₂ have the EH-property then H constructed by substituting H₁ into a vertex of H₂ also has the EH-property. Until recently, our knowledge of graphs with the EH-property was limited to the smallest family C of graphs containing F and is closed under substitutions. This talk is an exposition of a paper by Nguyen, Scott and Seymour proving for every n ≥ 4 the existence of a graph G_n on n vertices having the EH-property and is unconstructible from smaller graphs by vertex substitutions.