2020-21 LIMDA Seminar
Date: Wednesday, 30 Jun, 2021
Time: 15.00h (Barcelona time)
Title: RandNET Seminar
Speaker: Maya Stein (Santiago de Chile) and James Martin (Oxford)
Link: https://randnet.upc.edu/seminar/
Date: Wednesday, 02 Jun, 2021
Time: 12.15h (Barcelona time)
Where: Zoom
Title: Geometry of high genus maps
Speaker: Baptiste Louf (Uppsala)
Abstract: Maps are discrete surfaces built by gluing polygons along their sides (or, alternatively, they can be seen as graphs embedded in surfaces). They have been given a lot of attention for several decades now, and in this talk we will be interested in the geometric properties of large random maps.
This question has been well studied in the case of planar maps (i.e. maps of the sphere), and more recently extended to any surface when the topology is fixed. Here, we are interested in yet another regime, that we call high genus maps, in which the genus of the surface grows at the same time as the size. These objects naturally exhibit hyperbolic properties. I will give an overview of the existing results and open problems.
Date: Wednesday, 26 May, 2021
Time: 15.00h (Barcelona time)
Title: RandNET Seminar
Speaker: Lutz Warnke (GATech)
Link: https://randnet.upc.edu/seminar/
Date: Wednesday, 19 May, 2021
Time: 12.15h (Barcelona time)
Where: Zoom
Title: On Motzkin's problem in the circle group
Speaker: Pablo Candela (UAM)
Abstract: Given a finite subset $D$ of the interval $(0,1)$, if a Borel set $A\subset [0,1)$ contains no pair of elements whose difference modulo 1 is in $D$, then how large can the Lebesgue measure of $A$ be? This is the analogue in the circle group of a well-known problem of Motzkin, originally posed for sets of integers. We make a first treatment of this circle-group analogue, for finite sets $D$ of missing differences, using techniques from ergodic theory, graph theory and the geometry of numbers. Our results include an exact solution when $D$ has two elements, at least one of which is irrational. When every element of $D$ is rational, the problem is equivalent to estimating the independence ratio of a circulant graph. In the case of two rational elements, we give an estimate for this ratio in terms of the odd girth of the graph, which is asymptotically sharp and also recovers a classical solution of Cantor and Gordon to Motzkin's original problem for two missing differences. This is joint work with Carlos Catalá, Juanjo Rué and Oriol Serra.
Date: Wednesday, 05 May, 2021
Time: 12.15h (Barcelona time)
Where: Zoom
Title: Nested cycles with no geometric crossings.
Speaker: Irene Gil (Warwick)
Abstract: In this talk, we answer the following question posed by Erdös in 1975: what is the smallest function $f(n)$ for which all graphs with $n$ vertices and $f(n)$ edges contain two edge-disjoint cycles $C_1$ and $C_2$, such that the vertex set of $C_2$ is a subset of the vertex set of $C_1$ and their cyclic orderings of the vertices respect each other? We prove the optimal linear bound $f(n)=O(n)$ using sublinear expanders. This is joint work with Jaehoon Kim, Younjin Kim and Hong Liu.
Date: Wednesday, Apr 28, 2021
Time: 15.00h (Barcelona time)
Title: RandNET Seminar: Rui Castro
Speakers: Detecting a planted community in an inhomogeneous random graph
Link: https://randnet.upc.edu/seminar/
Date: Wednesday, 21 Apr, 2021
Time: 12.15h (Barcelona time)
Where: Zoom
Title: Quotientopes
Speaker: Vincent Pilaud (LIX-Polytechnique and CNRS, Paris)
Abstract: This talk will survey combinatorial and geometric properties of lattice quotients of the weak order on permutations, whose prototype is the classical Tamari lattice on binary trees. We will see in particular that any weak order quotient can be realized by a convex polytope called quotientope, generalizing the associahedron. Based on joint work with Francisco Santos, Arnau Padrol and Julian Ritter.
Date: Wednesday, 14 Apr, 2021
Time: 12.15h (Barcelona time)
Where: Zoom
Title: Bounding Obstructions sets: the cases of apices of minor closed classes
Speaker: Dimitrios M. Thilikos (LIRMM and CNRS, Montpellier)
Abstract: Given a minor-closed graph class {\cal G}, the (minor) obstruction of {\cal G} is the set of all minor-minimal graphs not in {\cal G}. Given a non-negative integer k, we define the k-apex of {\cal A} as the class containing every graph G with a set S of vertices whose removal from G gives a graph on {\cal G}. We prove that every obstruction of the k-apex of {\cal G} has size bounded by some 4-fold exponential function of p(k) where p is a polynomial function whose degree depends on the size of the minor-obstructions of {\cal G}. This bound drops to a 2-fold exponential one when {\cal G} excludes some apex graph as a minor (i.e., a graph in the $1$-apex of planar graphs). Joint work with Ignasi Sau and Giannos Stamoulis
Date: Wednesday, 07 Apr, 2021
Time: 12.45h (Barcelona time) (NOTE THE UNUSUAL TIME)
Video: here (UPC login required)
Title: On the complexity of finding large odd induced subgraphs and odd colorings
Speaker: Ignasi Sau (LIRMM and CNRS, Montpellier)
Abstract: This talk is about the problems of finding, given a graph $G$, a largest induced subgraph of $G$ with all degrees odd (called an odd subgraph), and the smallest number of odd subgraphs that partition $V(G)$. We call these parameters $mos(G)$ and $\chi_{odd}(G)$, respectively. We will discuss (some of) the following results:
- Deciding whether $\chi_{odd}(G) \leq q$ is polynomial-time solvable if $q \leq 2$, and NP-complete otherwise.
- FPT algorithms in time $2^{O(rw)}poly(n)$ and $2^{O(q \cdot rw)}poly(n)$ to compute $mos(G)$ and to decide whether $\chi_{odd}(G) \leq q$ on an $n$-vertex graph $G$ of rank-width at most $rw$, respectively. The dependency on rank-width is asymptotically optimal under the ETH.
- Some tight bounds for these parameters on restricted graph classes or in relation to other parameters.
Joint work with Rémy Belmonte, available at arXiv:2002.06078.
Date: Wednesday, Mar 24, 2021
Time: 15.00h (Barcelona time)
Title: 2-session RandNET Seminar: "Random planar graphs - results and conjectures" and "Maps of unfixed genus and blossoming trees"
Speakers: Benedikt Stuffler (TUWien, Vienna) and Eric Fusy (LIX-Polytechnique, Paris)
Link: https://randnet.upc.edu/seminar/
Date: Wednesday, 10 Mar, 2021
Time: 12.15h (Barcelona time)
Where: Zoom
Title: Algorithmic extensions of the Bollobás-Häggkvist conjecture
Speaker: Viresh Patel (UVA, Amsterdam)
Abstract: Dirac's Theorem is a classical result in graph theory stating that every n-vertex graph with minimum degree at least n/2 has a Hamilton cycle. If we restrict to regular graphs (and impose some mild connectivity conditions), we might hope to lower the degree threshold: in that direction, Bollobás and Häggkvist independently conjectured that every k-connected, D-regular, n-vertex graph with D≥n/(k+1) has a Hamilton cycle. Although the conjecture turns out to be false for k≥4, one might still wonder whether Hamiltonicity is easier to detect in regular (dense) graphs. We investigate this question. This is joint work with Fabian Stroh.
Video: here (UPC login required)
Date: Wednesday, Feb 24, 2021
Time: 15.00h (Barcelona time)
Title: 2-session RandNET Seminar: "Network archeology: a few results and many questions" and "The design of algorithms for the production of training data"
Speakers: Gábor Lugosi (UPF, Barcelona) and Élie de Panafieu (Nokia-Bell Labs)
Link: https://randnet.upc.edu/seminar/
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
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)
Share: