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.