# LIMDA Seminar

**ALBCOM - Algorithms and Theory of Computation**

**COMBGRAPH - Combinatorics, Graph Theory and Applications**

**GAPCOMB - Geometric, Algebraic and Probabilistic combinatorics**

## Next talk

**Date:** Thursday, 2 February, 2023

**Time: **16.15h (Barcelona time)

**Where: **Meet link

**Title: ** Joint properties of vertices with a given degree in the random recursive tree

**Speaker:** Bas Lodewijks (University of Lyon, University of Saint-Etienne)

**Abstract: **

In this talk, we will investigate the joint behaviour of the degree, depth, label of, and graph distance between high-degree vertices in the random recursive tree with n vertices labelled {1,...,n}. The analysis of the label of and graph distance between high-degree vertices is novel, in particular in relation to the behaviour of the depth of such vertices (whose known results we also improve and extend). Our analysis is based on a correspondence between the random recursive tree and a representation of the Kingman's n-coalescent.

## Previous sessions

**Date:** Thursday, 26 January, 2023

**Time: **16.15h (Barcelona time)

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

**Title: ** Cops and Robber Game on Surfaces of Euclidean, Spherical and Hyperbolic Metric

**Speaker:** Alexandra Wesolek (Simon Fraser University)

**Abstract: **

Recently, Mohar introduced a variant of the cops and robber game that is played on geodesic spaces. The game combines properties of pursuit-evasion games with the classical cops and robber game played on graphs. In this talk we discuss the rules of the game and strategies for the players when the game is played on compact surfaces of constant curvature 0,1 and -1. Joint work with Vesna Iršič and Bojan Mohar.

**Date:** Thursday, 19 January, 2023

**Time: **16.15h (Barcelona time)

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

**Title: ** Classifying weighted graphs up to Clifford group equivalence

**Speaker:** Robin Simoens (Ghent University and UPC)

**Abstract: **

Let G be an undirected, loopless graph on n vertices whose edges have weights in F_p, p prime. Let A=(a_ij) be its adjacency matrix. Define the following two operations:

For a given vertex k, map all a_ij to a_ij+a_ik a_jk (for all i,j in the neighbourhood of k, add a_ik a_jk to the weight of the edge connecting them).

For a given vertex k and a nonzero c in F_p, map all a_ik to ca_ik (multiply all edges incident with k, with c).

We call two such graphs Clifford group equivalent if there exists a sequence of these operations that converts one into the other. We are interested in the number of graphs up to this equivalence.

Our motivation comes from stabiliser codes. Two stabiliser codes are equivalent if their stabilisers are the same up to conjugation with a Clifford gate. Such equivalent codes have been shown to correspond with Clifford group equivalent graphs and vice versa.

For p=2 and n<=12, the number of equivalence classes has been determined. For odd p however, no results are known.

In this talk, I will discuss the above equivalence and present some strategies to compute the number of equivalence classes for p=3. I will explain how this helps us classify the stabiliser codes and certain other quantum error-correcting codes.

**Date:** Thursday, 1 December, 2022

**Time: **16.15h (Barcelona time)

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

**Title: ** Pattern Occurrence Counts in Random Planar Maps

**Speaker:** Michael Drmota (TU Wien)

**Abstract: **

Random planar maps have been studied from various aspects during the last 15 or 20 years, including various limiting distributions for several parameters of interest (such as the largest 2-connected component) and local Benjamini-Schramm limits as well as scaling limits. A pattern is a given planar map and we say that it appears in another map if it could be "cut out" just leaving a face. The simplest pattern is just an k-gons. It directly follows from the Benjamini-Schramm limit that the expected number of occurrences of a given pattern is asymptotically linear in the number of edges of the random map. However, it is a challenging problem to provide a more precise limit law. The purpose of this talk is to give a survey on the results and methods that have used so far in order to settle this question. It is conjectures that there is always a central limit theorem - and all results so far support this conjecture.

**Date:** Thursday, 10 November, 2022

**Time: **16.15h (Barcelona time)

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

**Title: ** Polynomial Algebras and Ideals for marked graphs reconstruction

**Speaker:** José Aliste (Universidad Andrés Bello, Chile)

**Abstract: **

In a previous work by using the framework of the V-polynomial of Ellis-Monaghan and Moffatt, we introduced marked graphs, the M-polynomial and the D-polynomial and showed how the D-polynomial can be used to give a fast computation of the expansion of the chromatic symmetric function of a graph as linear combination of chromatic symmetric functions of star forests. The D-polynomial is obtained from the M-polynomial by some relations that we call undotting relations. In this talk, we concentrate on the question of reconstructing the M-polynomial from the D-polynomial and study the undotting relations from a polynomial algebra point of view. By using results on Gröbner bases and elimination theory, plus some quasi-homogeneous polynomials we will explain that it is not always possible to reconstruct the M-polynomial from the D-polynomial, but that the M-polynomial will belong to a polytope that can be uniquely characterized starting from the D-polynomial in combinatorial and algebraic ways.

This is ongoing joint work with Anna de Mier, José Zamora and Rosa Orellana.

**Date:** Thursday, 3 November, 2022

**Time: **16.15h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title: ** Archaeology of random recursive dags and Cooper-Frieze random networks

**Speaker:** Simon Briend (UPF)

**Abstract: **

We study large networks that grow dynamically over time and in particular we consider network archaeology. It is a statistical problem of inferring the past properties of such growing networks, given the current state of the network. The existing literature on network archaeology mostly focuses on the simplest possible kind of networks, that is, trees. In various models of growing random trees, it is quite well understood up to what extent one may identify the origin of the tree (i.e., the root) by observing a large unlabeled tree. We will address the more realistic problem of finding the origin of growing networks when the network is not a tree. This requires new ideas as the centrality measures that proved to be successful in trees crucially rely on properties of the trees. More concretely, we propose to investigate archaeology of networks modelled by union of uniform random recursive trees as well as a particular case of the Cooper-Frieze model, which can be interpreted as a noisy uniform random recursive tree.

**Date: **Thursday, 27 October, 2022

**Time: **16.15h (Barcelona time)

**Where:** Room C3-005 Campus Nord UPC and Zoom link

**Title:** Enumeration of chordal graphs with bounded tree-width

**Speaker:** Jordi Castellví (UPC)

**Abstract:**

Tree-width is a fundamental parameter in structural and algorithmic graph theory. Graphs with tree-width at most $t$ can be defined as subgraphs of $t$-trees. A $t$-tree is a graph obtained from a $(t+1)$-clique by iteratively adding a new vertex connected to an existing $t$-clique. The asymptotic enumeration of graphs with tree-width at most $t$ is open for $t\geq 3$. This talk is devoted to the enumerative study of labelled graphs with bounded tree-width that are also chordal. A graph is chordal if it has no induced cycle of length greater than three. Chordality arises naturally in our setting, since $t$-trees are chordal, and has remarkable consequences, such as the fact that we can define the $k$-connected components of any chordal graph. With the help of analytic combinatorics, we obtain that the number of $k$-connected chordal graphs with $n$ labelled vertices and tree-width at most $t$ is of the form $cn^{-5/2}\gamma^n n!$, for some constants $c$ and $\gamma$ depending on $t$ and $k$. Additionally, the number of $i$-cliques in a uniform random $k$-connected labelled chordal graph with tree-width at most $t$ is normally distributed as $n\to\infty$.

Joint work with Michael Drmota, Marc Noy and Clément Requilé.

**Date:** Thursday, 6 October, 2022

**Time:** 16.15h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title: ** Ramsey-type properties of the binomial random graph

**Speaker:** Tássio Naia (LaBRI-U. Bordeaux)

**Abstract: **

The binomial random graph G(n,p) is a random graph obtained

from a complete graph of order n by deleting each edge with

probability 1 -p, where deletions are mutually independent.

We shall discuss recent advances in some of the following

questions (and maybe others, time permitting).

1) What subdigraphs must every orientation of G(n,p) contain?

2) Let k be an integer. For what p does G(n,p) asymptotically almost surely admit an orientation free of transitive tournaments (i.e., transitive orientations of a clique) of order k?

