2024-25 LIMDA Seminar

Date: Thursday, 12 June 2025

Aquest seminari es realitza en el marc del Pla de Recuperació, Transformació i Resiliència,  l'instrument fonamental per al desplegament dels fons europeus de recuperació (Next Generation EU). Aquest pla traça el full de ruta per a la modernització de l'economia espanyola, la recuperació del creixement econòmic i la creació d'ocupació després de la crisi del Covid-19, així com per preparar al país per afrontar els reptes de la propera dècada.

Date: Tuesday, 13 May 2025

Time: 14:00h (Barcelona time)

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

Title: Boolean Circuit Complexity and Two-Dimensional Cover Problems

Speaker: Bruno Pasqualotto Cavalar  (University of Toronto)

Abstract:

Date: Thursday, 24 April 2025

Time: 16:15h (Barcelona time)

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

Title: Progressive and rushed Dyck paths

Speaker: Axel Bacher (LIPN, Université Sorbonne Paris Nord)

Abstract:

Date: Thursday, 3 April 2025

Time: 16:15h (Barcelona time)

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

Title: Typical Ramsey properties of the primes and abelian groups

Speaker: Robert Hancock (University of Oxford)

Abstract:

Date: Thursday, 27 March 2025

Time: 16:15h (Barcelona time)

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

Title: Spectrahedral Shadows and Completely Positive Maps on Real Closed Fields

Speaker: Manuel Bodirsky (TU Dresden)

Abstract:

In this article we develop new methods for exhibiting convex semialgebraic sets that are not spectrahedral shadows. We characterize when the set of nonnegative polynomials with a given support is a spectrahedral shadow in terms of sums of squares. As an application of this result we prove that the cone of copositive matrices of size $n\geq 5$ is not a spectrahedral shadow, answering a question of Scheiderer. Our arguments are based on the model theoretic observation that any formula defining a spectrahedral shadow must be preserved by every unital $\mathbb{R}$-linear completely positive map $R\to R$ on a real closed field extension $R$ of $\mathbb{R}$.

Date: Thursday, 13 March 2025

Time: 16:15h (Barcelona time)

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

Title: The Natural Matroid of an Integer Polymatroid as a Source of Insights and New Problems

Speaker: Joe Bonin (George Washington University)

Abstract:

After recalling some basic concepts in matroid theory and using matroids to motivate integer polymatroids, we will discuss the natural matroid of an integer polymatroid.  The natural matroid was introduced in the 1970s to show that all integer polymatroids can be represented by identifying its elements with sets of elements in a matroid.  We will then show how the natural matroid provides a way to translate axiom schemes from matroids to integer polymatroids.  Lastly, we will explore some new classes of polymatroids that arise from the following result: if $\mathcal{C}$ is a minor-closed class of matroids, then the class of polymatroids having their natural matroid in $\mathcal{C}$ is minor-closed.  This opens up new research questions such as: what are the excluded minors for the class of $2$-polymatroids whose natural matroids are binary, or are direct sums of series-parallel networks?

This talk includes joint work with Carolyn Chun and Tara Fife, joint work with Kevin Long, and work of Fiona Young.

Date: Tuesday, 11 March 2025

Time: 15:00h (Barcelona time)

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

Title: Asynchronous Majority Dynamics on Binomial Random Graphs

Speaker: Pavel Pralat (Toronto Metropolitan University)

Abstract:

We study information aggregation in networks when agents interact to learn a binary state of the world. Initially each agent privately observes an independent signal which is correct with probability $1/2+\delta$ for some $\delta > 0$. At each round, a node is selected uniformly at random to update their public opinion to match the majority of their neighbours (breaking ties in favour of their initial private signal). Our main result shows that for sparse and connected binomial random graphs $G(n,p)$ the process stabilizes in a correct consensus in $O(n\log^2 n/\log\log n)$ steps with high probability. In fact, when $\log n/n \ll p = o(1)$ the process terminates at time $\hat T = (1+o(1))n\log n$, where $\hat T$ is the first time when all nodes have been selected at least once. However, in dense binomial random graphs with $p=\Omega(1)$, there is an information cascade where the process terminates in the incorrect consensus with probability bounded away from zero.

