# 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, 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

## Previous sessions

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

**____________________________**