LIMDA Seminar

Coming talks

Date: Thursday, 22 of January 2026

Time: 16:15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title: Words and ordered graphs

Speaker: Jaroslaw Grytczuk (Jagiellonian University)

Abstract: 

I will present some problems and results on the border between ordered graphs and combinatorics on words. The main object of our interest is a family of words that can be split into two identical subwords, so-called shuffle squares, which can be studied with the use of ordered matchings. To gain a feeling of this topic, one may try to prove that a periodic word consisting of an odd number of blocks ABBA is not a shuffle square; that is, it cannot be decomposed into two identical subwords. Another intriguing question is whether the following analog of the Necklace Splitting Theorem holds: Every k-ary word (with each letter of an alphabet occurring an even number of times) can be cut by at most k cuts so that the resulting pieces can be arranged to form a shuffle square. It is not known if any finite number of cuts is sufficient, even in the binary case.

Joint work with Bartłomiej Pawlik and Andrzej Ruciński

Date: Thursday, 5 of February 2026

Time: 16:15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title: Mixing time and diameter of the percolated hypercube

Speaker: Sahar Diskin (ETH Zürich)

Abstract:

We study bond percolation on the d-dimensional hypercube Q^d with edge retention probability p=c/d. It is well known that when c>1 is fixed, a unique giant component emerges. In this regime, we resolve long-standing conjectures of Bollobás, Kohayakawa, and Łuczak (1994) and of Benjamini and Mossel (2003), showing that the typical diameter of the giant component is Θ(d), and that the mixing time of the lazy random walk on it is Θ(d^2). In the talk, we will introduce the notion of mixing time and its connection to expansion properties of subsets of the giant. We will then discuss some of the key obstacles in obtaining this result, and in particular why classical sprinkling techniques are insufficient for this problem. Finally, we will explain how our new approach - based on analysing the effect of small perturbations and establishing stability under thinning - overcomes these obstacles. This method also yields tight large-deviation estimates for the size of the giant.  
Based on joint work with Michael Anastos, Lyuben Lichev, and Maksim Zhukovskii.

 

Previous talks

Date: Thursday, 11 of December 2025 

Time: 16:15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title: Reconstructing graphs using graphlet degree sequences

Speaker: Aneta Pokorná (Czech Academy of Sciences, Charles University)

Abstract:

Graphlets are small subgraphs rooted at a fixed vertex. The number of occurrences of graphlets aligned to a particular vertex, called graphlet degree sequence, gives a topological description of the surrounding of the analyzed vertex.

A long standing open problem in graph theory, the reconstruction conjecture, asks whether the structure of a graph is uniquely determined by its vertex-deleted subgraphs. We ask whether the structure of a graph G is uniquely determined by the graphlet degree sequences of its vertices (considering all graphlets smaller than G). We'll show that the answer is positive for graphs having certain type of asymmetric vertex-deleted subgraphs. Note that the idea of using asymmetry is novel even among the partial results for the (harder) reconstruction from vertex-deleted subgraphs.

____________________________

Date: Thursday, 4 December 2025

Time: 16:15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title: Exact enumeration of satisfiable 2-SAT formulas

Speaker: Élie de Panafieu (Nokia Labs)

Abstract:

The k-satisfiability (k-SAT) problem is a canonical constraint satisfaction problem in theoretical computer science. While k-SAT is NP-complete for k > 2 [Cook 71], it is solvable in linear time for k = 2 [Aspvall Plass Tarjan 79].

The probability for a random 2-SAT formula to be satisfiable undergoes a phase transition when the ratio of the number of clauses over the number of variables crosses 1 [Goerdt 92, Chvátal Reed 92, Fernandez de la Vega 92] and the width of the transition window is known [Bollobás Borgs Chayes Kim Wilson 1999].

In this talk, I will present results derived with Sergey Dovgal and Vlady Ravelomanana on the exact enumeration of satisfiable 2-SAT formulas and information they provide on the probability curve inside the transition window. The proofs rely on the introduction of a new type of generating functions designed specifically for the problem at hand and inspired by the generating functions developed for digraph enumeration [Robinson 77].

____________________________

Date: Thursday, 27 November 2025

Time: 16:15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title:  On the minimum degree of clique Ramsey-minimal graphs

Speaker: Yamaan Attwa (Freie Universität Berlin)

Abstract:

Following the footsteps of Folkman; Burr, Erd\H{o}s and Lovász (BEL) started the systematic study of extremal graph parameters of Ramsey graphs. Of these parameters, we are particularly interested in  $s_r(K_k)$; the smallest possible minimum degree in a graph that is $r$-Ramsey minimal to $K_k$. BEL proved that $s_2(K_k)= (k-1)^2$ for all $k \geq 2$ and since then there has been some research into this parameter as a function of both $k$ and $r$. The bulk of this talk will be dedicated to an algebraic-probabilistic construction providing upper bounds on $s_r(K_k)$ when $k\leq r \log^2 r.$ This is a a joint work with Sam Mattheus, Tibor Szabó, and Jacques Verstraete.

____________________________

Date: Thursday, 20 November 2025

Time: 16:15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title: On random regular graphs and the Kim-Vu Sandwich Conjecture

Speaker: Natalie Behague (University of Warwick)

Abstract:

The random regular graph G_d(n) is selected uniformly at random from all d-regular graphs on n vertices. This model is a lot harder to study than the Erdős-Renyi binomial random graph model G(n, p) as the probabilities of edges being present are not independent. Kim and Vu conjectured that when d ≫ log n it is possible to ‘sandwich’ the random regular graph G_d(n) between two Erdős-Renyi random graphs with similar edge density. A proof of this sandwich conjecture would unify many previous separate hard-won results.

Various authors have proved weaker versions of the sandwich conjecture with incrementally improved bounds on d — the previous state of the art was due to Gao, Isaev and McKay who proved the conjecture for d ≫ (log n)^4. I will sketch our new proof of the full conjecture.

This is joint work with Richard Montgomery and Daniel Il'kovič.

____________________________

Date: Thursday, 13 November 2025

Time: 16:15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title: The maximum diameter of d-dimensional simplicial complexes

Speaker: Silas Rathke (Freie Universität Berlin)

Abstract:

We consider the problem of Santos about finding the largest possible diameter of a strongly connected d-dimensional simplicial complex on n vertices. For d=2, we determine the answer precisely for every n by an explicit construction. For larger d, we find the optimum value for every n that is large enough. The underlying theorem can be seen as a generalization of finding a tight Euler trail in a d-uniform hypergraph. Joint work with Stefan Glock, Olaf Parczyk, and Tibor Szabó.

____________________________

Date: Thursday, 30 October 2025

Time: 16:15h (Barcelona time)

Where: Room C3-204a (Biblioteca) Campus Nord UPC and Meet link

Title: Directed graphs and bases of the Hecke algebra

Speaker: Marcos Skandera (Lehigh University)

Abstract:

The Hecke algebra has two important bases: the natural basis and the Kazhdan-Lusztig basis.  The change-of-basis matrix relating the two has entries that are polynomials {P_{v,w}(q) | v,w in S_n} in N[q] known as the Kazhdan-Lusztig polynomials. In general we have only a recursive formula for these, but when the permutation w has certain properties, we can see the coefficients in certain directed graphs.  In the talk we will assume familiarity with basic linear algebra.

____________________________

Date: Tuesday, 28 October 2025

Time: 16:15h (Barcelona time)

Where: Room C3-204a (Biblioteca) Campus Nord UPC and Meet link

Title: On modular Hadamard matrices