3) Given p, what is the largest integer t such that every orientation of G(n,p) contains every oriented tree on t vertices?

This is joint work with G.F. Barros, B.P. Cavalar, H. Hàn, G. Mota, Y. Kohayakawa, M. Pavez-Signé and M. Stein.

**Date:** Thursday, 29 September, 2022

**Time:** 16.15h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title: ** Multidimension of simple games: compact representations of voting systems

**Speaker:** Fabián Riquelme (Universidad de Valparaíso)

**Abstract: **

Simple games are mathematical structures that represent binary decision-making procedures between players, agents, or actors. Weighted voting games (WVG) are simple games usually used to represent voting systems in which the players have different powers to influence the collective decision. The WVGs can be represented as unions and/or intersections of integer vectors, i.e., compact ways of representation that help to store and understand the system's collective behavior. The dimension, codimension, and multidimension are the minimum number of WVGs such that their intersection (union, intersection/union, respectively) is the given game. We present different properties and theoretical and experimental results regarding these succinct representations that allow understanding gaps between weighted voting systems and simple games.

This is a project partially funded by Fondecyt de Iniciación 11200113 from ANID, Chile.

Joint work with Xavier Molinero, Salvador Roura, Maria Serna

**Date:** Thursday, 22 September, 2022

**Time: **16.15h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title: **The jump of the clique chromatic number of random graphs

**Speaker: **Dieter Mitsche (Univ. Jean Monnet, Saint-Etienne/Univ. Claude Bernard, Lyon)

**Abstract: **

The clique chromatic number of a graph is the smallest number of colors in a vertex coloring so that no maximal clique is monochromatic. In 2016 together with McDiarmid and Pralat we noted that around pm n^{-1/2} the clique chromatic number of the random graph G(n,p) changes by n^{\Omega(1)} when we increase the edge-probability p by n^{o(1)}, but left the details of this surprising phenomenon as an open problem.

