# Research Seminar

Starting in the Summer Semester 2024, we are holding a fortnightly research seminar with invited speakers from a range of topics in Combinatorics. The seminar generally takes place in **Seminarraum 1**, roughly every other **Monday** at **1pm** - all students and staff are welcome to join us. See below for a list of upcoming and previous talks.

## Schedule

## Summer Semester 2024

University of Cambridge

What is the maximum proportion of $d$-dimensional space that can be covered by non-overlapping, identical spheres? In this talk I will discuss a new lower bound for this problem, which is the first asymptotically growing improvement to Rogers' bound from 1947. Our proof is almost entirely combinatorial and reduces to a novel theorem about independent sets in graphs with bounded degrees and codegrees.

This is based on joint work with Marcelo Campos, Matthew Jenssen and Marcus Michelen.

Karlsruher Institut für Technologie

A classical problem in combinatorial geometry, posed by Erdős in 1946, asks to determine the maximum number of unit segments in a set of $n$ points in the plane. Since then a great variety of extremal problems in finite planar point sets have been studied. Here, we look at such questions concerning triangles. Among others we answer the following question asked by Erdős and Purdy almost 50 years ago: Given $n$ points in the plane, how many triangles can be approximate congruent to equilateral triangles?

For our proofs we use hypergraph Turán theory. This is joint work with Balogh and Dumitrescu.

ETH Zürich

We show that if $n$ is odd and $p ≥ C \log{n}/n$, then with high probability Hamilton cycles in $G(n, p)$ span its cycle space. More generally, we show this holds for a class of graphs satisfying certain natural pseudorandom properties. The proof is based on a novel idea of parity-switchers, which can be thought of as analogues of absorbers in the context of cycle spaces. As another application of our method, we show that Hamilton cycles in a near-Dirac graph $G$, that is, a graph $G$ with odd $n$ vertices and minimum degree $n/2 + C$ for sufficiently large constant $C$, span its cycle space. This is joint work with Micha Christoph and Rajko Nenadov.

University of Illinois, Chicago

Given integers $1 < s < t$, what is the maximum size of a $K_s$-free subgraph that every $n$-vertex $K_t$-free graph is guaranteed to contain? This problem was posed by Erdős and Rogers in the 1960s as a way to generalize classical graph Ramsey numbers (which correspond to the case $s = 2$). We prove almost optimal results in the case $t=s+1$ using recent constructions in Ramsey theory. We also consider the problem where we replace $K_s$ and $K_t$ by arbitrary graphs $H$ and $G$ and discover several interesting new phenomena.

This is joint work with Jacques Verstraete.

ETH Zürich

An $n$-vertex graph $G$ is a $C$-expander if $|N(X)| \ge C|X|$ for every $X \subseteq V(G)$ with $|X| \lt n/2C$ and there is an edge between every two disjoint sets of at least $n/2C$ vertices. We show that there is some constant $C > 0$ for which every $C$-expander is Hamiltonian. In particular, this implies the well known conjecture of Krivelevich and Sudakov from 2003 on Hamilton cycles in $(n,d,\lambda)$-graphs. This completes a long line of research on the Hamiltonicity of sparse graphs, and has many applications. Joint work with N. Draganić, R. Montgomery, A. Pokrovskiy and B. Sudakov.

Technische Universität Berlin

Chung and Graham showed in 1983 that there exist $n$-vertex graphs with $O(n log n)$ edges which contain all trees on $n$ vertices as subgraphs. We extend this result by showing that there exists a planar graph on a polynomial number of vertices in $n$ that contains every tree on $n$ vertices as a subgraph. This is joint work with Helena Bergold, Vesna Iršič, Robert Lauff, Joachim Orthaber and Manfred Scheucher.

Czech Technical University in Prague

Let $R(C_n)$ be the Ramsey number of the cycle on $n$ vertices. We prove that, for some $C > 0$, with high probability every $2$-colouring of the edges of $G(N,p)$ has a monochromatic copy of $C_n$, as long as $N> R(C_n) + C/p$ and $p > C/n$. This is sharp up to the value of $C$ and it improves results of Letzter and of Krivelevich, Kronenberg and Mond.

This is joint work with Matías Pavez-Signe and Nicolas Sanhueza-Matamala.

Heidelberg University

We give an overview of some key conjectures and results in the area.

CISPA Helmholtz Center for Information Security

For some positive integer $k$, a digraph $D$ is called $k$-\textit{dicolorable} if there exists a partition $(V_1,\ldots,V_k)$ of $V(D)$ such that $D[V_i]$ is acyclic for $i \in [k]$. Further, we say that $D$ is {\it $k$-dicritical} if $D$ is not $(k-1)$-dicolorable, but all of its proper subgraphs are.

The analogous problem in undirected graphs having been studied extensively, it is natural to try to understand what the maximum density of a large $k$-dicritical digraph is. Hoshino and Kawarabayashi conjectured that for every positive integer $k$, a simple $k$-dicritical digraph on $n$ vertices has at most $(\frac{1}{2}-\frac{1}{2^k-1})n^2$ arcs, with a finite number of exceptions. Aboulker observed that this conjecture implies that there are only finitely many $k$-dicritical tournaments for any positive integer $k$.

