# LIMDA Seminar

**ALBCOM - Algorithms and Theory of Computation**

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

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

## Next talk

**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.

## Previous sessions

**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

**____________________________**