Discrete and Algorithmic Mathematics Red de Matemática Discreta y Algorítmica

Sesión especial Matemática Discreta y Algorítmica (MDA), bienal RSME 2026

Equipo organizador

  • Maria Bras-Amorós, Universitat Politècnica de Catalunya

  • Pablo Candela, Instituto de Ciencias Matemáticas

  • Guillem Perarnau, Universitat Politècnica de Catalunya, Centre de Recerca Matemàtica

  • Francisco Santos, Universidad de Cantabria

Descripción
La matemática discreta estudia estructuras combinatorias o discretas, particularmente grafos, geometrías finitas, estructuras geométricas discretas y aspectos combinatorios de estructuras algebraicas y de teoría de números, y en ella los aspectos algorítmicos tienen una relevancia particular de forma natural. La sesión propuesta está auspiciada por la Red de Matemática Discreta y Algorítmica, financiada por el Ministerio de Ciencia e Innovación para el periodo 2025-2027 (RED2024-153572-T), y presentará una panorámica de la investigación actual del área en España.

Palabras clave: Matemática Discreta, Algoritmos, Combinatoria, Códigos, Geometría Discreta.

Programa

Lunes, 19 de enero

Hora Autor, Título
15:30 – 16:00 Aida Abiad (TU/Eindhoven), The eigenvalue method in coding theory
16:00 – 16:30 Alberto Espuny Díaz (U. Barcelona), Constructing structures in the budget-constrained random graph process
16:30 – 17:00 Daniel Palacín (U. Complutense Madrid), Casi periodicidad desde una perspectiva modelo-teórica

Martes, 20 de enero

Hora Autor, Título
11:00 – 11:30 Pedro A. García-Sánchez (U. Granada), Descomposición de semigrupos numéricos en semigrupos irreducibles
11:30 – 12:00 Mónica Blanco (U. Cantabria), Lattice zonotopes and the lonely runner conjecture
12:00 – 12:30 Rodrigo I. Silveira (U. Politècnica Catalunya), When simple geometry gets hard: shortest paths with algebraic obstacles
  Pausa comida
