Barcelona Discrete Mathematics Meeting 2025 (BDMM)

Abstract

In this talk, we discuss the existence of rainbow 3-term arithmetic progressions within 3-colorings of various ground sets, including finite intervals, cyclic groups, and general abelian groups. This foundational question—how rainbow structures emerge under specific density conditions on color classes—has inspired a wealth of insights, problems, and generalizations within Rainbow Ramsey Theory.

Abstract

In circuit complexity a magnification result infers an apparently strong circuit lower bound from an apparently weak one. The talk presents a general method how to prove such results. It relies on so-called distinguishers: binary matrices that are sparse but retain some properties of error correcting codes.

Abstract

In this talk we will present a general theory that allows us to obtain bounds for the total variation distance between multivariate integer-valued random vectors and a Poisson random vector based on the  notion of multivariate size-bias coupling. We will apply these bounds to a vector that counts the number of graphs that are isomorphic to a vector of distinct subgraphs of a Erdös-Rény graph with edge probability that converges to zero as the number of vertices converges to infinity. This talk is based on a joint work with Rui Zhang.

Abstract

We consider the non-crossing straight-line spanning trees on a finite point set in the plane. A flip is a transformation of one such tree into another by means of exchanging exactly one edge. In this talk we consider the flip graph whose vertices are the non-crossing trees and edges are the flips. In particular we are interested in the case of n points in convex position and the diameter of the corresponding flip graph in terms of n. We present improved upper and lower bounds of 14/9 n and 5/3 n, respectively. –This is joint work with Havard Bjerkevik, Linda Kleist, and Birgit Vogtenhuber.

Abstract

Discrete Potential Theory is the study of harmonic functions, and then the Laplace equation, on graphs and networks. From the very beginning, the Matrix Analysis and Potential Theory (MAPTHE) group has tried, and has been successful, to place the discrete-continuum relationship of potential theory on a solid theoretical background, both in graph theory, and more generally in network setting, that configure a Discrete Vector Calculus mimetic to the differentiable one. Very recent papers, emphasize the use of Discrete Vector Calculus in different problems, including the analysis of Random Walks, Big Data problems or the treatment of truss structures in mechanics. We are convinced that our approach is suitable to establish an analogy with the continuous model. In fact, the mentioned analogy and our methods, have allowed us to introduce new techniques on the analysis of some discrete problems and even to raise problems that at first only have sense if they are compared with their continuous analogue. Specifically, the statement and solution of general boundary value problems (BVP), with general elliptic operators on a network, represent the main subject of the group. The study of BVP by MAPTHE group includes both aspects, the direct problem and the inverse one, that contribute to an efficient resolution of problems such as implementation of Electrical Impedance Tomography (EIT) techniques on cancer detection, and diffusion issues in networks where Random Walks represent a mathematical model and can be used to extract information about important issues in networks. These are the actual two research lines of the MAPTHE group, but in this talk we focus on the first one. For health issues, EIT represents a non-invasive and radiation-free imaging technique for recovering the conductivity distribution inside the body under observation from skin surface measurements. Besides, EIT is known to be a groundbreaking area of research because its low cost and portable instrumentation. It is well known that this problem is severely ill-posed, especially if complex networks are considered. Therefore, new algorithms to overcome this structural difficulty are necessary. Using discrete techniques, we are verifying that the design of stable algorithms for the recovery of conductances can be achieved through an optimization process. As a consequence, we can improve existing EIT techniques for clinical diagnosis.

Abstract

The lonely runner conjecture (LRC) is the following statement formulated by Jörg Wills in 1968: 

If $n$ “runners’’ move along a circle of length one, all starting at the origin, each with its own (constant) velocity, then there is a time at which they are all at distance at least $1/(n+1)$ from the origin. 

In its shifted version (sLRC) the runners are allowed to start each at a different position and the velocities are assumed distinct (or else giving all runners the same velocity produces an easy counter-example). The conjecture has been approached from different perspectives, and is proved until $n=6$ in the original version (Barajas and Serra 2008) and $n=3$ in the shifted version (Cslovjecsek et al. 2022). The latter is based in a reformulation of LRC and sLRC as questions about the covering radii of certain zonotopes, developed by Henze, Malikiosis and Schymura (2017).

In this talk I will review the conjecture and its relation to zonotopes and their covering radii, and will show that, both in the original and the shifted versions, if the conjecture holds for integer velocities adding up to at most $n^{2n}$ then it holds for arbitrary velocities. This is based in joint work with Romanos Malikiosis and Matthias Schymura, and it improves a recent result of terence Tao, who proved the same with a bound of $n^{Cn^2}$ instead.