# LIMDA Seminar (2020-2021)

**ALBCOM - Algorithms and Theory of Computation**

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

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

## Next talks

Autumn term 2020-21 will run on Wednesdays 12:15 online.

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

## Previous sessions

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

**____________________________**