Date: Thursday, 20 February 2025

Time: 16:15h (Barcelona time)

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

Title: Classifying numerical semigroups using polyhedral geometry

Speaker: Christopher O'Neill (San Diego State University)

Abstract:

A numerical semigroup is a subset of the natural numbers that is closed under addition.  There is a family of polyhedral cones C_m, called Kunz cones, for which each numerical semigroup with smallest positive element m corresponds to an integer point in C_m.  It has been shown that if two numerical semigroups correspond to points in the same face of C_m, they share many important properties.  In this way, the faces of the Kunz cones naturally partition the set of all numerical semigroups into "cells" within which any two numerical semigroups have similar algebraic structure.  

In this talk, we survey what is known about the face structure of Kunz cones, and how studying Kunz cones can inform the classification of numerical semigroups.  No familiarity with numerical semigroups or polyhedral geometry will be assumed for this talk.

Aquest seminari es realitza en el marc del Pla de Recuperació, Transformació i Resiliència,  l'instrument fonamental per al desplegament dels fons europeus de recuperació (Next Generation EU). Aquest pla traça el full de ruta per a la modernització de l'economia espanyola, la recuperació del creixement econòmic i la creació d'ocupació després de la crisi del Covid-19, així com per preparar al país per afrontar els reptes de la propera dècada.

Date: Thursday, 6 February 2025

Time: 16:15h (Barcelona time)

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

Title: Simultaneous edge-colourings

Speaker: Richard Lang (UPC)

Abstract:

An old result of Vizing concerns the number of colours required for a proper edge-colouring of a graph. More recently a related question has been studied, where the goal is to simultaneously colour the edges of multiple graphs with as few colours as possible. In this talk, I will give an introduction to the general topic and then present some  progress on the matter.

Date: Wednesday, 29 January 2025

Time: 16:15h (Barcelona time)

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

Title: Minimal graph rigidity is in NC for K_{3,3}-free and K_5-free graphs

Speaker: Kilian Rothmund (Aalen Univerisity)

Abstract:

A graph is minimal rigid in the plane if it admits a so-called infinitesimal rigid embedding while having the minimum number of edges. We consider two problems: First, we want to decide whether a graph is minimal rigid. Second, we want to compute infinitesimal rigid embeddings for minimal rigid graphs. Both problems can be solved in polynomial time and there is also an efficient randomized parallel (RNC) algorithm. In this talk I will present efficient deterministic parallel (NC) algorithms for the two problems when the input graph does not have a K_{3,3} minor. I will also present an NC algorithm for the first problem when the input graph does not have a K_5 minor. The algorithms work by decomposing the input graphs into planar components. Planar minimally rigid graphs have a geometric characterization by Streinu and Haas et al. and we will begin with the observation that this characterization yields deterministic NC algorithms for the planar case.

Based on joint work with Rohit Gurjar and Thomas Thierauf.

Date: Thursday, 19 December 2024

Time: 16:15h (Barcelona time)

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

Title: Eigenvalue bounds for the independence number of graph powers and an application to coding theory

Speaker: Aida Abiad (Eindhoven University of Technology and Vrije Universiteit Brussel)

Abstract:

In this talk, eigenvalue bounds on the independence number of graph powers will be presented. We will then use such eigenvalue bounds to estimate the maximum size of a code in the sum-rank metric, illustrating how the spectral method can often improve the state of the art coding bounds.

Date: Thursday, 12 December 2024

Time: 16:15h (Barcelona time)

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

Title: Multicolour Ramsey numbers

Speaker: Simon Griffiths (PUC-Rio)

Abstract:

In this talk we discuss recent results on Ramsey numbers and multicolour Ramsey numbers, including the exponential improvement on the upper bound.

Based on joint work with Paul Balister, B\'ela Bollob\'as, Marcelo Campos, Eoin Hurley, Robert Morris, Julian Sahasrabudhe and Marius Tiba.

