Research Seminar
Roughly every other week we have a research seminar with external and internal speakers. Students and staff are welcome to join us.
Room: SR1 (provisionally)
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
TBC
ETH Zürich
TBC
University of Illinois, Chicago
TBC
Technische Universität Berlin
TBC
CISPA Helmholtz Center for Information Security
TBC
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 Kn whose edges get independent weights from the distribution UNIFORM[0,1] converges to Apéry's constant in probability, as n→∞. We generalize this result to sequences of graphs Gn 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 κ(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 α. 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 α 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 α→±∞ 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 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 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.