We show that this latter statement is true in the first nontrivial case, that is, when $k=3$. We also extend this result for semi-complete digraphs. Finally, by a computer-assisted approach, we give the full list of 3-dicritical semi-complete digraphs. There are exactly 8 of them, 2 of which are tournaments.

This is joint work with Frédéric Havet and Lucas Picasarri-Arrieta.

Department of Mathematical Sciences, KAIST (Daejeon, South Korea)

For a given hypergraph $H$ and a vertex $v\in V(H)$, consider a random matching $M$ chosen uniformly from the set of all matchings in $H$. In $1995$, Kahn conjectured that if $H$ is a $d$-regular linear $k$-uniform hypergraph, the probability that $M$ does not cover $v$ is $(1 + o_d(1))d^{-1/k}$ for all vertices $v\in V(H)$. This conjecture was proved for $k = 2$ by Kahn and Kim in $1998$. In this talk, we disprove this conjecture for all $k \geq 3$. For infinitely many values of $d,$ we construct $d$-regular linear $k$-uniform hypergraph $H$ containing two vertices $v_1$ and $v_2$ such that $\mathcal{P}(v_1 \notin M) = 1 - \frac{(1 + o_d(1))}{d^{k-2}}$ and $\mathcal{P}(v_2 \notin M) = \frac{(1 + o_d(1))}{d+1}$. The gap between $\mathcal{P}(v_1 \notin M)$ and $\mathcal{P}(v_2 \notin M)$ in this $H$ is best possible. In the course of proving this, we also prove a hypergraph analog of Godsil's result on matching polynomials and paths in graphs, which is of independent interest.

Technische Universität Hamburg

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\l gorzata Bednarska-Bzd\c{e}ga, Dennis Clemens, and Fabian Hamann.

Technische Universität Darmstadt

TBC

## Previous Talks

## Winter Semester 2023/24

Institute of Computer Science, Czech Academy of Sciences, Prague

A theorem of Frieze from 1985 asserts that the total weight of the minimum spanning tree of the complete graph $K_n$ whose edges get independent weights from the distribution $UNIFORM[0,1]$ converges to Apéry's constant in probability, as $n \to \infty$. We generalize this result to sequences of graphs $G_n$ that converge to a graphon $W$. Further, we allow the weights of the edges to be drawn from different distributions (subject to moderate conditions). The limiting total weight $\kappa(W)$ of the minimum spanning tree is expressed in terms of a certain branching process defined on $W$, which was studied previously by Bollobás, Janson and Riordan in connection with the giant component in inhomogeneous random graphs. Joint work with Gopal Viswanathan. arXiv:2310.11705.

Heidelberg University

In recent years, there has been a push to translate extremal results in graph theory to random graphs, investigating to what extent they hold. Sudakov and Vu initiated the systematic study of so-called local resilience: roughly speaking, this refers to minimum degree conditions such that every subgraph of a graph with such a minimum degree satisfies a desired property. The study of local resilience has been most prominent on random graphs. In this talk I will survey some of the results in the area, and then discuss an open problem about the local resilience of random geometric graphs with respect to Hamiltonicity. I will further discuss some progress towards this problem. This talk is based on joint work with Lyuben Lichev and Alexandra Wesolek.

Heidelberg University

We introduce a family of robust spanning trees embedded in Euclidean space, named central spanning tree (CST), whose geometrical structure is resilient against perturbations such as noise. The family of trees is defined through a parameterized NP-hard minimization problem over the edge lengths, with specific instances including the minimum spanning tree or the Euclidean Steiner tree. The minimization problem weighs the length of the edges by their tree edge-centralities, which are regulated by a parameter $\alpha$. Two variants of the problem are explored: one permitting the inclusion of Steiner points (referred to as branched central spanning tree or BCST), and another that does not. The effect of $\alpha$ on tree robustness is empirically analyzed, and a heuristic for approximating the optimal solution is proposed. Geometrical properties of the tree and its behavior in limit cases as $\alpha\to\pm\infty$ are also studied. This is a joint work with Christoph Schnörr and Fred Hamprecht.

Centre de Reserca Matemàtica

*Can we identify uniquely each edge of a graph using few paths?*

A collection $\mathcal{P}$ of (non-necessarily induced) paths in a graph G is said to be
*separating* if, for all distinct $e, f ∈ E(G)$, there exists a path in $\mathcal{P}$ containing
either $e$ or $f$ , but not both.
We shall discuss recent advances towards this problem (confirming con-
jectures posed by Balogh, Csaba, Martin, and Pluhár and by Falgas-Ravry,
Kittipassorn, Korándi, Letzter, and Narayanan), as well as some of related
open questions.
This is joint work with Fábio Botler, Marthe Bonamy, François Dross and
Jozef Skokan.