We settle this problem, i.e., resolve the nature of this polynomial `jump' of the clique chromatic number of the random graph G(n,p) around edge-probability p = n^{-1/2}. Our proof uses a mix of approximation and concentration arguments, which enables us (i) to go beyond Janson's inequality used in previous work and (ii) to determine the clique chromatic number of G(n,p) up to logarithmic factors for any edge-probability p.

Joint work with Lyuben Lichev and Lutz Warnke.

**Date:** Thursday, 15 September, 2022

**Time:** 16.15h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title: **Zero-knowledge proofs and their applications

**Speaker: **Marta Bellés (UPF)

**Abstract: **

Informally speaking, zero-knowledge proofs are cryptographic tools that allow you to prove that you know a secret without revealing it. More precisely, zero-knowledge proofs are cryptographic protocols that allow one party to convince another that a statement is true without revealing anything other than the veracity of the statement. This type of proofs were introduced in 1985 as theoretical cryptographic objects, but the appealing properties of the protocols have made them become crucial tools in many real-world applications with strong privacy issues. In this presentation I will explain the main ideas behind zero-knowledge, I will talk about the type of statements that we know can be proved with zero-knowledge, and present some of the most outstanding applications of this technology.

**Date:** Thursday, 8 September, 2022

**Time: **15.00h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title: **Triality revisited

**Speaker: **Klara Stokes (Umeå)

**Abstract: **

An incidence geometry has a duality if there is a correlation permuting two of the types. A duality of order two is also called a polarity. A triality is a correlation of order three, permuting three types. Triality is a classical notion in geometry, associated with an outer automorphism of Lie groups of type $D_4$. It was first described by E. Study in 1903 and later by E. Cartan in 1925. In 1959, J. Tits classified the trialities with absolute points. These investigations motivated his definition of the generalised polygons; the content of the appendix of the same paper.

In this talk I will describe how to use coset geometries to construct examples of incidence geometries with r-alities and prescribed automorphism group. I will also describe how to construct incidence geometries with trialites using maps on surfaces as well as from voltage graphs/gain graphs.

This is joint work with Dimitri Leemans.

**Date: **Tuesday, 28 June, 2022

**Time:** 11:30 (Barcelona time)

**Where: **Room C3-005 Campus Nord UPC and Zoom link

**Title:** The Kahn-Kalai conjecture on thresholds

**Speaker:** Patrick Morris (UPC)

**Abstract:**

Ever since the work of Erdős and Rényi pioneering the study of random graphs, one of the central themes of the subject has been to determine the location of the threshold* *for certain graph properties; the critical probability at which the property switches from being very unlikely to very likely. For many examples of interest, such as the appearance of (possibly spanning) subgraphs, one can obtain lower bounds on thresholds by running simple expectation calculations. In this reading seminar, we will discuss the recent solution of a surprising conjecture of Kahn and Kalai from 2006, that states that these expectation calculations are actually never far from the truth and that they differ from the true value of the threshold by at most a factor of log n. The conjecture is very general and has many important implications in the study of random graph thresholds.

Until a couple of years ago this conjecture seemed far out of reach and it was not even clear whether one should try to prove it or try to find a counterexample. This makes the solution of this conjecture, posted by Park and Pham in March this year, a truly remarkable result and perhaps even more surprising is that their proof is only 5 pages and, by all accounts, a very elegant argument using no heavy machinery. Although this result came as a huge surprise in the community, it builds on the ideas of several big breakthroughs in recent years. Indeed, in 2019, Frankston, Kahn, Narayanan and Park posted the proof of a fractional version of the Kahn-Kalai conjecture, a weaker form of the conjecture that still has far-reaching implications. In turn, the proof in that paper (now in Annals) adopts ideas of another big breakthrough (also in Annals) to a seemingly unrelated problem known as the Erdős-Rado Sunflower problem.

This talk is a taster session for an upcoming reading seminar where we will look at the remarkable recent proof of the Kahn-Kalai conjecture, due to Park and Pham, and several papers that led to this breakthrough. This seminar is planned to start in September.

**Date: **Thursday, 2 June, 2022

**Time:** 16.30h (Barcelona time)

**Where: **Room C3-005 Campus Nord UPC and Zoom link

**Title:** Perfect codes of circulant graphs of degree $p^l-1$

**Speaker:** Xiaomeng Wang (Lanzhou University, UPC)

**Abstract:**

A perfect code in a graph is an independent set $D$ such that every vertex not in $D$ is adjacent to exactly one vertex in $D$. We will review the known results on perfect codes in circulant graphs and present a new characterization on the existence and structure of perfect codes in circulant graphs of degree a power of a prime minus one.

**Date:** Thursday, 26 May, 2022

**Time: **16.30h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title:** Absolutely maximally entangled states: a combinatorial and geometric view

**Speaker:** Simeon Ball (UPC)

**Abstract:**

I will assume no prior knowledge of Hilbert spaces or quantum mechanics. This talk is aimed at researchers in graphs and combinatorial geometry.

In this talk I will briefly explain the concept of entanglement in quantum mechanics and define what is an absolutely maximally entangled state of the Hilbert space $({\mathbb C}^q)^{\otimes n}$. In the qubit case ($q=2$) I will sketch a link between such states and simple graphs and by doing so, we will see that it is not difficult to classify all absolutely maximally entangled states of $({\mathbb C}^2)^{\otimes n}$ that have a stabiliser group.

The case $q>2$ is more complicated as simple graphs can no longer be used to describe the states. We can however, find an equivalence to a set of $n$ lines $\mathcal X$ in the finite projective space PG$(n-1,q)$.

In the case $q=2$ (and for simplicity assuming $n$ is even), it is well known that this set of lines $\mathcal X$ has two properties namely, that every co-dimensional two subspace intersects an even number of lines of $\mathcal X$ and any subset of $\frac{1}{2}n$ lines of $\mathcal X$ span the entire space.

The smallest parameters for which it is not known if there is an absolutely maximally entangled state is the Hilbert space $({\mathbb C}^4)^{\otimes 8}$.

In this talk I will explain ongoing work with Edgar Moreno in which we prove that for $q=4$ an

absolutely maximally entangled state (which has a stabiliser group) is equivalent to a set of lines in a finite projective space with a property similar to that for $q=2$. I will explain how we hope to classify all such sets of lines and thereby determine if there is an absolutely maximally entangled state in the Hilbert space $({\mathbb C}^4)^{\otimes 8}$ or not.

**Date:** Thursday, 19 May, 2022

**Time:** 16.30h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title: **The Semi-Random Tree Process

**Speaker: **Sofiya Burova (ENS Lyon)

**Abstract:**

The online semi-random graph process is a one-player game which starts with the empty graph on n vertices. At every round, a player (called Builder) is presented with a vertex v chosen uniformly at random and independently from previous rounds, and constructs an edge of his choice that is incident to v. Inspired by recent advances on the semi-random graph process, we define a family of generalised online semi-random models. Then, we analyse a particular instance that shares similar features with the original semi-random graph process and study the hitting times of classical graph properties.

Joint work with Lyuben Lichev.

**Date:** Thursday, 12 May, 2022

**Time:** 16.30h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title: **Moore's problem in its bipartite biregular version

**Speaker: **Gabriela Araujo-Pardo (Instituto de Matemáticas, UNAM)

**Abstract:**** **

**Date:** Thursday, 28 Apr, 2022

**Time:** 16.30h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title:** Optimization, Testing, Learning of Deterministic Finite State Machines

**Speaker:** Alberto Larrauri (TU Graz)

**Abstract:**** **

Finite state machines are a formalism used to describe a wide array of

reactive systems. Among them, finite automata are machines that either

accept or reject each input word. We give an overview of three closely-

linked problems related to deterministic finite automata (DFA):

optimization, testing and learning. In the optimization problem, we are

given a classification of input words and the goal is to obtain a

smallest automaton consistent with that information. In conformance

testing, we begin with a DFA A and a bound k, and we are asked to

produce a small set of words distinguishing A from all other (non-

equivalent) automata containing at most k states. Lastly, in active

learning the task is to infer a model of a black-box automaton through

limited interaction with an oracle called a "minimally adequate

teacher". Finally, we briefly discuss extensions of these problems

where instead of considering a single machine in isolation, we study

multiple ones that interact with each other and showcase some recent

results.

**Date:** Thursday, 21 Apr, 2022

**Time:** 16.30h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title:** Ramsey Multiplicity and Search Heuristics

**Speaker:** Christoph Spiegel (Zuse Institute Berlin)

**Abstract:**** **

We present several new improved and tight asymptotic bounds relating both to the minimum number of monochromatic cliques contained in any edge-coloring of a complete graph as well as the minimum number of cliques in graphs with bounded independence number. Most notably, we present an improvement in the upper bound of the K4 and K5 Ramsey multiplicity and introduce a notion of off-diagonal Ramsey multiplicity. The upper bounds are established through graph and Cayley graph constructions found through well-established computer search heuristics.

**Date:** Thursday, 21 Apr, 2022

**Time: **17.00h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title:** Stability of Erdős-Ko-Rado Theorems in Circle Geometries

**Speaker: **Sam Adriaensen (Vrije Universiteit Brussel)

**Abstract:**** **

Techniques from algebraic graph theory have proven to be quite powerful in solving combinatorial problems. Especially for solving Erdős-Ko-Rado problems. There, one takes an incidence structure consisting of points and blocks (which are sets consisting of points), and one wonders what the largest families of blocks is such that they have pairwise non-empty intersection. In a lot of cases, the largest families are the trivial ones, where you fix a point and just take all blocks containing this point. In a lot of settings, one can prove that these are the only examples of maximum size, using the Hoffman ratio bound.

Often, the limitations of these techniques are that you can only say something about the intersecting families of maximum size. In this talk I will show that we can do better. The incidence structures under investigation are circle geometries. They are typically constructed by taking a quadratic surface Q in 3-dimensional projective space PG(3,q). The non-trivial plane sections of Q are called circles. The points and blocks of the circle geometries are the points and circles respectively of Q. Using the expander mixing lemma, we cannot only prove that the largest intersecting families are of size q² ± O(q), but that all intersecting families of size 1/√2 q² + O(q) are trivial (i.e. they consist of circles through a fixed point).

**Date: **Thursday, 7 Apr, 2022

**Time:** 16.30h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title:** Número Sidon-Ramsey en Z_n

**Speaker:** Luis Miguel Delgado Ordoñez (Universidad del Cauca)

**Abstract: **

El problema de los conjuntos de Sidon es un problema clásico en la Teoría Combinatoria de Números, del cual daré una breve introducción. Posteriormente, expondré la versión en coloraciones de dicho problema y explicaré su conexión con el teorema de Rado en la teoría de Ramsey donde apareció el denominado Número Sidon-Ramsey. Finalmente, presentaré los resultados obtenidos en la investigación adelantada del Número de Sidon-Ramsey en grupos cíclicos.

**Date:** Thursday, 7 Apr, 2022

**Time:** 17.00h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title:** Construcciones combinatorias de códigos

ortogonales ópticos

**Speaker:** Hamilton Mauricio Ruiz (Universidad del Cauca)

**Abstract: **

Los códigos ortogonales ópticos COOs, se definen como un conjunto de secuencias de peso constante con buenas propiedades de autocorrelación y correlación cruzada. Desde su aparición en 1989, varias son las áreas de las matemáticas encargadas de la búsqueda y diseño de construcciones explícitas de COOs, una de ellas es la combinatoria. En esta charla explicaremos algunas herramientas combinatorias utilizadas en la construcción de códigos ortogonales ópticos, especialmente aquellas construcciones que utilizan el concepto de cuadrados latinos mutuamente ortogonales y conjuntos de Sidon modulares.

**Date: **Thursday, 31 Mar, 2022

**Time: **16.30h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title:** Schur properties of randomly perturbed sets

**Speaker:** Patrick Morris (UPC)

**Abstract: **

A set $A$ of integers is said to be Schur if any two-colouring of $A$ results in monochromatic $x,y$ and $z$ with $x+y=z$. We discuss the following problem: how many random integers from $[n]$ need to be added to some $A\subseteq [n]$ to ensure with high probability that the resulting set is Schur? Hu showed in 1980 that when $|A|> \ceil{4n/5}$, no random integers are needed, as $A$ is already guaranteed to be Schur. Recently, Aigner-Horev and Person showed that for any dense set of integers $A\subseteq [n]$, adding $\omega(n^{1/3})$ random integers suffices, noting that this is optimal for sets $A$ with $|A|\leq \ceil{n/2}$.

We close the gap between these two results by showing that if $A\subseteq [n]$ with $|A|=\ceil{n/2}+t<\ceil{4n/5}$, then adding $\omega(\min\{n^{1/3},nt^{-1}\})$ random integers will with high probability result in a set that is Schur. Our result is optimal for all $t$, and we further initiate the study of perturbing sparse sets of integers $A$ by providing nontrivial upper and lower bounds for the number of random integers that need to be added in this case.

Joint work with Shagnik Das and Charlotte Knierim.

**Date:** Thursday, 24 Mar, 2022

**Time:** 16.30h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title:** Characterization of the extremal families for the Kruskal-Katona's inequality

**Speaker:** Lluís Vena (UPC)

**Abstract:**

Given $S$ a family of sets of size $k$ in $[n]$, its lower shadow $\Delta(S)$ is the family of sets of size $k-1$ which are contained in at least one set of the family. The celebrated Kruskal-Katona theorem gives the minimum size of $\Delta(S)$ in terms of the size of $S$. F\"uredi and Griggs (and M\"ors) showed that the extremal families for this shadow minimization problem in the Boolean lattice are unique for some cardinalities and asked for a general characterization of these extremal families.

In this talk we present a new combinatorial inequality from which yet another simple proof of the Kruskal--Katona theorem can be derived. The inequality can be used to obtain a characterization of the extremal families for this minimization problem, giving an answer to the question of F\"uredi and Griggs. Some known and new additional properties of extremal families can also be easily derived from the inequality.

Join work with Oriol Serra.

**Date:** Thursday, 17 Mar, 2022

**Time:** 16.30h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title:** Path decompositions of random directed graphs

**Speaker:** Alberto Espuny (TU Ilmenau)

**Abstract:**** **

In this talk we consider the problem of decomposing the edges of a directed graph into as few paths as possible. The minimum number of paths needed in such an edge decomposition is called the path number of the digraph.

The problem of determining the path number is generally NP-hard. However, there is a simple lower bound for the path number of a digraph in terms of its degree sequence, and a conjecture of Alspach, Mason, and Pullman from 1976 states that this lower bound gives the correct value of the path number for any even tournament. The conjecture was recently resolved, and in this talk I will discuss to what extent the conjecture holds for other digraphs. In particular, I will discuss some of the ingredients of a recent result showing that the conjecture holds with high probability for the random directed graph D(n,p) for a large range of p.

This is joint work with Viresh Patel and Fabian Stroh.

**Date: **Thursday, 10 Mar, 2022

**Time: **16.30h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title:** Higher sumsets and approximate groups

**Speaker:** Arindam Biswas (U. of Copenhagen)

**Abstract: **

Let G be an abelian group and A be any non-empty, finite subset. For the integers, the structure of the higher sumsets mA with $m\geq 1$ was investigated by Nathanson in the 1970s. Recent works of Granville-Walker, Lev, etc. have improved some of the bounds of Nathanson and Granville-Shakan-Walker also investigated higher sumsets in $Z^d$. We will discuss these results and their relationship to approximate groups.

**Date:** Thursday, 3 Mar, 2022

**Time:** 16.30h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title:** Marked graphs and the chromatic symmetric function

**Speaker:** Anna de Mier (UPC)

**Abstract:**** **

In the mid 90s Stanley introduced the chromatic symmetric function, a

symmetric function analogue of the chromatic polynomial, and he asked

whether it determines trees up to isomorphism. Motivated by this

question and with the aim of better understanding the chromatic

symmetric function, we introduce a class of marked graphs (that is,

graphs with vertices weighted by elements of a semigroup) and a

polynomial on them defined via deletion-contraction. From this

polynomial, that we call the M-polynomial, one can compute the expansion

of the chromatic symmetric function in terms of the chromatic symmetric

functions of stars (which give rise to a basis for symmetric functions).

We then explain how these results could be used to approach Stanley's

question and carry out the program for trees up to diameter five

satisfying a mild extra condition.

This is joint work with José Aliste-Prieto, Rosa Orellana and José Zamora.

**Date:** Thursday, 24 Feb, 2022

**Time:** 16.30h (Barcelona time)

**Where: ** Room C3-005 Campus Nord UPC and Zoom link

**Title:** Some problems on randomly perturbed graphs

**Speaker:** Alberto Espuny (TU Ilmenau)

**Abstract:**

The theory of randomly perturbed graphs has seen tremendous growth in recent years. This theory serves to interpolate between classical results in extremal graph theory and the theory of random graphs. Given some property P that we wish to study (say, the containment of a given spanning structure), the idea is to consider a deterministic graph H which does not satisfy P and a random graph G=G(n,p) which is very unlikely to satisfy P, and study whether the union of H and G will satisfy P. In particular, we aim to obtain the best possible combinations of parameters for H and G that will yield P with high probability.

**Date:** Wednesday, 26 Jan, 2022

**Time:** 14.30h (Barcelona time)

**Where**: G-meet: meet.google.com/fty-utgm-qxq

**Title:** Probabilistic and Extremal studies in Additive Combinatorics

**Speaker:** Max Wötzel (UPC)

Ph.D. defence** , **Thesis director: Rué, Juanjo | Serra, Oriol

**Abstract:**

The results in this thesis concern extremal and probabilistic topics in number theoretic settings. We prove sufficient conditions on when certain types of integer solutions to linear systems of equations in binomial random sets are distributed normally, results on the typical approximate structure of pairs of integer subsets with a given sumset cardinality, as well as upper bounds on how large a family of integer sets defining pairwise distinct sumsets can be. In order to prove the typical structural result on pairs of integer sets, we also establish a new multipartite version of the method of hypergraph containers, generalizing earlier work by Morris, Saxton and Samotij.

**Date:** Monday, 20 Dec, 2021

**Time:** 15.00h (Barcelona time)

**Where**: Room C3005 Campus Nord UPC and Zoom

**Title:** Deviation Probabilities for arithmetic progressions

**Speaker:** Oriol Serra (UPC)

**Abstract:**

The study of large deviations on the expected number of arithmetic

progressions on a random set of the first N positive integers has a rich

history, parallel to the study of large deviations on subgraph counts of

the random graph G(n,p).

Goldsmith, Griffiths and Scott introduced a new approach using

martingale methods to analyze moderate deviations in subgraph counts in

G(n,m). In the talk an adaption of the method to count arithmetic

structures given by solutions of a linear system in an abelian group is

presented. The method reduces to the general problem of counting edges

in random hypergraphs. Exponential bounds for moderate deviations in

edge counting are then translated to the arithmetic setting. The bounds

for the counting of edges in hypergraphs are seen to be essentially best

possible.

Joint work with Gonzalo Fiz-Pontiveros, Simon Griffiths and Mattheus Secco

**Date:** Monday, 13 Dec, 2021

**Time:** 14.00h (Barcelona time)

**Where**: online at https://meet.google.com/uve-zvxj-wdr

**Title:** Threshold phenomena involving the connected components of random graphs and digraphs

PhD Defense COULSON, MATTHEW JOHN

Advisor: PERARNAU LLOBET, GUILLEM

**Speaker:** Mathew Coulson (UPC)

**Abstract:**

We consider some models of random graphs and directed graphs and investigate their behavior near thresholds for the appearance of certain types of connected components. Firstly, we look at the critical window for the appearance of a giant strongly connected component in binomial random digraphs. We provide bounds on the probability that the largest strongly connected component is very large or very small. Next, we study the configuration model for graphs and show new upper bounds on the size of the largest connected component in the subcritical and barely subcritical regimes. We also show that these bounds are tight in some instances. Finally we look at the configuration model for random digraphs. We investigate the barely sub-critical region and show that this model behaves similarly to the binomial random digraph whose barely sub- and super-critical behaviour was studied by Luczak and Seierstad. Moreover, we show the existence of a threshold for the existence of a giant weak component, as predicted by Kryven.

**Date:** Monday, 29 Nov, 2021

**Time:** 15.00h (Barcelona time)

**Where**: Room C3005 Campus Nord UPC and Zoom

**Title:** Four families of polynomials in spectral graph theory

**Speaker:** Miquel Àngel Fiol (UPC)

**Abstract:**

In this talk we describe four families of polynomials related to the spectrum of a graph. First, some known main results involving such polynomials, such as the spectral excess theorem characterizing distance-regularity, are discussed. Second, some new results giving bounds for the $k$-independence number $\alpha_k$ of a graph are presented. In this context, we comment on some relationships between the inertia (Cvetkovi\`c) and ratio (Hoffman) bounds of $\alpha_k$.

**Date:** Wednesday, 24 Nov, 2021

**Time:** 15.00h (Barcelona time)

**Title:** RandNET Seminar

**Speaker:** Roberto Imbuzeiro Oliveira (IMPA)

**Link: **https://randnet.upc.edu/seminar/

**Date:** Monday, 22 Nov, 2021

**Time:** 14.00h (Barcelona time)

**Where**: Room C3005 Campus Nord UPC and Zoom

**Title:** Hermitian self-orthogonal codes

**Speaker:** Simeon Ball (UPC)

**Abstract: **

Let $C$ be a $[n,k]_{q^2}$ linear code, i.e. a $k$-dimensional subspace of ${\mathbb F}_{q^2}^n$.

$C$ is linearly equivalent to a Hermitian self-orthogonal code if and only if there are non-zero $\lambda_i \in {\mathbb F}_{q}$ such that $$\sum_{i=1}^n \lambda_{i} u_{i}v_{i}^q=0,$$ for all $u,v \in C$.

For any linear code $C$ over ${\mathbb F}_{q^2}$ of length $n$, Rains defined the {\em puncture code} $P(C)$ to be $$P(C)=\{\lambda=(\lambda_{1},\ldots,\lambda_n) \in {\mathbb F}_q^n \ | \ \sum_{{i}=1}^n \lambda_{i} u_{i}v_{i}^q=0, \ \mathrm{for} \ \mathrm{all} \ u,v \in C \}.$$

There is a truncation of a linear code $C$ over ${\mathbb F}_{q^2}$ of length $n$ to a linear over ${\mathbb F}_{q^2}$ of length $r \leqslant n$ which is linearly equivalent to a Hermitian self-orthogonal code if and only if there is an element of $P(C)$ of weight $r$.

Rains was motivated to look for Hermitian self-orthogonal codes, since there is a simple way to construct a $ [\![ n,n-2k]\!] _q$ quantum code, given a Hermitian self-orthogonal code. This construction is due to Ketkar et al, generalising the ${\mathbb F}_4$-construction of Calderbank et al.

In this talk, I will detail an effective way to calculate the puncture code. I will outline how to prove various results about when a linear code has a truncation which is linearly equivalent to a Hermitian self-orthogonal linear code and how to extend it to one that does in the case that it has no such truncation. In the case that the code is a Reed-Solomon code, it turns out that the existence of such a truncation of length $r$ is equivalent to the existence of a polynomial $g(X)$ of degree at most $(q-k)q-1$ with the property that $g(X)+g(X)^q$ has $q^2-r$ distinct zeros.

(joint work with Ricard Vilar)

**Date:** Monday, 15 Nov, 2021

**Time:** 15.00h (Barcelona time)

**Where**: Room C3005 Campus Nord UPC and Zoom

**Title:** Counting rooted 3-connected bipartite planar maps

**Speaker:** Marc Noy (UPC)

**Abstract: **

We provide the first solution to the problem of counting (rooted) 3-connected bipartite planar maps. Our starting point is the enumeration of bicolored planar maps by number of monochromatic edges, following the work of Bernardi and Bousquet-Mélou in J. Comb. Theory Ser. B, 101 (2011), 315--377. The decomposition of a map into 2- and 3-connected components allows us to obtain the generating functions of 2- and 3-connected bicolored maps. Setting to zero the variable marking monochromatic edges we obtain the generating function of 3-connected bipartite maps, which is algebraic of degree 26. We deduce from it an asymptotic estimate for the number of 3-connected bipartite planar maps of the form g^n/n^(5/2), where g = 1/r = 2.40958 and r is an explicit algebraic number of degree 10.

This is joint work in progress with Clément Requilé and Juanjo Rué.

**Date:** Monday, 8 Nov, 2021

**Time:** 15.00h (Barcelona time)

**Where: ** Room C3001 Campus Nord UPC

**Title:** On a notion of homomorphisms for graphs embedded on surfaces, and its poset of cores

**Speaker:** Lluís Vena (UPC)

**Abstract: **A graph homomorphism between two graphs is a mapping between the corresponding vertex sets that sends edges to edges. We present a homomorphism notion between graphs embedded on (non-necessarily orientable) surfaces, also known as maps, that is graph homomorphism between graphs, yet it preserves the topology they are embedded in (namely its sign genus). Furthermore, we define a core of a map in an analogous way as for graphs, give a characterization of when a map is a core (in terms of the contractible cycles of the map), and we study the properties of the poset of cores, showing that it behaves radically different than in the case of graphs (for instance, there is no dense totally ordered interval).

Joint work with Delia Garijo and Andrew Goodall.

**Date:** Wednesday, 27 Oct, 2021

**Time:** 14.00h (Barcelona time)

**Title:** RandNET Seminar

**Speaker:** Martin Balko (Charles University Prague)

**Link: **https://randnet.upc.edu/seminar/

**Date:** Wednesday, 29 Sep, 2021

**Time:** 16.00h (Barcelona time)

**Title:** RandNET Seminar

**Speaker:** Louigi Addario-Berry (McGill University)

**Link: **https://randnet.upc.edu/seminar/

**Date:** Wednesday, 15 Sep, 2021

**Time:** 15.00h (Barcelona time) (Watch out: exceptional time)

**Where: ** Room C3005 Campus Nord UPC and Zoom

**Title:** (Maximal) Independet Sets in Various Random Graph Classes

**Speaker:** Michael Drmota (TU Wien)

**Abstract: **

The purpose ot this talk is to discuss the following two questions for

random series-parallel graphs and random co-graphs:

- How many (maximal) independent sets can we expect for a typical graph of this kind?

- Does there typically exist an independent set of linear size?

Interestingly, in both graph classes we can expect exponentially many independent sets,

whereas independent sets of linear size exist typically only for series-parallel graphs.

This talk is based on the following two papers:

M. Drmota, L. Ramos, C. Requile, and J. Rue, Maximal independent sets and maximal matchings in series-parallel and related graph classes, The Electronic Journal of Combinatorics 27 (1), P1.5, 2020.

Frédérique Bassino, Mathilde Bouvel, Michael Drmota, Valentin Féray, Lucas Gerin, Mickaël Maazoun, Adeline Pierrot, Linear-sized independent sets in random cographs and increasing subsequences in separable permutations, arXiv:2104.07444.

**Date:** Wednesday, 30 Jun, 2021

**Time:** 15.00h (Barcelona time)

**Title:** RandNET Seminar

**Speaker:** Maya Stein (Santiago de Chile) and James Martin (Oxford)

**Link: **https://randnet.upc.edu/seminar/

**Date:** Wednesday, 02 Jun, 2021

**Time:** 12.15h (Barcelona time)

**Where: ** Zoom

**Title:** Geometry of high genus maps

**Speaker:** Baptiste Louf (Uppsala)

**Abstract: **Maps are discrete surfaces built by gluing polygons along their sides (or, alternatively, they can be seen as graphs embedded in surfaces). They have been given a lot of attention for several decades now, and in this talk we will be interested in the geometric properties of large random maps.

This question has been well studied in the case of planar maps (i.e. maps of the sphere), and more recently extended to any surface when the topology is fixed. Here, we are interested in yet another regime, that we call high genus maps, in which the genus of the surface grows at the same time as the size. These objects naturally exhibit hyperbolic properties. I will give an overview of the existing results and open problems.

**Date:** Wednesday, 26 May, 2021

**Time:** 15.00h (Barcelona time)

**Title:** RandNET Seminar

**Speaker:** Lutz Warnke (GATech)

**Link: **https://randnet.upc.edu/seminar/

**Date:** Wednesday, 19 May, 2021

**Time:** 12.15h (Barcelona time)

**Where: ** Zoom

**Title:** On Motzkin's problem in the circle group

**Speaker:** Pablo Candela (UAM)

**Abstract: **Given a finite subset $D$ of the interval $(0,1)$, if a Borel set $A\subset [0,1)$ contains no pair of elements whose difference modulo 1 is in $D$, then how large can the Lebesgue measure of $A$ be? This is the analogue in the circle group of a well-known problem of Motzkin, originally posed for sets of integers. We make a first treatment of this circle-group analogue, for finite sets $D$ of missing differences, using techniques from ergodic theory, graph theory and the geometry of numbers. Our results include an exact solution when $D$ has two elements, at least one of which is irrational. When every element of $D$ is rational, the problem is equivalent to estimating the independence ratio of a circulant graph. In the case of two rational elements, we give an estimate for this ratio in terms of the odd girth of the graph, which is asymptotically sharp and also recovers a classical solution of Cantor and Gordon to Motzkin's original problem for two missing differences. This is joint work with Carlos Catalá, Juanjo Rué and Oriol Serra.

**Date:** Wednesday, 05 May, 2021

**Time:** 12.15h (Barcelona time)

**Where: ** Zoom

**Title:** Nested cycles with no geometric crossings.

**Speaker:** Irene Gil (Warwick)

**Abstract: **In this talk, we answer the following question posed by Erdös in 1975: what is the smallest function $f(n)$ for which all graphs with $n$ vertices and $f(n)$ edges contain two edge-disjoint cycles $C_1$ and $C_2$, such that the vertex set of $C_2$ is a subset of the vertex set of $C_1$ and their cyclic orderings of the vertices respect each other? We prove the optimal linear bound $f(n)=O(n)$ using sublinear expanders. This is joint work with Jaehoon Kim, Younjin Kim and Hong Liu.

**Date:** Wednesday, Apr 28, 2021

**Time:** 15.00h (Barcelona time)

**Title: **RandNET Seminar: Rui Castro

**Speakers: **Detecting a planted community in an inhomogeneous random graph

**Link: **https://randnet.upc.edu/seminar/

**Date:** Wednesday, 21 Apr, 2021

**Time:** 12.15h (Barcelona time)

**Where: ** Zoom

**Title:** Quotientopes

**Speaker:** Vincent Pilaud (LIX-Polytechnique and CNRS, Paris)

**Abstract: **This talk will survey combinatorial and geometric properties of lattice quotients of the weak order on permutations, whose prototype is the classical Tamari lattice on binary trees. We will see in particular that any weak order quotient can be realized by a convex polytope called quotientope, generalizing the associahedron. Based on joint work with Francisco Santos, Arnau Padrol and Julian Ritter.

**Date:** Wednesday, 14 Apr, 2021

**Time:** 12.15h (Barcelona time)

**Where: ** Zoom

**Title:** Bounding Obstructions sets: the cases of apices of minor closed classes

**Speaker:** Dimitrios M. Thilikos (LIRMM and CNRS, Montpellier)

**Abstract: **Given a minor-closed graph class {\cal G}, the (minor) obstruction of {\cal G} is the set of all minor-minimal graphs not in {\cal G}. Given a non-negative integer k, we define the k-apex of {\cal A} as the class containing every graph G with a set S of vertices whose removal from G gives a graph on {\cal G}. We prove that every obstruction of the k-apex of {\cal G} has size bounded by some 4-fold exponential function of p(k) where p is a polynomial function whose degree depends on the size of the minor-obstructions of {\cal G}. This bound drops to a 2-fold exponential one when {\cal G} excludes some apex graph as a minor (i.e., a graph in the $1$-apex of planar graphs). Joint work with Ignasi Sau and Giannos Stamoulis

**Date:** Wednesday, 07 Apr, 2021

**Time:** 12.45h (Barcelona time) (NOTE THE UNUSUAL TIME)

**Video: ** here (UPC login required)

**Title:** On the complexity of finding large odd induced subgraphs and odd colorings

**Speaker:** Ignasi Sau (LIRMM and CNRS, Montpellier)

**Abstract: **This talk is about the problems of finding, given a graph $G$, a largest induced subgraph of $G$ with all degrees odd (called an odd subgraph), and the smallest number of odd subgraphs that partition $V(G)$. We call these parameters $mos(G)$ and $\chi_{odd}(G)$, respectively. We will discuss (some of) the following results:

- Deciding whether $\chi_{odd}(G) \leq q$ is polynomial-time solvable if $q \leq 2$, and NP-complete otherwise.

- FPT algorithms in time $2^{O(rw)}poly(n)$ and $2^{O(q \cdot rw)}poly(n)$ to compute $mos(G)$ and to decide whether $\chi_{odd}(G) \leq q$ on an $n$-vertex graph $G$ of rank-width at most $rw$, respectively. The dependency on rank-width is asymptotically optimal under the ETH.

- Some tight bounds for these parameters on restricted graph classes or in relation to other parameters.

Joint work with Rémy Belmonte, available at arXiv:2002.06078.

**Date:** Wednesday, Mar 24, 2021

**Time:** 15.00h (Barcelona time)

**Title:** 2-session RandNET Seminar: "Random planar graphs - results and conjectures" and "Maps of unfixed genus and blossoming trees"

**Speakers:** Benedikt Stuffler (TUWien, Vienna) and Eric Fusy (LIX-Polytechnique, Paris)

**Link: **https://randnet.upc.edu/seminar/

**Date:** Wednesday, 10 Mar, 2021

**Time:** 12.15h (Barcelona time)

**Where: ** Zoom

**Title:** Algorithmic extensions of the Bollobás-Häggkvist conjecture

**Speaker:** Viresh Patel (UVA, Amsterdam)

**Abstract: **Dirac's Theorem is a classical result in graph theory stating that every n-vertex graph with minimum degree at least n/2 has a Hamilton cycle. If we restrict to regular graphs (and impose some mild connectivity conditions), we might hope to lower the degree threshold: in that direction, Bollobás and Häggkvist independently conjectured that every k-connected, D-regular, n-vertex graph with D≥n/(k+1) has a Hamilton cycle. Although the conjecture turns out to be false for k≥4, one might still wonder whether Hamiltonicity is easier to detect in regular (dense) graphs. We investigate this question. This is joint work with Fabian Stroh.

**Video**: here (UPC login required)

**Date:** Wednesday, Feb 24, 2021

**Time:** 15.00h (Barcelona time)

**Title:** 2-session RandNET Seminar: "Network archeology: a few results and many questions" and "The design of algorithms for the production of training data"

**Speakers:** Gábor Lugosi (UPF, Barcelona) and Élie de Panafieu (Nokia-Bell Labs)

**Link: **https://randnet.upc.edu/seminar/

**Date:** Wednesday, Jan 20, 2021

**Time:** 12.15h (Barcelona time)

**Where: ** Zoom

**Title:** On the expected number of perfect matchings in cubic planar graphs

**Speaker:** Marc Noy

**Abstract: **A well-known conjecture by Lovász and Plummer from the 1970s asserted that a bridgeless cubic graph has exponentially many perfect matchings. It was solved in the affirmative by Esperet et al. (Adv. Math. 2011). On the other hand, Chudnovsky and Seymour (Combinatorica 2012) proved the conjecture in the special case of cubic planar graphs. In our work we consider random bridgeless cubic planar graphs with the uniform distribution on graphs with n vertices. Under this model we show that the expected number of perfect matchings in labeled bridgeless cubic planar graphs is asymptotically c γ^n, where c>0 and γ~1.14196 is an explicit algebraic number. We also compute the expected number of perfect matchings in (non necessarily bridgeless) cubic planar graphs and provide lower bounds for unlabeled graphs. Our starting point is a correspondence between counting perfect matchings in rooted cubic planar maps and the partition function of the Ising model in rooted triangulations.

Joint work with Clément Requilé and Juanjo Rué.

**Video:** here

**Date:** Wednesday, Jan 13, 2021

**Time:** 12.15h (Barcelona time)

**Where: ** Zoom

**Title:** A canonical polynomial Van der Waerden's theorem.

**Speaker:** António Girão

**Abstract: **In this talk, we will give a brief overview of some fundamental results in Arithmetic Ramsey theory. Starting with the now famous Van der Waerden’s theorem we intend to give a sketch of a new proof of the canonical version of Van der Waerden’s theorem, originally proved by Erdös and Graham, since it already contains important ideas which are used in our proof of the canonical version of the Polynomial Van der Waerden’s Theorem.

Finally, we hope to give a short sketch of a proof of the canonical version of the Polynomial Van der Waerden’s Theorem which was proved in the 90’s by Bergelson and Leibman. Our proof uses beautiful ideas of Walters in his purely combinatorial proof of Bergelson and Leibman’s result.

**Video: **here

**Date:** Wednesday, Dec 16, 2020

**Time:**12.15h (Barcelona time)

**Where: ** Zoom

**Title:** Graph polynomials and choosability of planar graphs

**Speaker:** Jarek Grytczuk (Warsaw University of Technology)

**Abstract: **A graph G is k-choosable if it is colorable from arbitrary lists of colors, each of size k, assigned to the vertices of G. A famous theorem of Thomassen asserts that every planar graph is 5-choosable, whereas Voigt found planar graphs that are not 4-choosable. Recently, Zhu reproved Thomassen's theorem by using graph polynomials and the celebrated Combinatorial Nullstellensatz. By using a similar approach we proved that every planar graph can be made 4-choosable by deleting a suitable matching. This strengthens some earlier results on defective choosability of planar graphs and perhaps kindles some hope for a computer-free proof of the Four Color Theorem. We will discuss some possible directions towards this extravagant goal.

This is joint work with Xuding Zhu.

**Video:** here

**Date:** Wednesday, Dec 09, 2020**Time:** 12.15h (Barcelona time)

**Where: ** Zoom

**Title:** On the minimum bisection of random 3−regular graphs

**Speaker:** Lyuben Lichev (ENS Lyon)

**Slides**: here

**Video**: here

**Abstract: **A minimum bisection of a graph with even number of vertices is a partition of the vertices of the graph in two equal parts, which induce a bipartite graph with minimal number of edges (that is, of minimal size). Finding the size of a minimum bisection is a classical (and in general difficult) problem in graph theory and computer science. In this talk, we will concentrate on the methods, used in the recent paper https://arxiv.org/abs/2009.00598 (joint work with Dieter Mitsche) to give better asymptotically almost sure lower and upper bounds on the minimum bisection of a 3-regular graph, chosen uniformly at random. In the proof of the lower bound, we will look for a rather precise information on the structure of the two parts of a minimum bisection. In the upper bound, we will partially reuse this information in combination with classical spectral ideas.

**Date:** Wednesday, Dec 02, 2020**Time:** 12.15h (Barcelona time)

**Slides: ** here

**Video: **here

**Title:** Optimization of eigenvalue bounds for the independence and chromatic number of graph powers

**Speaker:** Miguel Àngel Fiol (UPC)

**Abstract: **The k-th power G^k of a graph G=(V,E) is the graph whose vertex set is V, and in which two distinct vertices are adjacent if and only if their distance in G is at most k. In this talk we present various eigenvalue bounds for the independence number and chromatic number of G^k, which purely depend on the spectrum of G, together with a method to optimize them. In particular, such bounds are shown to be tight for some of the so-called k-partially walk-regular, which can be seen as a generalization of distance-regular graphs. In this case, the bounds are obtained via a new family of polynomials obtained from the spectrum of a graph, called minor polynomials. Moreover these results coincide with the Delsarte's linear programming bound and, in fact, the given bounds also apply also for the Lovász theta number \theta, and the Shannon capacity of a graph \Theta. In general, our bounds for the k-independence number also work for its quantum counterpart, which is not known to be a computable parameter in general, thus justifying the use of integer programming to optimize them. In some cases, our approach has the advantage of yielding closed formulas and, so, allowing asymptotic analysis. Some of the bounds previously known in the literature follow as a corollary of our main results. Infinite families of graphs where the bounds are sharp are presented as well.

(Joint work with A. Abiad, G. Coutinho, B. D. Nogueira, and S. Zeijlemaker)

**Date:** Wednesday, Nov 11, 2020**Time:** 12.15h (Barcelona time)

**Slides: **here

**Video: ** Link to Video (UPC login required)**Title:** Hamiltonicity of random subgraphs of the hypercube.**Speaker:** Alberto Espuny-Díaz (Technische Universität Ilmenau)**Abstract: **The study of Hamiltonicity has been one of the driving forces in the development of random graph theory. I will briefly survey some of the classical benchmark results in the $G_{n,p}$ model (thresholds and hitting time results) and then discuss the analogous problem for (binomial) random subgraphs of the hypercube. Here, we have very recently obtained threshold and hitting time results for Hamiltonicity, resolving and extending a long-standing conjecture. Our proofs rely on perturbation results for subgraphs of the hypercube, which I will also discuss. The main goal of the talk will be to explain some of the main ideas behind the proof, which involves branching processes, the Rödl nibble, and absorption.

**Date:** Wednesday, Oct 21, 2020**Time:** 12.15h (Barcelona time)**Where: ** Zoom **Title:** A compactification result for the set of positive sequences (with applications to graph limits).**Speaker:** Lluís Vena (UPC, Barcelona)**Abstract: **The graph limits aims to provide a better understanding of large graphs by giving a limit object which is linked to a convergence

notion for a sequence of graphs. One of the problems that arise is the following: even when the convergent notions care about similar parameters, the different convergence notions either only works for certain families of graphs, or they trivialize for others. The best known example of this behaviour is the left-convergence introduced by Lovasz et. al., and the Benjamini-Schramm convergence for bounded degree graphs: in both cases the convergence of the sequence involves the subgraph counts (we fix the subgraph to count, such as the triangle K_3, and let the parameter of the sequence grow). For the left-convergence, if the graphs G_n are not dense, then the limit trivializes; for the Benjamini-Schramm convergence, we can only consider sequences of graphs with bounded maximum degree.

We present the following 'compactification' result: assuming the continuum hypothesis, there exists a set of positive sequences A (with the property that the quotient of every pair of sequences in A has a limit (possibly infinite)), for which, for any subsequence b of positive numbers, there exist an a in A, a constant \infty>c>0, and a subsubsequence d (indexed by I) of b such that d_n/a_n \to_{n\to \infty, n\in I} c (the limit of d along the subsequence is comparable to a). With this, we give a convergence notion that is the common generalization of the Benjamini-Schramm convergence and the left-convergence for graphs, and has the property that any sequence of graphs (with growing number of vertices) has a convergence subsequence.

This is a joint work with David Chodounsky.

**Video**: here (UPC login required)

**Date:** Thursday, June 25, 2020**Time:** 15h (Barcelona time)**Where: ** Zoom**Title:** Faster k-SAT algorithms using biased-PPSZ**Speaker:** Or Zamir, Tel Aviv University, Israel**Abstract: **The PPSZ algorithm, due to Paturi, Pudlak, Saks and Zane, is currently the fastest known algorithm for the k-SAT problem, for every k>3. For 3-SAT, a tiny improvement over PPSZ was obtained by Hertli. We introduce a biased version of the PPSZ algorithm using which we obtain an improvement over PPSZ for every k≥3. For k=3 we also improve on Hertli’s result and get a much more noticeable improvement over PPSZ, though still relatively small. In particular, for Unique 3-SAT, we improve the current bound from 1.308^n to 1.307^n.

Joint work with Thomas Dueholm Hansen, Haim Kaplan and Uri Zwick.

**Date**: Wednesday June 17, 2020**Time**: 11h (watch the time)

**Where**: Zoom

**Speaker**: Ross Kang (Radboud Univ, The Netherlands)**Title**: New investigations into the structure of locally sparse graphs (Slides available here)

**Abstract**: The structure of triangle-free graphs has deeply influenced the development of combinatorial mathematics. Both fundamental results of Mantel (1907) and of Ramsey (1930) yield global structure from the local property of having no edges in any neighbourhood.

I recently began some basic explorations in this classic area. This has led to unexpected and novel questions and developments, especially with respect to structural aspects related to independent sets and colourings in graphs. To begin I will give an overview of the history including the focus of current/recent activities.

Then I will present a new general framework for structure in locally sparse graphs. This generalises and strengthens many notable results in the area, including those of Ajtai, Komlós, Szemerédi (1980/1), Shearer (1983/1996), Kim (1995), Johansson (1996), Alon (1996), Alon, Krivelevich, Sudakov (1999), Molloy (2019), Bernshteyn (2019), and Achlioptas, Iliopoulos, Sinclair (2019). The methodology underlying this framework asymptotically cannot be improved in general, by a consideration of random regular graphs. The framework is built around a technique inspired by statistical physics --namely, a local analysis of the hard-core model-- as well as the suitable application of the Lovász local lemma. It essentially reduces the main task to a routinely verified property of the hard-core model we call local occupancy.

This talk touches on joint work with, variously, Wouter Cames van Batenburg, Ewan Davies, Louis Esperet, Rémi de Joannis de Verclos, François Pirot, Jean-Sébastien Sereni, and Stéphan Thomassé.

**Date**: Wednesday June 10, 2020 **Time**: 15h (watch the time)**Where**: Zoom link

**Speaker**: Marcelo Soares Campos (IMPA, Rio de Janeiro)

**Title**: On the number of sets with a given doubling constant

**Abstract**: We study the number of $k$-element subsets $A$ of a given abelian group $G$, such that $|A+A|\leq \lambda|A|$. Proving a conjecture of Alon, Balogh, Morris and Samotij, and improving a result of Green and Morris, who proved the conjecture for $\lambda$ fixed, we provide an upper bound on the number of such sets, when $\lambda=o(k/(\log n)^3)$, which is tight up to a factor of $2^{o(k)}$ in many cases. The main technical result we will prove, which has found other applications, is a "Container Theorem for sumsets" proved using the asymmetric container lemma, introduced by Morris, Samotij and Saxton.

**Date**: Wednesday February 26, 2020**Time**: 12h**Where**: Room C3-005, Campus Nord UPC**Speaker**: Miquel Àngel Fiol (UPC Barcelona)**Title**: On d-Fibonacci digraphs.**Abstract**: The d-Fibonacci digraphs F(d,k), introduced in this work, have the number of vertices following generalized Fibonacci-like sequences. They can be defined both as digraphs on alphabets and as iterated line digraphs. Here we study some of their nice properties. For instance, F(2,k) has diameter d+k-2 and is semi-pancyclic, that is, it has a cycle of every length between 1 and \ell, with \ell\in\{2k-2,2k-1\}. Moreover, it turns out that several other numbers of F(d,k) (of closed l-walks, classes of vertices, etc.) also follow the same linear recurrences as the numbers of

vertices of the d-Fibonacci digraphs.

Joint work with C. Dalfó

**Date**: Wednesday January 22, 2020**Time**: 12h**Where**: Room C3-005, Campus Nord UPC**Speaker**: Alberto Larrauri (UPC Barcelona)**Title**: On the evolution of the set of limiting probabilities of first order properties for sparse random graphs.**Abstract**: It is known that for any first order property of graphs P, the limit probability that the random graph G(n,c/n) satisfies P as n tends to infinity exists and varies in a smooth way with c. An immediate consequence of this is that first order properties cannot individually ``capture'' the phase transition that occurs in G(n,c/n) when c=1. For each c we consider the set of limiting probabilities L_c={lim Pr(G(n,c/n) satisfies P): P first order property} We ask the question of whether we can ``detect" the phase transition in G(n,c/n) through the changes in L_c. We arrive at a negative answer and show that there is a constant c_0\approx 0.93... such that the closure of L_c is the whole interval [0,1] when c>= c_0 and this closure is a finite union of disjoint intervals when c< c_0. Moreover, the number of intervals forming the closure tends to infinity as c tends to zero. The same question can be asked in the setting of random uniform hypergraphs and similar results are obtained.

This is joint work with Marc Noy and Tobias Muller.

Date: **Wednesday December 18, 2019**

Time: **12h**

Where: **Room C3-005, Campus Nord UPC**

Speaker: **Lluís Alemany (UPC Barcelona)**

Title: **Edge crossings in random linear arrangements****Abstract**: In spatial networks, vertices are arranged in some space and edges may cross. Here study two statistical properties of edge crossings in general spaces, with a special focus on one-dimensional layouts, where edges may cross when drawn above the vertex sequence as it happens in linguistic and biological networks.

Here we investigate the distribution of edge crossings under the null hypothesis of a uniformly random arrangement of the vertices. We generalize the existing formula for the expectation of this number in trees to any network and derive a general expression for the variance of the number of crossings relying on a novel characterization of the algebraic structure of that variance in an arbitrary space. We provide compact formulae for the expectation and the variance in complete graphs, cycle graphs, one-regular graphs and various kinds of trees (star trees, quasi-star trees and linear trees). In these networks, the scaling of expectation and variance as a function of network size is asymptotically power-law-like.

I will also outline some applications and future research directions beyond the current arxiv version of this work (https://arxiv.org/abs/1910.03926).

**____________________________**

Date: **Wednesday December 11, 2019**

Time: **12h**

Where: ** Room C3-005, Campus Nord UPC**

Speaker: **Juanjo Rué (UPC Barcelona)**

Title: An Erdös–Fuchs Theorem for Ordered Representation Functions

Abstract: This is a joint work with Gonzalo Cao-Labora and Christoph Spiegel (UPC).

**____________________________**

Date: **Wednesday November 13, 2019**

Time: **12h**

Where: ** Room C3-005, Campus Nord UPC**

Speaker: **Pablo Oviedo (UPC Barcelona)**

Title: **Universal intervals in the homomorphism order of directed graphs**

Abstract**: **We show a density theorem for the class of finite proper trees ordered by the homomorphism order. We strengthen this result by showing

that every interval of proper trees (not homomorphic to paths)is in fact universal, that is, it contains every countable partial order as a suborder. We also show that every interval of the class of cyclic digraphs ordered by the homomorphism order is universal. We end bydiscussing the consequences of these results on the class of all finite digraphs.

This is joint work with Jan Hubicka and Jaroslav Nesetril.

**____________________________**

Date: **Wednesday November 6, 2019**

Time: **12h**

Where: **Room C3-005, Campus Nord UPC**

Speaker: **Jaroslav Nesetril (Institute of Theoretical Computer Science,** **Charles University, Prague)****Title**: Sparse representations of algebras

**Abstract: **Representations of groups, monoids and categories by isomorphisms and homomorphisms of graphs in a surprisingly close relatinship to sparse hierarchy of classes of graphs.

A joint work with P. Ossona de Mendez (Paris,Prague).

**____________________________**

**Wednesday, October 16, 2019**

**12h**

**Room C3-005, Campus Nord UPC**

**Arindam Biswas (U Wien)**

Title:

**Minimal nets in metric spaces and minimal complements in groups**

**____________________________**

Date: **Thursday October 3, 2019**

Time: **12h**

Where: **Room C3-005, Campus Nord UPC**

Speaker:** Miquel Angel Fiol (Department of Mathematics, UPC Barcelona)**

Title: **A new class of polynomials from the spectrum of a graph, and its** **application to bound the k-independence number**

Abstract: The k-independence number of a graph is the maximum size of a set of vertices at pairwise distance greater than $k$. A graph is called walk-regular, if the number of closed walks of a given length l, rooted at a vertex v, only depends on l. In particular, a distance-regular graph is also walk-regular (but the converse does not hold). In this work, we introduce a new family of polynomials obtained from the spectrum of a graph. These polynomials, together with the interlacing technique, allow us to give tight spectral bounds on the $k$-independence number of a walk-regular graph.

Date: **Wednesday September 25, 2019**

Time: **12h**

Where: **Room C3-005, Campus Nord UPC**

Speaker:** Maryam Sharifzadeh (Mathematics Institute, Warwick)**

Title: ** Asymptotic Structure for the Clique Density Theorem**

Abstract: The famous Erdös-Rademacher problem asks for the smallest number of r-cliques in a graph with the given number of vertices and edges. Despite decades of active attempts, the asymptotic value of this extremal function for all r was determined only recently, by Reiher. In this talk, we describe the asymptotic structure of all almost extremal graphs. This task for r=3 was previously accomplished by Pikhurko and Razborov. This is joint work with Jaehoon Kim, Hong Liu, and Oleg Pikhurko.

Date: **Wednesday September 18, 2019**

Time: **12h**

Where: **Room C3-005, Campus Nord UPC**

Speaker: **Marc Vinyals (Tata Institute of Fundamental Research, Mumbai)**

Title: **Equality Alone Does not Simulate Randomness**

Abstract: Randomness can provide an exponential saving in the amount of communication needed to solve a distributed problem, and the canonical example of this is equality. However, in all examples where randomness helps having access to an equality oracle would be enough to solve the problem efficiently. Is equality all there is to randomness?

In this talk we show that equality is not enough. More precisely, we exhibit a function that can be solved efficiently using randomized protocols but not with only access to an equality oracle.

Joint work with Arkadev Chattopadhyay and Shachar Lovett.

**12th September, 2019**,

**12h**

**Room C3-005, Campus Nord UPC**

**Dimitrios Thilikos**(CNRS, LIRMM & Dept. Math., NKUA)

**The parameterized complexity of F-M-Deletion on partial k-trees: a tight classification.**

Abstract: For a fixed connected graph H, the {H}-M-Deletion problem asks, given a graph G, for the minimum number of vertices that intersect all minor models of H in G. It is known that this problem can be solved in time f(tw) n^{O(1)}, where tw is the treewidth of G. We determine the asymptotically optimal function f(tw), for each possible choice of H. Namely, we prove that, under the ETH, f(tw)=2^{Θ(tw)} if H is a contraction of the chair or the banner, and f(tw)=2^{Θ(tw log tw)} otherwise.

The proof combines several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, Bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. Joint work with Julien Baste and Ignasi Sau

**____________________________**

This seminar is partially supported by ERC Consolidator Research Grant ERC-2014-CoG 648276 AUTAR

**____________________________**