Date: Thursday, 5 December 2024

Time: 16:15h (Barcelona time)

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

Title: Asymptotic expansion of regular graphs

Speaker: Élie de Panafieu (Nokia Labs)

Abstract:

A graph is regular if all its vertices have the same degree. Progress in the exact and asymptotic enumeration of regular graphs has involved a variety of techniques, including probabilistic methods, generating functions, and computer algebra. In particular, differential equations characterizing the generating function of k-regular graphs have been computed for the first few values of k. We present a new exact formula enumerating graphs with their degrees constrained to belong to a given set. Our approach is based on generating function manipulations and extends to many graph variants, including bipartite graphs. Applying the Laplace method, we deduce the asymptotic expansion (unbounded number of error terms) of k-regular graphs, confirming a conjecture from Brendan Mckay (1983).

Date: Thursday, 28 November 2024

Time: 16:15h (Barcelona time)

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

Title: Some elementary algebraic methods in the study of zero-sum theorems.

Speaker: Sukumar Das Adhikari (RKMVERI)

Abstract:

Consider  a finite abelian group $G$ (written additively). A sequence $S=g_1 \cdot \ldots \cdot g_l$ over $G$ is called a {\it zero-sum sequence} if $g_1+\cdots +g_l =0,$ where $0$ is the identity element of the group. Inspired by a well known result of Erd\H{o}s, Ginzburg and Ziv, the area of zero-sum theorems in combinatorial number theory has seen a rapid growth in  recent years.

The area of zero-sum theorems has many interesting results and several unanswered questions. Several authors have introduced interesting elementary algebraic techniques to deal with these problems. We describe some experiments with these elementary algebraic methods and some combinatorial ones, in a weighted generalization in  the area of Zero-sum Combinatorics.

Date: Monday, 25 November 2024

Time: 15:00h (Barcelona time)

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

Title: The Heilbronn triangle problem

Speaker: Cosmin Pohoata (Emory University)

Abstract:

The Heilbronn triangle problem is a classical problem in discrete geometry with several old and new connections to various topics in extremal and additive combinatorics, graph theory, incidence geometry, harmonic analysis, and projection theory. In this talk, we will give an overview of some of these connections, and discuss some recent developments. Based on joint work with Alex Cohen and Dmitrii Zakharov.

Date: Friday, 22 November 2024

Time: 15:00h (Barcelona time)

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

Title: Color avoidance for monotone paths

Speaker: Eion Mulrenin (Emory University)

Abstract:

Ten years ago, Moshkovitz and Shapira determined the tower height for hypergraph Ramsey numbers of tight monotone paths. We address the color-avoiding version of this problem in which one no longer necessarily seeks a monochromatic subgraph, but rather one which \textit{avoids} some colors. This problem was previously studied in uniformity two by Loh and by Gowers and Long. We show, in general, that the tower height for such Ramsey numbers requires one fewer exponential than in the usual setting. The transition occurs at uniformity three, where the usual Ramsey numbers of monotone paths of length $n$ are exponential in $n$, but the color-avoiding Ramsey numbers turn out to be polynomial. Joint work with Cosmin Pohoata and Dmitrii Zakharov.

Date: Tuesday, 31 October 2024

Time: 16:15h (Barcelona time)

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

Title: On the chromatic symmetric function, the generalized degree sequence and the subtree sequence

Speaker: José Aliste (Universidad Andrés Bello)

Abstract:

R. Stanley asked whether a tree is determined up to isomorphism by its chromatic symmetric function. We approach this question by studying the relationship between the chromatic symmetric function and other invariants. We will study the generalized degree sequence, which enumerates vertex subsets by cardinality and the numbers of internal and external edges and the subtree sequence, which enumerates subtrees by cardinality and number of leaves.  We will show that the chromatic symmetric function determines the generalized degree sequence, and that the generalized degree sequence determines the subtree sequence, thus proving a conjecture of Logan Crew and improving on previous results by Jeremy L. Martin, Matthew Morin and Jennifer Wagner.