Speaker: Shalom Eliahou (Université du Littoral Côte d'Opale)

Abstract:

A Hadamard matrix is a square matrix with coefficients $\pm 1$ and pairwise orthogonal rows. The century-old Hadamard conjecture (1893) states that Hadamard matrices exist in every order $n$ divisible by 4. The currently smallest open cases are $n=668$, $716$ and $892$.

In the early 1970's, Marrero and Butson introduced the weaker notion of $m$-modular Hadamard matrices for any $m \ge 0$. These are still square matrices with coefficients $\pm 1$, but whose orthogonality condition on rows is only required to hold modulo $m$. The case $m=0$ corresponds to true Hadamard matrices. 
A simple but key observation is that, for any modulus $m\ge 2$, $m$-modular Hadamard matrices of order $n < m$ are true Hadamard matrices.

As follows from the classical Hadamard conjecture, $m$-modular Hadamard matrices are conjectured to exist in every order $n$ divisible by 4. The difficulty of this weaker conjecture increases sharply with $m$: while it is trivial for $m=4$, the record since 2001 stands at $m=32$.

In this talk, after recalling a few constructions of modular Hadamard matrices, we will present partial results in case $m=64$, including as yet unpublished ones. 

____________________________

Date: Thursday, 23 October 2025

Time: 16:45h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title: Graham's rearrangement for a class of semidirect products

Speaker: Simone Costa (University of Brescia)

Abstract:

A famous conjecture of Graham stated in 1971 asserts that for any set ${A \subseteq \mathbb{Z}_p \setminus \{0\}}$ there is an ordering $a_1, \ldots, a_{|A|}$ of the elements of $A$ such that the partial sums $a_1, a_1+a_2, \ldots, a_1 + a_2 + \ldots + a_{|A|}$ are all distinct. Before the recently improvements, the state of the art was essentially that the conjecture holds when $|A| \leq 12$ and when $A$ is a non-zero sum set of size $p-1$, $p-2$ or $p-3$. Many of the arguments for small $A$ use the Polynomial Method and rely on Alon’s Combinatorial Nullstellensatz. Very recently, Kravitz in [N. Kravitz. Rearranging small sets for distinct partial sums, Integers, 24 (2024)], using a rectification argument, made a significant progress proving that the conjecture holds whenever $|A| \leq \log p / \log\log p$. A subsequent paper of Bedert and Kravitz [B. Bedert, N. Kravitz. Graham’s rearrangement conjecture beyond the rectification barrier, Israel J. Math., (2025)] improved the logarithmic bound into a super-logarithmic one that is of the form $e^{c(\log p)^{1/4}}$ for some small constant $c>0$.

In [S. Costa, S. Della Fiore and E. R. Engel. Graham's rearrangement for a class of semidirect products, arXiv, (2025)], we use a similar procedure to obtain an upper bound of the same type in the case of semidirect products $\mathbb{Z}_p \rtimes_{\varphi} H$ where $\varphi: H \to Aut(\mathbb{Z}_p)$ satisfies $\varphi(h) \in \{id, -id\}$ for each $h \in H$ and where $H$ is abelian and each subset of $H$ can be ordered such that all of its partial products are distinct.

____________________________

Date: Thursday, 23 October 2025

Time: 16:15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title: Erd\H{o}s distinct-sums problem, polynomial method, probabilistic method

Speaker: Stefano Della Fiore (University of Brescia)

Abstract:

Let $\{a_1, . . . , a_n\}$ be a set of positive integers with $a_1 < \dots < a_n$ such that all $2^n$ subset sums are distinct. A famous conjecture by Erd\H{o}s states that $a_n>c\cdot 2^n$ for some constant $c$, while the best result known to date is of the form $a_n>c\cdot 2^n/\sqrt{n}$. In this talk, we give an overview on the different methods that have been used, during the past years, to provide some nontrivial lower bounds on $a_n$ (see [Elk, Erd, DFX]). Then,  inspired by an information-theoretic interpretation,  in [CDD],  we extend the study to vector-valued elements $a_i\in \mathbb{Z}^k$ and we weaken the condition by requiring that only sums corresponding to subsets of size smaller than or equal to $\lambda n$ be distinct.  For this case, we derive lower and upper bounds on the smallest possible value of $a_n$.

[CDD] S.  Costa,  M.  Dalai and S.  Della Fiore,  Variations on the Erdős distinct-sums problem, Discr. App.   Math.  325 (2023), 172--185.
[Elk] N. D. Elkies, An improved lower bound on the greatest element of a sum-distinct set of fixed order, J. Combin.
Theory Ser. A 41 (1986), 89--94.
[Erd] P. Erd\H{o}s, Problems and results in additive number theory, Colloque sur la Theorie des Nombres, Bruxelles (1955), 127--137.
[DFX] Q. Dubroff, J. Fox and M. Wenqiang Xu, A note on the Erd\H{o}s distinct subset sums problem, SIAM J. Discret. Math. 35 (2021), 322--324.

____________________________

Date: Thursday, 16 October 2025

Time: 16:15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title: Two generalisations of separating path systems

Speaker: Georgios Kontogeorgiou (Universidad de Chile)

Abstract:

Let $G$ be an arbitrary graph on $n$ vertices. Given two edges $e$ and $f$ in $G$, we say that a subgraph $H$ of $G$ separates $e$ from $f$ if $H$ contains $e$ but does not contain $f$. It was conjectured by Katona (2013), and proved by Bonamy, Botler, Dross, Naia and Skokan (2023), that there is a family of only $O(n)$ paths that together separate all the edges of $G$ from each other. In this talk, we will consider the following generalisations of this problem.

- Given an arbitrary graph $H$, can we separate the edges of $G$ with only O(n) subdivisions of $H$ (and single edges)? We will answer this in the affirmative.
- Suppose that we want a multiset of paths that not only separates the edges of $G$, but that can also be coloured with $k$ colours so that every two edges are separated by a pair of paths of distinct colours. How large must such a multiset be? We will discover the optimal values for some families of graphs and all $k\in\mathbb{N}$, and we will examine the behaviour of these values as $k\rightarrow\infty$.

____________________________

Date: Thursday, 9 October 2025

Time: 16:15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title: Hitting times and the power of choice for random geometric graphs

Speaker: Dawid Ignasiak (TU Vienna)

Abstract:

We consider a random geometric graph process where random points $(X_i)_{i\ge 1}$ are embedded consecutively in the $d$-dimensional unit torus $\mathbb T^d$, and every two points at distance at most $r$ form an edge. As $r\to 0$, we confirm that well-known hitting time results for $k$-connectivity (with $k\ge 1$ fixed) and Hamiltonicity in the Erd\H{o}s-R\'enyi graph process also hold for the considered geometric analogue. Moreover, we exhibit a sort of probabilistic monotonicity for each of these properties. 

We also study a geometric analogue of the power of choice where, at each step, an agent is given two random points sampled independently and uniformly from $\mathbb{T}^d$ and has to add exactly one of them to the already constructed point set. When the agent is allowed to make their choice with the knowledge of the entire sequence of random points (offline 2-choice), we show that they can construct a connected graph at the first time $t$ when none of the first $t$ pairs of proposed points contains two isolated vertices in the graph induced by $(X_i)_{i=1}^{2t}$, and maintain connectivity thereafter. We also derive analogous results for $k$-connectivity and Hamiltonicity. This shows that each of the said properties can be attained two times faster (time-wise) and with four times fewer points in the offline 2-choice process compared to the 1-choice process.

In the online version where the agent only knows the process until the current time step, we show that $k$-connectivity and Hamiltonicity cannot be significantly accelerated (time-wise) but may be realised on two times fewer points compared to the 1-choice analogue.

Based on joint work with Lyuben Lichev.

____________________________

Date: Tuesday, 30 September 2025

Time: 16:15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title: A graph energy conjecture through the lenses of semidefinite programming

Speaker: Emanuel Juliano (Universidade Federal de Minas Gerais)

Abstract:

The energy of a graph is defined as the sum of the absolute values of its adjacency eigenvalues. This graph parameter was introduced by Gutman (1978), motivated by applications in molecular chemistry. Since its origin, Gutman asked which graphs on n vertices have maximal energy and conjectured this maximal is achieved by the complete graph, a claim soon disproved by Godsil (1981). Later, Koolen and Moulton (2001) answered the question by providing an infinite family of strongly regular graphs with maximal energy.

The question of which graph on n vertices has the minimal energy, on the other hand, is trivial, as the empty graph has energy 0. Using Graffiti, Fajtlowicz conjectured in the 1980s that if the size of the largest independent set is fixed, then the complete balanced multipartite graphs are those with minimum energy. That is, if G is a graph on n vertices with independence number alpha, then the energy of G is at least 2(n - alpha).

In this talk, we take a step towards Fajtlowicz's conjecture. By formulating the graph energy as a semidefinite program, we show that the energy is lower bounded by 2(n - chi_f), where chi_f is the fractional chromatic number. As a byproduct of the SDP formulation, we obtain several lower bounds for the graph energy that improve and refine previous results by Hoffman (1970) and Nikiforov (2007).

____________________________

Date: Tuesday, 16 September 2025

Time: 15:00h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title: Optimal Linear Functional-Repair Regenerating Storage Codes

Speaker: Henk D.L. Hollmann (University of Tartu)

Abstract:

The amount of data in need of storage keeps increasing at an astonishing rate. Therefore it is of paramount importance to develop methods to store all this data in a reliable, efficient, and economically feasible way. In modern storage systems, the data storage is handled by a Distributed Storage System (DSS). Typically, a DSS stores data in encoded form accross a number of storage units, often referred to as storage nodes. So a DSS employs redundancy to be able to handle the occasional loss of a storage node. Often, a DSS simply employs replication. But many modern DSS employ non-trivial erasure codes (for example based on Reed-Solomon codes), especially to store “cold” data (data that remains unchanged, for example for archiving purposes, but sometimes even for “lukewarm” data (data that needs only occasional updating). An obvious requirement is that at any time, the original data can be reconstructed from the data stored by the storage nodes.

In this talk, we will discuss various aspects of storage codes, including the cut-set bound that describes optimal codes, and discuss the construction of some new optimal codes based on a new type of “regular” configuration of subspaces of a vector space over a finite field.

(In part, joint work with Junming Ke and Ago-Erik Riet)

A longer version of this abstract can be found here. 

____________________________

____________________________