# LIMDA Seminar (2019-2020)

**ALBCOM Seminar on Algorithms and Theory of Computation**

**COMBGRAPH Seminar on Combinatorics, Graph Theory and Applications**

**GAPCOMB Geometric, Algebraic and Probabilistic combinatorics**

## Next talks

**Date**: Wednesday January 22, 2019**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.

## Previous sessions

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

**____________________________**

**Previous sessions this year**

**Date**:

**Speaker**:

**Title**:

**Abstract**:

**____________________________**