Date: Thursday, 31 October 2024

Time: 15:15h (Barcelona time)

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

Title: Counting spanning structures in dense graphs

Speaker: Matías Pavez-Signé (Universidad de Chile)

Abstract:

In this talk, I will introduce a simple (though effective) technique for estimating the number of copies of some classes of spanning subgraphs in graphs and hypergraphs satisfying certain degree conditions. In particular, this can be used to estimate the number of perfect matchings in hypergraphs with minimum degree above the existence threshold.

This is joint work with Richard Montgomery.

Date: Thursday, 24 October 2024

Time: 16:15h (Barcelona time)

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

Title: Laplacians and colors for graphs and hypergraphs

Speaker: Raffaella Mulas (Vrije Universiteit Amsterdam)

Abstract:

In the first part of the talk, we will discuss some properties of the normalized Laplacian for graphs and hypergraphs, as well as an application to networks of genetic expression. We will then discuss the non-backtracking Laplacian for graphs, and examine connections between Laplacians and coloring numbers.

Date: Thursday, 24 October 2024

Time: 15:15h (Barcelona time)

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

Title: The fractional chromatic number of the plane is at least 4

Speaker: Mate Matolcsi (Rényi Institute of Mathematics)

Abstract:

We prove that the fractional chromatic number of the unit distance graph of the Euclidean plane is greater than or equal to 4. This improves a series of earlier lower bounds edging closer to 4 over the past decades. A fundamental ingredient of the proof is the notion of geometric fractional chromatic number introduced recently in connection with the density of planar 1-avoiding sets. In the proof we also exploit the amenability of the group of Euclidean transformations in dimension 2.

Date: Tuesday, 22 October 2024

Time: 15:00h (Barcelona time)

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

Title: Bi-eulerian embeddings of dense graphs and digraphs

Speaker: Jo Ellis-Monaghan (University of Amsterdam)

Abstract:

When can a graph or digraph be cellularly embedding in a orientable surface so that it has exactly two faces, each bounded by an euler circuit? Is it possible to specify one of the euler circuits in advance? When is it possible to specify an arbitrary circuit decomposition of the edges and complete it to an embedding with just one more face, noting that this face is then necessarily bounded by an euler circuit?  Finding such a face achieves a maximum genus embedding  having the  circuits in a given decomposition as facial walks.

This leads more generally to the question of determining the maximum genus of an embedding relative to a circuit decomposition. Beyond topological graph theory, these questions arise in surprisingly diverse settings, including DNA self-assembly, Steiner triple systems, and latin squares.

We prove that if an eulerian (di)graph is sufficiently dense, then it is indeed always possible to achieve these special embeddings of maximum orientable genus.

This is joint work with Mark Ellingham.

Date: Thursday, 17 October 2024

Time: 16:15h (Barcelona time)

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

Title: Unavoidable bichromatic patterns in $2$-edge-colorings of the complete graph

Speaker: Amanda Montejano (Universidad Nacional Autónoma de México)

Abstract:

