LIMDA Joint Seminar Announcements 2017-2018

Forthcoming sessions and activities

Date: Wednesday  January 17, 2018

Time: 12h

Where:  Room C3-005, Campus Nord UPC

Speaker: Mattew Tointoin (Université de Neuchâtel, Switzerland.)

Title:  TBA

Previous sessions and activities

Date: Wednesday December 13, 2017

Time: 12h

Where:  Room C3-005, Campus Nord UPC

Speaker: Simon Griffiths (Pontifical Catholic University of Rio de Janeiro)

Title:  Title: Moderate deviations of subgraph counts

Abstract: We study the probability of deviations of subgraph counts in the Erd\H os-R\'enyi random graph $G(n,m)$.  In particular, for a particular range of moderately large deviations we determine the associated rate asymptotically.  We also discuss the relation between subgraph count deviations.

Based on joint work with Christina Goldschmidt and Alex Scott.

Date: Tuesday November  28, 2017

Time: 14h

Where:  Room C3-005, Campus Nord UPC

Speaker: Pablo Candela (UAM-ICMAT)

Title:  On sets with small sumset in the circle

Abstract:  It is known by a theorem of Raikov that for any measurable subset A of the circle group, if the sumset A+A has Haar measure |A+A| <1, then this measure must be at least 2|A|. We shall discuss recent joint work with Anne de Roton concerning subsets A of the circle with |A+A| < (2+c) |A|. The results include partial progress towards an analogue in this setting of a conjecture of Freiman known as the 3k-4 conjecture. We shall also discuss applications of these results to the problem of estimating how large can the measure of a subset of the circle be if the set avoids solutions to an equation of the form x+y=kz, for k>2 an integer.

Date: Wednesday November  22, 2017

Time: 12h

Where:  Room C3-005, Campus Nord UPC

Speaker: M. Ángeles Serrano (ICREA-UB)

Title: Multiscale unfolding of real networks by geometric renormalization

Abstract: Renormalization has proven to be a very powerful method for a rigorous investigation of systems as viewed at different distance scales. When implemented as a renormalization group to explore critical phenomena and universal properties, it is based on geometric concepts like self-similarity and scale-invariance. In complex networks multiple scales coexist but, due to the small world property, are so entangled that a proper definition of these symmetries remained elusive. However, complex networks display a hidden metric structure that can be exploited to define a geometric renormalization group.

We find that real scale-free networks embedded in a hidden metric space show geometric scaling under this renormalization group transformation. This feature enables us to unfold real networks in a self-similar multilayer shell which reveals the coexisting scales and their interplay. The multiscale unfolding brings about immediate practical applications. Among many possibilities, it yields a natural way of building high-fidelity smaller-scale replicas of large real networks, and sustains the design of a new multiscale navigation protocol in hyperbolic space which boosts the success of single-scale versions.

Date: Wednesday November  15, 2017

Time: 12h

Where:  Room C3-005, Campus Nord UPC

Speaker: Anna de Mier (UPC)

Title:  Approximating and decomposing clutters with matroids

Abstract: There are several clutters (aka antichains of sets) that can be associated with a matroid, as the clutter of circuits, the clutter of bases or the clutter of hyperplanes. This talk is about the following question: given an arbitrary clutter L, which are the matroidal clutters that are closest to L? To answer it we must first decide on the meaning of closest, and select one of the different matroidal clutters.
We show that for almost all reasonable choices above there is a finite set of matroidal clutters that approximate L and, moreover, that L can be recovered from them. We speak in this case of a decomposition of L. In addition to proving the existence of the decompositions
theoretically, we also give an algorithmic procedure to compute them.
The same framework also allows us to decompose matroidal clutters of non-representable matroids into representable ones, or into other classes of matroids. More generally, we prove that under mild conditions one can decompose the the clutter L with members of a favourite family of clutters, not necessarily a matroidal one.

This is joint work with Jaume Martí-Farré.

Date: Wednesday November 8, 2017

Time: 12h

Where:  Room C3-005, Campus Nord UPC

Speaker: Maximilian Wötzel (UPC-BGSMath)

Title:  On Testing Minor-Freeness in Bounded Degree Graphs with One-Sided Error

Abstract: We present a one-sided error property testing algorithm for H-minor freeness in bounded-degree
graphs for any minor H that is a minor of the (k \times 2)-grid (for any positive integer k). This
includes, for example, testing whether a graph is a cactus graph and testing minor-freeness for minors
which are cycles with parallel chords. The query complexity of our algorithm in terms of the number of
vertices in the graph, n,  is \tilde{O}(n^{2/3} / \eps^5).

Czumaj et~al. showed that C_k-minor freeness can be tested with query complexity \tilde{O}(\sqrt{n}). In
contrast to these results, we analyze the structure of the graph and show that either we can find a
subgraph of sublinear size that includes the forbidden minor, H, or we can find a pair of disjoint
subsets of vertices whose edge-cut is large, and such that the induced subgraph of each subset is
connected. We then prove a combinatorial lemma which shows that the latter structure includes H as a
minor.

Date: Wednesday October 25, 2017

Time: 12h

Where:  Room C3-005, Campus Nord UPC

Speaker: Christoph Spiegel (UPC)

Title:  Sparse Supersaturation and Extremal Results for Linear Homogeneous SystemsAbstract: We study the thresholds for the property of containing a solution to a linear homogeneous system in random sets. We expand a previous sparse Szémeredi-type result of Schacht to the broadest class of matrices possible. We also provide a shorter proof of a sparse Rado result of Friedgut, Rödl, Ruciński and Schacht based on a hypergraph container approach due to Nenadov and Steger. Lastly we further extend these results to include some solutions with repeated entries using a notion of non-trivial solutions due to Rúzsa as well as Rué et al.

Date: Wednesday October 18

Time: 12h

Where:  Room C3-005, Campus Nord UPC

Speaker: Gonzalo Fiz (UPC-BGSMath)

Title: The triangle-free process and R(3,k)

Abstract: Consider the following random graph process (G_m)_{m\in \N} on the vertex set [n] . Let G_0 be the empty graph and, for each m \in \N, let G_m be obtained from G_{m−1} by adding a single edge, chosen uniformly from those non-edges of G_{m−1} which do not create a triangle. The process ends when we reach a maximal triangle-free graph; we denote by G_{n,\triangle} this (random) final graph. This "triangle-free process" was suggested by Bollob\'as and Erd\H{o}s in 1990 as a possible method of producing good Ramsey graphs, but until Bohman's breakthrough paper in 2009, which determined the order of magnitude of e(G_{n,\triangle}), very little was known about the random triangle-free graph G_{n,\triangle} it produces.

A technique which has proved extremely useful in the study of random graph processes is the so-called ‘differential equations method’, which was introduced by Wormald in the late 1990s. In this method, the idea is to ‘track’ a collection of graph parameters, by showing that (with high probability) they closely follow the solution of a corresponding family of differential equations.

The aim of this talk is to give an overview of this method and to discuss a recent refinement of Bohman's result, which determines asymptotically the number of edges in G_{n,\triangle}, and moreover shows that it shares many properties with the Erd\H{o}s-R\'enyi random graph G(n,m) of the same density. As an application, we improve Kim's lower bound on the Ramsey number R(3,k), obtaining a bound within a factor of four of Shearer's upper bound.

This is joint work with Simon Griffiths and Rob Morris. Similar results were obtained independently by Tom Bohman and Peter Keevash.