All posts by jboulanger

The Haagerup property

Upcoming seminar

Speaker: Ignacio Vergara
Departamento de Matemática y ciencias de la computación (USACH)
Date: Tuesday, October 21, 2025 at 2:00 p.m. Santiago time

Abstract:

The Haagerup property is an analytic property of groups that generalises amenability. It originated from the study of C*-algebras, and it has found applications in several areas of mathematics, including harmonic analysis, geometric group theory, topology, and ergodic theory. This talk will consist in an introduction to this property and its connections to group actions on Banach spaces.

Venue: John Von Neumann Seminar Room, CMM, Beauchef 851, North Tower, 7th Floor

Central limit theorems for strcutured branching processes

Past seminar

Speaker: Nicolás Zalduendo
Centro de Modelamiento Matematico
Date: Tuesday, October 7, 2025 at 2:00 p.m. Santiago time

Abstract:

Branching processes are mathematical models for populations that evolve by random reproduction: each individual lives for some time and then gives birth to new individuals, whose lives and offspring evolve independently. When such systems are enriched with spatial or structural information—allowing individuals to move, interact, or carry traits—they form infinite-dimensional stochastic processes that capture a wide range of phenomena, from cell division to particle systems.

In this talk, I will discuss recent results on the central limit theorem (CLT) for a large class of such structured branching processes. Roughly speaking, the CLT describes how the random fluctuations around the average exponential growth of the population become Gaussian in the long run. I will first revisit the classical finite-dimensional case to build intuition, and then explain how the same ideas extend to spatially dependent and non-local models. The main novelty is that, by combining probabilistic and analytic techniques—most notably Stein’s method—we can not only prove convergence but also quantify the speed at which it happens.

 

Venue: John Von Neumann Seminar Room, CMM, Beauchef 851, North Tower, 7th Floor

Secretary Problems and Combinatorial Optimal Stopping

Past seminar

Speaker: Vasilis Livanos
Centro de Modelamiento Matematico
Date: Tuesday, September 30, 2025 at 2:00 p.m. Santiago time

Abstract: 

Secretary problems constitute a classical setting of online
decision-making, where discrete elements arrive in uniformly random
order, reveal their weight, and must be accepted or rejected
irrevocably, with the aim of maximizing a given function over the
selected set. In the most general form of the problem, we are given a
combinatorial feasibility constraint (e.g. a matroid) and the selected
set has to be feasible with respect to that constraint. In such
problems, the objective is to design algorithms which guarantee a
multiplicative factor approximation with respect to the optimal feasible
set if we knew the weights of the elements in advance. By far the most
important open problem in this area is the Matroid Secretary conjecture,
which states that there exists a constant-factor approximation algorithm
for every given matroid, and has been open for almost two decades now.

In this talk, I will introduce secretary problems, describe some
standard ideas and approaches for them, as well as present what is
probably my favourite algorithm of all time: Korula and Pal’s
1/(2e)-approximate algorithm for the graphic matroid setting (i.e.
selecting an acyclic set of edges in an undirected graph where the
weights of the edges is revealed online in uniformly random order).
Later on, if time permits, I will present some recent progress on
algorithms for the general Matroid Secretary conjecture. This talk will
be partly based on joint work with Kristóf Bérczi, José Soto and Victor
Verdugo that appeared in IPCO 2025.

 

Venue: John Von Neumann Seminar Room, CMM, Beauchef 851, North Tower, 7th Floor

Two-Edge Connectivity via Pac-Man Gluing

Past seminar

Speaker: Felix Hommelsheim
Centro de Modelamiento Matematico
Date: Monday, September 1, 2025 at 2:30 p.m. Santiago time

Abstract:  

We study the 2-edge-connected spanning subgraph (2-ECSS) problem: Given a graph $G$, compute a connected subgraph $H$ of $G$ with the minimum number of edges such that $H$ is spanning, i.e., $V(H) = V(G)$, and $H$ is 2-edge-connected, i.e., $H$ remains connected upon the deletion of any single edge, if such an $H$ exists. The $2$-ECSS problem is known to be NP-hard. In this work, we provide a polynomial-time $(\frac 5 4 + \varepsilon)$-approximation for the problem for an arbitrarily small $\varepsilon>0$, improving the previous best approximation ratio of $\frac{13}{10}+\varepsilon$.

Our improvement is based on two main innovations: First, we reduce solving the problem on general graphs to solving it on structured graphs with high vertex connectivity. This high vertex connectivity ensures the existence of a 4-matching across any bipartition of the vertex set with at least 10 vertices in each part. Second, we exploit this property in a later gluing step, where isolated 2-edge connected components need to be merged without adding too many edges. Using the 4-matching property, we can repeatedly glue a huge component (containing at least 10 vertices) to other components. This step is reminiscent of the Pac-Man game, where a Pac-Man (a huge component) consumes all the dots (other components) as it moves through a maze. These two innovations lead to a significantly simpler algorithm and analysis for the gluing step compared to the previous best approximation algorithm, which required a long and tedious case analysis.

Venue: John Von Neumann Seminar Room, CMM, Beauchef 851, North Tower, 7th Floor