2019-20 LIMDA Seminar

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