2017-18 LIMDA Seminar
Date: April 12th 2018
Speaker: Nina Kamcev (ETH Zurich)
Title: Zero forcing in random and pseudorandom graphs
Abstract: A subset S of initially infected vertices of a graph G is called forcing if we can infect the entire
graph by iteratively applying the following process. At each step, any infected vertex which has a unique
uninfected neighbour, infects this neighbour. The forcing number of G is the minimum cardinality of a
forcing set in G. It was introduced independently as a bound for the minimum rank of a graph, and as a
tool in quantum information theory.
The focus of this talk is on the forcing number of the random graph. Furthermore, we will state our
bounds on the forcing number of pseudorandom graphs and related problems.
The results are joint work with Thomas Kalinowski and Benny Sudakov.
uninfected neighbour, infects this neighbour. The forcing number of G is the minimum cardinality of a
forcing set in G. It was introduced independently as a bound for the minimum rank of a graph, and as a
tool in quantum information theory.
The focus of this talk is on the forcing number of the random graph. Furthermore, we will state our
bounds on the forcing number of pseudorandom graphs and related problems.
The results are joint work with Thomas Kalinowski and Benny Sudakov.
____________________________
Date: March 21th 2018
Speaker: Marc Noy (UPC, Barcelona)
Title: Logic and graphs on surfaces
Abstract: The zero-one law holds in a class G of graphs if, for each graph property A expressible in first order (FO) logic, the probability that A is satisfied converges to either 0 or 1 when the number of vertices goes to infinity. We say that the convergence law holds if every FO property has a limiting probability, not necessarily 0 or 1.
We will discuss zero-one and convergence laws in the class of graphs embeddable on a fixed surface in FO
and also in monadic second order (MSO) logic, where one can quantify over sets of vertices in addition to quantifying over vertices. For FO properties the results do not depend on the surface, but for MSO there is a striking difference between the plane (or the sphere) and surfaces of higher genus.
Based on joint work with P. Heinig, T. Müller and A. Taraz, and with A. Atserias and S. Kreutzer.
We will discuss zero-one and convergence laws in the class of graphs embeddable on a fixed surface in FO
and also in monadic second order (MSO) logic, where one can quantify over sets of vertices in addition to quantifying over vertices. For FO properties the results do not depend on the surface, but for MSO there is a striking difference between the plane (or the sphere) and surfaces of higher genus.
Based on joint work with P. Heinig, T. Müller and A. Taraz, and with A. Atserias and S. Kreutzer.
____________________________
Date: January 16th 2018
Speaker: Matthew Tointon (Université de Neuchâtel, Switzerland)
Title: Commuting probability in infinite groups
Abstract: In a finite group G one can ask what the probability is that two elements chosen independently uniformly at random commute. It is clear that if G has an abelian subgroup of bounded index then this probability should be bounded from below. In the 1980s Peter Neumann proved a beautiful quantitative converse to this observation.
Antolin, Martino and Ventura consider the same question for infinite groups, choosing the two random elements with respect to a certain limit of finite probability measures. They conjecture that for any 'reasonable' sequence of measures Neumann's result should still hold. They also prove some special cases of this conjecture.
In this talk I will show that the Antolin-Martino-Ventura conjecture holds with effective quantitative bounds if we take the sequence of measures defined by the successive steps of a simple random walk, or the uniform measures on a Folner sequence. I will also present a concrete interpretation of the word 'reasonable' that is sufficient to force a sequence of measures to obey the conjecture. If I have time I will present an application to conjugacy growth.
____________________________
Date: December 13th 2017
Speaker: Simon Griffiths (Pontifical Catholic University of Rio de Janeiro)
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: November 28, 2017
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: November 22nd 2017
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
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é.
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: November 8th 2017
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: October 25th 2017
Speaker: Christoph Spiegel (UPC)
Title: Sparse Supersaturation and Extremal Results for Linear Homogeneous Systems
Title: Sparse Supersaturation and Extremal Results for Linear Homogeneous Systems
Abstract: 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: October 18th 2017
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.
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.
Share: