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

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

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

Speaker:  Kitty Varga
Budapest University of Technology and Economics
Date: Monday, June 30, 2025 at 2:30 p.m. Santiago time

Abstract:  

Inverse and reverse optimization problems aim to adjust the objectivefunction of an underlying optimization problem while minimizing the extent of modification. In inverse optimization, the goal is to modify the objective function so that a given feasible solution becomes optimal. In reverse optimization, the goal is to modify the objective function so that the optimum value attains a specified number.

In this talk, we mainly focus on inverse maximum-capacity optimization problems under the bottleneck Hamming distance, the weighted infinity norm and weighted span objectives. Our main contributions include simple, purely combinatorial algorithms that efficiently solve these general problems, assuming that an efficient algorithm is available for the underlying optimization problem.

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

Speaker:  Juan Pablo Contreras Fernández
Universidad Diego Portales
Date: Monday, June 16, 2025 at 2:30 p.m. Santiago time

Abstract:  

In this talk, we present a survey of techniques and results on error bounds and convergence rates for both deterministic and stochastic fixed-point iterations, with a focus on methods such as the Krasnoselskii-Mann and Halpern iterations. Our primary emphasis is on general normed spaces, where we employ tools from optimal transport to derive tight error bounds. For spaces with additional structure, such as Hilbert spaces, we also discuss existing techniques and the sharp results established in the literature. Finally, we highlight applications of these findings in reinforcement learning and optimization, and outline open questions and potential directions for future research.

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

Speaker:  Haritha Cheriyath
Center for Mathematical Modeling, U. de Chile
Date: Monday, June 02, 2025 at 2:30 p.m. Santiago time

Abstract:  

A dynamical system is usually made up of a state space and a rule (a map acting on the space) that tells us how the system evolves over time. One of the central questions in studying these systems is figuring out when two of them are essentially the same, or conjugate, as we usually say. There are several known features, called invariants, that stay the same under conjugacy, but so far, no single invariant can completely characterize when two systems are conjugate.

Because of that, it is natural to look at a slightly weaker idea of equivalence, called strong orbit equivalence. All conjugate systems turn out to be strongly orbit equivalent, and what is nice is that, in this setting, a complete invariant does exist.

In this talk, we will take a look at some familiar invariants from the world of conjugacy and see how they behave in the context of strong orbit equivalence.

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

Speaker:  Svenja Griesbach
Center for Mathematical Modeling, U. de Chile
Date: Monday, May 19, 2025 at 2:30 p.m. Santiago time

Abstract:  

In the impartial selection problem, a subset of agents up to a fixed size k among a group of n is to be chosen based on votes cast by the agents themselves. A selection mechanism is impartial if no agent can influence its own chance of being selected by changing its vote. It is \alpha-optimal if, for every instance, the ratio between the votes received by the selected subset is at least a fraction of \alpha of the votes received by the subset of size k with the highest number of votes.
We study deterministic impartial mechanisms in a more general setting with arbitrarily weighted votes and provide the first approximation guarantee, roughly 1/\lceil 2n/k\rceil. When the number of agents to select is large enough compared to the total number of agents, this yields an improvement on the previously best known approximation ratio of 1/k for the unweighted setting. We further show that our mechanism can be adapted to the impartial assignment problem, in which multiple sets of up to k agents are to be selected, with a loss in the approximation ratio of 1/2.

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

Speaker:  Christopher Cabezas
Center for Mathematical Modeling, U. de Chile
Date: Monday, April 21, 2025 at 2:30 p.m. Santiago time

Abstract:  

An important question in dynamical systems is the classification, i.e., to be able to distinguish two isomorphic dynamical systems. In this work, we focus on the family of multidimensional substitutive subshifts. Constant-shape substitutions are a multidimensional generalization of constant-length substitutions, where any letter is assigned a pattern with the same shape. We prove that in this class of substitutive subshifts, under the hypothesis of having the same structure, it is decidable whether there exists a factor map between two aperiodic minimal substitutive subshifts. The strategy followed in this work consists in giving a complete description of the factor maps between these substitutive subshifts. We will also discuss related results, such as a condition to ensure that the substitution defines a subshift, and some consequences on coalescence, automorphism group and number of symbolic factors. This is a joint work with Julien Leroy.

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

Speaker:  Mirabel Mendoza
Center for Mathematical Modeling, U. de Chile
Date: Monday, March 31, 2025 at 2:30 p.m. Santiago time

Abstract:  

We consider the Shortest Odd Path (SOP) problem, where given an undirected graph $G$, a weight function on its edges, and two vertices $s$ and $t$ in $G$, the aim is to find an $(s,t)$-path with odd length and, among all such paths, of minimum weight. For the case when the weight function is conservative, i.e., when every cycle has non-negative total weight, the complexity of the SOP problem had been open for 20 years, and was recently shown to be NP-hard. I’ll present a polynomial-time algorithm for the special case when the weight function is conservative and the set of negative-weight edges forms a single tree. The algorithm exploits the strong connection between SOP and the problem of finding two internally vertex-disjoint paths between two terminals in an undirected edge-weighted graph. This is a joint work with Alpár Jüttner, Csaba Király, Gyula Pap, Ildikó Schlotter, and Yutaro Yamaguchi.

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

Speaker:  María Fernanda Espinal
Center for Mathematical Modeling, U. de Chile
Date: Monday, March 17, 2025 at 2:30 p.m. Santiago time

Abstract:  

The Yamabe problem is a classical question in conformal geometry that seeks for existence of metrics with constant scalar curvature within a conformal class. The problem was posed by H. Yamabe in 1960 as a possible extension of the famous uniformization theorem, which states that every simply connected Riemann surface is conformally equivalent to the open unit disk, the complex plane or the Riemann sphere. After the conjecture was already confirmed by the work of R. Schoen, an alternative approach was proposed by R.Hamilton in 1989. He suggested to use a geometric flow, which is now known as the Yamabe flow. The k-Yamabe flow is a fully non-linear extension to the Yamabe flow that appears naturally in problems related to topological classification in higher dimensions. In this talk we describe the construction, classification and asymptotic behavior of radially symmetric gradient k-Yamabe solitons that are locally conformally flat [ES24], these are special solutions to this flow that play a central role in the theory. Our study extends the results obtained by P. Daskalopouolos and N. Sesum in [DS13] in the case n > 2k.

Joint work with Mariel Sáez.

References
[DS13] Panagiota Daskalopoulos and Natasa Sesum. The classification of locally conformally flat yamabe solitons. Advances in Mathematics, 240:346–369, 2013.
[ES24] Mar´ıa Fernanda Espinal and Mariel S´aez. On the existence and classification of k-yamabe gradient solitons. arXiv preprint arXiv:2410.06942, 2024.

Venue: Jacques L Lions Seminar Room, CMM, Beauchef 851, North Tower, 7th Floor