Schedule and abstracts 2024/2025
Schedule and abstracts 2023/2024
15.02.2024 
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 MakerBreaker and WaiterClient 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 BednarskaBzdȩga, Dennis Clemens, and Fabian Hamann.

08.02.2024 
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 graphtheoretic 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 sconnected 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 AignerHorev and Dan Hefetz.

01.02.2024 
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 2colouring 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 2colouring) from being a 4^{t^2(1+o(1))} fraction of all tsets 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.

25.01.2024 
Alexandra Wesolek (TU Berlin)

Cops and Robber Game on Surfaces.

Abstract: The Cops and Robber game on geodesic spaces is a pursuitevasion game with discrete steps which captures the behavior of the game played on graphs, as well as that of continuous pursuitevasion 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.

17.01.2024 
Michael Krivelevich (Tel Aviv University)

Percolation through isoperimetry.

Abstract: Let G be a dregular 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 CS, 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.

11.01.2024 
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 oddminor 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 oddminor. This solves a problem posed by Simonyi and Zsbán [European Journal of Combinatorics, 31(8), 21102119 (2010)]. We also prove that if for a graph G the Dol'nikovKříž 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.

17.11.2023 
Jan Volec (Czech Technical University in Prague)

On the minimum eigenvalue of regular trianglefree graphs.

Abstract: Motivated by two wellknown conjectures of Erdős on trianglefree graphs, Brandt asked in 1994 whether the smallest eignvalue of an nvertex dregular trianglefree 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 nvertex trianglefree graph G is at most 15n/94 < 0.1596n. In particular, if G is dregular, 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.

26.10.2023 and 02.11.2023 
Yamaan Attwa (FU Berlin)

ErdősHajnal is true for an infinite family of prime graphs.

Abstract: We say that a graph H has the ErdősHajnal property if there exists some ε = ε(H)>0 such that every Hfree graph G has a homogeneous set of size at least G^{ε}. Erdős and Hajnal conjectured that every graph H has the EHproperty. The conjecture is known to be true for the set F of graphs on at most 5 vertices except P_{5} and its complement. Alon, Pach and Solymosi proved that if H_{1} and H_{2} have the EHproperty then H constructed by substituting H_{1} into a vertex of H_{2} also has the EHproperty. Until recently, our knowledge of graphs with the EHproperty 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 EHproperty and is unconstructible from smaller graphs by vertex substitutions.

Links
Mailing list:
To subscribe to the mailinglist of the seminar, please follow this link:
https://lists.fuberlin.de/listinfo/combinatoricsseminar
Notes:
For any request, please send an email to:
combinatoricsseminarowner@lists.fuberlin.de
Archives
Schedule and abstracts 2024/2025
Schedule and abstracts 2023/2024
Schedule and abstracts 2022/2023
Schedule and abstracts 2021/2022
Schedule and abstracts 2020/2021
Schedule and abstracts 2019/2020
Schedule and abstracts 2018/2019
Schedule and abstracts 2017/2018
Schedule and abstracts 2016/2017
Schedule and abstracts 2015/2016
Schedule and abstracts 2014/2015
Schedule and abstracts 2013/2014
Schedule and abstracts 2012/2013
Schedule and abstracts 2011/2012
Schedule and abstracts 2010/2011
Schedule and abstracts 2009/2010