Theoretical Computer Science & Discrete Mathematics

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: tba

Schedule

Summer Semester 2024

Further talks to be confirmed.

Start
Speaker
Title, tap for details
Apr 22, 1:00 pm
Julian Sahasrabudhe (Online)
A new lower bound for sphere packing

University of Cambridge

What is the maximum proportion of dd-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.

Source: infweb
Apr 29, 1:00 pm
Felix Clemen
Triangles in the Plane

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

Source: infweb
May 27, 1:00 pm
David Munhá Correia
TBC

ETH Zürich

TBC

Source: infweb

Previous Talks

Winter Semester 2023/24

Start
Speaker
Title, tap for details
Oct 24, 2:00 pm
Jan Hladký
Random minimum spanning tree and dense graph limits

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 KnK_n whose edges get independent weights from the distribution UNIFORM[0,1]UNIFORM[0,1] converges to Apéry's constant in probability, as nn \to \infty. We generalize this result to sequences of graphs GnG_n that converge to a graphon WW. Further, we allow the weights of the edges to be drawn from different distributions (subject to moderate conditions). The limiting total weight κ(W)\kappa(W) of the minimum spanning tree is expressed in terms of a certain branching process defined on WW, 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.

Source: infweb
Dec 12, 1:00 pm
Alberto Espuny Díaz
Local resilience of random geometric graphs

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.

Source: infweb
Jan 30, 11:00 am
Enrique Fita Sanmartín
Robust spanning trees given vertices in Rd\mathbb{R}^d

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.

Source: infweb
Feb 29, 11:00 am
Tássio Naia
Separating systems in graphs

Centre de Reserca Matemàtica

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

A collection P\mathcal{P} of (non-necessarily induced) paths in a graph G is said to be separating if, for all distinct e,fE(G)e, f ∈ E(G), there exists a path in P\mathcal{P} containing either ee or ff , 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.

Source: infweb
Last update on Apr 8, 2024 at 15:16 UTC
color-mode icon
home icon