We study the color patterns that, for $n$ sufficiently large, are unavoidable in $2$-colorings of the edges of a complete graph $K_n$ with respect to $\min \{e(R), e(B)\}$, where $e(R)$ and $e(B)$ are the numbers of red and blue edges, respectively. More precisely, we completely characterize which patterns are unavoidable depending on the order of magnitude of $\min \{e(R), e(B)\}$ (in terms of $n$), and show how these patterns evolve from the case without restriction in the coloring, namely that $\min \{e(R), e(B)\} \ge 0$ (given by Ramsey's theorem), to the highest possible restriction, namely that $|e(R) - e(B)| \le 1$. This is a joint work with Adriana Hansberg and Yair Caro.

Date: Thursday, 26 September 2024

Time: 16:15h (Barcelona time)

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

Title: First-Fit Coloring of Forests in Random Arrival Model

Speaker: Bartłomiej Bosek (Jagiellonian University)

Abstract:

We consider a graph coloring algorithm that processes vertices in order taken uniformly at random and assigns colors to them using First-Fit strategy. We show that this algorithm uses, in expectation, at most (1+o(1))⋅ln(n)/lnln(n) different colors to color any forest with n vertices. We also construct a family of forests that shows that this bound is best possible. 

Join work with Grzegorz Gutowski, Michał Lasoń, Jakub Przybyło.

Date: Thursday, 26 September 2024

Time: 15:00h (Barcelona time)

Where: Sala d'Actes Manuel Martí Recober, B6, Campus Nord UPC

Title: Theory, Algorithms and Applications of Linear Arrangements of Trees: Generation, Expectation and Optimization

Ph.D. Defense: Lluís Alemany Puig (UPC)

Advisor: Ramon Cancho Ferrer (UPC)

Abstract:

A successful approach to represent the syntactic structure of sentences in Computational Linguistics, founded in the theory developed by Tesnière, is that of syntactic dependency tree. Pairs of vertices of syntactically-related words are joined with an edge that carries a label which indicates the type of syntactic relationship. When words and syntactic relationships are abstracted away, by removing the vertex labels and removing the edge labels with the type of syntactic relationship, we are left with a so-called linearized tree. A linearized tree is simply a rooted tree in conjunction with a linear arrangement. And a linear arrangement of a graph is a permutation of the graph's vertices, and can be represented by drawing the vertices on a horizontal line and the edges as semicircles above it.

There exist many computational problems that involve linear arrangements of graphs. Remarkable examples are those that look for an arrangement $\pi$ that optimize the sum of edge lengths, where the length of an edge $uv$ is defined as $|\pi(u) - \pi(v)|$. The problem that minimizes this sum is known as the minimum Linear Arrangement problem (minLA). When one maximizes the sum of edge lengths, the problem is known as the Maximum Linear Arrangement problem (MaxLA). In an attempt to provide a theory of word order, language researchers put forward the now well-known Dependency Distance minimization principle after observing and providing large-scale evidence of the tendency in languages to minimize the total sum of edge lengths in the syntactic dependency trees of their sentences. In order to provide an exhaustive theory of word order, some language researchers have also argued that MaxLA manifests itself in languages in substructures of the syntactic dependency trees isomorphic to a star graph.

Both minLA and MaxLA are known to be NP-Hard on general graphs, and only minLA is known to be solvable in polynomial time on trees. In this thesis we contribute with optimal algorithms to solve several constrained variants of both minLA and MaxLA. We study these two problems for bipartite graphs under the constraint that vertices have to be arranged in two disjoint intervals according to the vertex partition they belong (bipartite arrangements). These are also studied for free trees under the constraint that edges are not allowed to cross in the arrangement (planar arrangements), and for rooted trees under the constraint that the arrangement is planar and the root is not covered (projective arrangements). We also tackle the unconstrained formulation of MaxLA for free trees. Our efforts have yielded polynomial-time solutions for $k$-linear trees ($0\le k\le2$) and a $3/2$-approximation algorithm. Furthermore, we devise algorithms and derive formulas to calculate the expected value of the cost of bipartite arrangements of bipartite graphs, and planar and projective arrangements of trees, based on new knowledge on how to generate such arrangements uniformly at random. All these algorithms, and others as well, have been packaged into the Linear Arrangement Library (LAL), licensed under the GNU Affero GPL.

Date: Wednesday, 18 September 2024

Time: 15:00h (Barcelona time)

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

Title: Decomposing to a Matching and a 2-Degenerate Graph

Speaker: Bartłomiej Bosek (Jagiellonian University)

Abstract:

We show that edges of any 2-arboric graph can be partitioned into a matching and a 2-degenerate graph. In particular, this implies that every 2-arboric graph is 1-defective 3-choosable. Similar decompositions were already known for triangle-free planar graphs, which are 2-arboric. Our method gives a simpler proof that is more general and does not require planarity. This is joint work with Grzegorz Gutowski, Michał Lasoń, and Jakub Przybyło.