15:30 – 16:00 Anna de Mier (U. Politècnica Catalunya), Graphs with the same G-invariant but different configurations
16:00 – 16:30 Luis Pedro Montejano (U. Rovira Virgili), On Roudneff’s conjecture: advances and an interesting $k$-variant
16:30 – 17:00 Philippe Gimenez (U. Valladolid), Additive combinatorics and commutative algebra, a sumsets approach
17:00 – 17:30 Diego González-Sánchez (CNRS, IMJ-PRG), Higher-order Fourier analysis via spectral algorithms
17:30 – 18:00 Pausa café
18:00 – 18:30 Irene Gil Fernández (CEU San Pablo), An approach to Hoàng-Reed Conjecture
18:30 – 19:00 Bernardo González Merino (U. Murcia), Recent developments on large signed subset sums of vectors
  • Aida Abiad, The eigenvalue method in coding theory
    Department of Mathematics and Computer Science, Eindhoven University of Technology (TU/e),
    Department of Mathematics and Data Science, Vrije Universiteit Brussel
    a.abiad.monge@tue.nl
    Resumen In this talk, several new eigenvalue bounds on the independence number of graph powers will be presented. We will then illustrate an application of such bounds in coding theory. In particular, we will use them to estimate the maximum size of a code in the sum-rank metric, demonstrating how the spectral method can often improve the state of the art coding bounds.
  • Alberto Espuny Díaz, Constructing structures in the budget-constrained random graph process
    Departament de Matemàtiques i Informàtica, Universitat de Barcelona
    aespuny@ub.edu
    Resumen In this talk, I will present results concerning the budget-constrained random graph process introduced by Frieze, Krivelevich and Michaeli. Through this process, a player, called Builder, is presented with $t$ distinct edges of $K_n$ one by one, chosen uniformly at random. Builder may purchase at most $b$ of these edges, and must (irrevocably) decide whether to purchase each edge as soon as it is offered, and their goal is to construct a graph which satisfies a certain property. The main goal is to understand asymptotically, for a given $t=t(n)$, the optimum $b$ which suffices for Builder to construct a graph with the desired property (with high probability). I will present an overview of the state of the art in this model, discussing results concerning both spanning and local properties. For spanning properties, I will present new results about graph factors, graph covers and powers of Hamilton cycles. For local properties, I will discuss new results concerning building copies of $K_4$. Our new results solve different problems proposed by Frieze, Krivelevich and Michaeli. These results come from joint works with Frederik Garbe, Tássio Naia and Zak Smith, and with Sylwia Antoniuk, Kalina Petrova and Miloš Stojaković.
  • Daniel Palacín, Casi-periodicidad desde una perspectiva modelo-teórica
    Departamento de Álgebra, Geometría y Topología, Facultad de Ciencias Matemáticas, Universidad Complutense de Madrid
    dpalacin@ucm.es
    Resumen Los ultraproductos constituyen una herramienta básica para analizar, desde un punto de vista modelo-teórico, el comportamiento asintótico de una clase de estructuras. En un ultraproducto de grupos finitos, el ultralímite de la medida de contar normalizada induce una medida de Keisler, invariante bajo automorfismos y traslaciones, que ha desempeñado un papel crucial en los últimos años en varias aplicaciones de la teoría de modelos a la combinatoria aditiva. En esta charla, presentaré un trabajo conjunto con Amador Martin-Pizarro en el que obtenemos un resultado de casi-periodicidad modelo-teórico, relacionado con el teorema de casi-periodicidad de Croot y Sisack, para grupos arbitrarios equipados con una medida de Keisler bajo ciertas hipótesis menores. Si el tiempo lo permite, indicaré brevemente cómo utilizar este resultado para obtener una demostración no cuantitativa del teorema de Roth sobre progresiones aritméticas de longitud 3. No se presupondrá ningún conocimiento previo de teoría de modelos.
  • Pedro A. García-Sánchez, Christopher O’Neill, Descomposición de semigrupos numéricos en semigrupos irreducibles
    Departamento de Álgebra e IMAG, Universidad de Granada
    pedro@ugr.es
    Resumen Un semigrupo numérico es irreducible si no puede expresarse como la intersección de dos semigrupos numéricos que lo contengan propiamente. Cada semigrupo numérico puede expresarse como una intersección de (finitas) semigrupos numéricos irreducibles . A esas expresiones que no sean “irredundantes” las llamaremos factorizaciones en irreducibles. Mostramos que las uniones de conjuntos de longitudes de factorizaciones de semigrupos numéricos en semigrupos numéricos irreducibles son todas iguales a $\mathbb{N}_{\ge 2}$. Además, daremos algunos ejemplos de familias de semigrupos numéricos para los que el conjunto de longitudes de factorizaciones en irreducibles son intervalos (trabajo conjunto con C. O’Neill). **Referencias** [1] P. A. García-Sánchez, Factorizations into irreducible numerical semigroups, Commun. Korean Math. Soc. 40 (2025) 587–592 J. C. Rosales and M. B. Branco, Decomposition of a numerical semigroup as an intersection of irreducible numerical semigroups, Bull. Belg. Math. Soc. Simon Stevin 9 (2002), 373–381. **Agradecimientos** Esta investigación se ha llevado a cabo con la financiación del grupo FQM-343 y del Proyecto de Excelencia ProyExcel00868 de la Junta de Andalucía, el proyecto PID2022-138906NB-C21 financiado por MCIN/AEI/10.13039/501100011033 y fondos FEDER, además de por la RED2024-153572-T, financiada por la Agencia Estatal de Investigación.
  • Mónica Blanco, Francisco Santos, Lattice zonotopes and the lonely runner conjecture
    Departamento de Matemáticas, Estadística y Computación, Universidad de Cantabria
    monica.blancogomez@unican.es
    Resumen The lonely runner conjecture states that if $n$ people are running around the circle, having started at the same time at the origin and with distinct and constant running velocities, there will be, for each of the runners, a moment in time in which they are "lonely", that is, at distance at least $\frac{1}{n}$ from the others. A stronger version of the conjecture, called "shifted", allows the runners to have different starting points. It is known that there is no loss of generality in assuming the velocities to be integers, and that the conjecture can be interpreted geometrically as an obstruction property. Based on these facts, Henze and Malikiosis (2019) rephrased the conjecture (both the original and the shifted one) as a convex-geometric question on certain lattice zonotopes, which we will call LRZ (Lonely Runner Zonotopes) or sLRZ (for the shifted version). In this talk I will discuss some recent work on the study of these zonotopes, and how we are hoping this will help towards proving the conjecture, at least in some cases. **Agradecimientos** Supported by grants PID2022-137283NB-C21, funded by, MCIN/AEI/10.13039/501100011033
  • Rodrigo I. Silveira, When simple geometry gets hard: shortest paths with algebraic obstacles
    Departament de Matemàtiques, Universitat Politècnica de Cataluya
    rodrigo.silveira@upc.edu
    Resumen This talk explores two geometric shortest path problems that share a surprising trait: they are simple to state but deceptively difficult to solve. The first is the Weighted Region Problem, where the plane is subdivided into regions, each assigned a cost of traversal — some areas are “cheaper” to cross than others. The challenge is to find a shortest path according to this weighted cost. The second is the Shortest Descending Path problem, which considers a polyhedral terrain and two points, $s$ and $t$, on its surface. The goal is to compute a shortest path from $s$ to $t$ that never ascends. For both problems, no efficient algorithms are known. The underlying difficulty appears to be algebraic: computing an optimal path requires solving algebraic equations that seem computationally intractable. In this talk, I will provide a gentle introduction to these two intriguing problems, summarize what is currently known about them, and highlight how algebraic obstacles may explain why they resist efficient algorithms.
  • Anna de Mier, Joseph E. Bonin, Kerri Morgan and Lluís Vena, Graphs with the same G-invariant but different configurations
    Departament de Matememàtiques, Universitat Politècnica de Catalunya
    anna.de.mier@upc.edu
    Resumen In 1974 W. Tutte introduced the rotor construction, that allowed him to construct "codichromatic" graphs (i.e., graphs with the same Tutte polynomial) up to 5-connectivity. We show that the same construction can be applied to yield graphs with the same G-invariant, which is a valuative matroid invariant that contains, in particular, the Tutte polynomial. This is to our knowledge the first known construction of such graphs (in contrast, several examples of non-graphic matroids with the same G-invariant are known.) . However, in the case of the G-invariant it applies only for 3-connectivity. Like the Tutte polynomial, the G-invariant is a matroid invariant, and as such depends only on the cycle structure of the graph. Also as the Tutte polynomial, one does not need the full cycle structure to compute the G-invariant, it is enough to know the "configuration" of the corresponding matroid. We show that the graphs we obtain not only have different associated matroids but also have different configurations. **Agradecimientos** This work was partially supported by grant PID2023-147202NB-I00 funded by MICIU/AEI/10.13039/501100011033.
  • Luis Pedro Montejano, On Roudneff’s conjecture: advances and an interesting $k$-variant
    Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira Virgili
    luispedro.montejano@urv.cat
    Resumen J. P. Roudneff conjectured in 1991 that every arrangement of $n \ge 2d+1\ge 5$ pseudohyperplanes in the real projective space $\mathbb{P}^d$ has at most as many complete cells (i.e., cells bounded by each hyperplane) as the number of complete cells corresponding to the cyclic arrangements (i.e., the dual of the cyclic polytopes). I will talk about this conjecture and its interpretation in oriented matroid theory. I will discuss the progress of Roudneff’s conjecture and also about a $k$-variant in which the cyclic polytopes once again play an important role.
  • Ignacio García-Marco, Philippe Gimenez, Mario González-Sánchez, Additive combinatorics and commutative algebra, a sumsets approach
    Instituto de Matemáticas de la Universidad de Valladolid (IMUVA)
    pgimenez@uva.es
    Resumen Given a finite nonempty subset $\mathcal{A}$ in $\mathbb{N}^d$, for all $s\geq 0$, the set $s\mathcal{A}=\{a_1+\cdots+a_s,\ a_i\in \mathcal{A}\}$ is called the $s$-fold iterated sumset of $\mathcal{A}$. Additive combinatorics studies sumsets of $\mathcal{A}$ and their cardinality. On the other hand, if one takes a field $\mathbb{K}$ and $\mathcal{A}=\{\mathbf{a}_1,\ldots, \mathbf{a_n}\}\subset\mathbb{N}^d$, one can associate to each $\mathbf{a_i}=(a_{i1},\ldots,a_{id})$, the monomial $\mathbf{t}^{\mathbf{a}_i}=t_1^{a_{i1}}\times \cdots\times t_d^{a_{id}}\in \mathbb{K}[t_1,\ldots,t_d]$, and define the ring homomorphism $\varphi_\mathcal{A}$: $\mathbb{K}[x_1,\ldots,x_n]\rightarrow \mathbb{K}[t_1,\ldots,t_d]$, $x_i\mapsto\mathbf{t}^{\mathbf{a}_i}$. This parametrically defines a toric variety and provides a toric ideal $I_\mathcal{A}=\ker\varphi_\mathcal{A}$. Based on recent results in [1], [2], [3], [4], [5], and some work in progress, we will show how the sumsets structure of $\mathcal{A}$ is related to the syzygies and, in particular, to the Castelnuovo-Mumford regularity, of the toric ideal $I_\mathcal{A}$. This illustrates the interplay between additive combinatorics and commutative algebra, exhibiting how each area can help to solve problems in the other one. **Referencias** [1] L. Colarte-Gómez, J. Elias and R.M. Miró-Roig (2023). Sumsets and Veronese varieties. *Collect. Math.*, 74, 353–374. [2] S. Eliahou, E. Mazumdar (2022). Iterated sumsets and Hilbert functions. *J. Algebra*, 593, 274–294. [3] J. Elias (2022). Sumsets and Projective Curves. *Mediterr. J. Math.*, 19:177, 11 pp. [4] P. Gimenez and M. González Sánchez (2023). Castelnuovo-Mumford regularity of projective monomial curves via sumsets, *Mediterr. J. Math.*, 20:287, 24 pp. [5] M. González-Sánchez (2025). *Syzygies, regularity, and their interplay with additive combinatorics*. PhD Thesis, University of Valladolid. **Agradecimientos** This work was partially supported by the grant PID2022-137283NB-C22 funded by MICIU/AEI/10.13039/501100011033 and ERDF/EU.
  • Diego González-Sánchez, Pablo Candela, Balázs Szegedy, Higher-order Fourier analysis via spectral algorithms
    Centre National de la Recherche Scientifique (CNRS), IMJ-PRG
    gonzalez.sanchez.diego@renyi.hu
    Resumen Fourier analysis is a powerful tool to analyze functions defined on compact abelian groups. During the past decades, advances in additive combinatorics and ergodic theory have led to the discovery of a new form of representation theory on compact abelian groups that generalizes Fourier analysis. This theory is known as higher-order Fourier analysis. Roughly speaking, while Fourier analysis deals with representing functions in terms of harmonics such as $\exp(2\pi i \xi x)$, higher-order Fourier analysis deals with representing functions in terms of higher order harmonics such as $\exp(2\pi i\xi x^2)$. In this talk, we will introduce such a theory and a recent joint work with Candela and Szegedy which aims at bridging the gap between higher-order Fourier analysis and possible applications. **Agradecimientos** This work is supported by Horizon Europe (HORIZON) via the Marie Skłodowska-Curie Actions (MSCA) Postdoctoral Fellowship number 101202161 funded by the European Union and by project PID2024-156180NB-I00 funded by the Ministry of Science, Innovation, and Universities of Spain.
  • Irene Gil Fernández, Gaia Carenini, An approach to Hoàng-Reed Conjecture
    Universidad CEU San Pablo
    irene.gilfernandez@ceu.es
    Resumen Hoàng-Reed Conjecture states that every digraph in which each vertex has outdegree at least $k$ contains $k$ directed cycles $C_1, \dots, C_k$ such that $C_j$ meets $\bigcup_{i=1}^{j-1}C_i$ in at most one vertex, for each $2\leq j\leq k$. This conjecture was proved by M. Welhan (2010) for outdegree equal to 3, but his method does not seem to work for higher $k$. In this talk we try to show some work on progress together with G. Carenini on the resolution of this problem.
  • Bernardo González Merino, Recent developments on large signed subset sums of vectors
    Departamento de Ingeniería y Tecnología de Computadores, Universidad de Murcia
    bgmerino@um.es
    Resumen The following question arises in some topics of Mathematics: for given $d\geq 2$, $n\geq d$ and $k\leq n$, what is the largest value $c(d,n,k)$ such that from any set of $n$ unit vectors in $\mathbb R^d$, we may select $k$ vectors with corresponding signs $\pm 1$ so that their signed sum has norm at least $c(d,n,k)$? The problem in dual to classical vector sum minimization and balancing questions, which have been studied for over a century. On the one hand, we will explain most of the known results regarding both exact values of $c(d,n,k)$ for small values of the parameters as well as sharp asymptotic estimates when some of the parameters tend to infinity. On the other hand, we will briefly show some recent developments on this topic, such as the solution by F. Grundbacher to the exact computation of $c(3,4,4)=\sqrt{5}$.