Afternoon on Probability and Combinatorics
This will be an afternoon with lectures on new developments in random graphs and (probabilistic) combinatorics.
All talks are in the Belle van Zuylenzaal of the Academiegebouw (Domplein 29).
The Academiegebouw is within walking distance of Utrecht Centraal train station. Alternatively, you can take bus 28 (direction: De Uithof P+R, stop: Janskerkhof).
Following the programme, the PhD defense of Anshui Li will take place in the same building. The audience is of course very welcome to attend this also.
(Preliminary) Programme
| 13:15 - 13:30 | Coffee and registration | |
| 13:30 - 14:15 |
Jan van den Heuvel (London School of Economics) | Can the circle be closed? |
| 14:15 - 14:35 |
Anshui Li (Utrecht) | Treewidth of random geometric graphs |
| 14:35 - 14:50 | Break | |
| 14:50 - 15:10 |
Tom van der Zanden (Utrecht) | Subexponential Algorithms for Subgraph Isomorphism (and related problems) on Minor-Free Graphs |
| 15:10 - 15:55 |
Josep Diaz (UPC Barcelona) | Moran process for digraphs |
| 15:55 - 16:10 | Break | |
| 16:10 - 16:35 |
Ross Kang (Radboud Universiteit Nijmegen) | Colourings involving sparse or dense sets |
| 16:35 - 17:20 |
Mathew Penrose (Bath University) | Isolated points for inhomogeneous random graphs |
| 18:00 - 19:00 | PhD defense of Anshui Li (elsewhere in the building) |
Abstracts
| Speaker: | Jan van den Heuvel (London School of Economics) |
| Title: | Can the circle be closed? |
| Abstract: | Given the collection of vectors formed by two (or more) bases of an n-dimensional vector space, it is fairly straightforward to see that these vectors can be put in a linear ordering such that every n consecutive vectors form a basis. But is it possible to put those vectors in a circular ordering such that every n cyclically consecutive vectors form a basis? And in general, when can a collection of vectors be put in such a circular ordering? This kind of questions were first asked in 1988. In this talk we look at what is known about the problem and at the many open problems that remain. |
| Speaker: | Anshui Li (Utrecht) |
| Title: | Treewidth of random geometric graphs |
| Abstract: | We prove a conjecture of Mitsche and Perarnau stating that the treewidth of the random geometric graph \(G(n,r)\) satisfies \(\text{tw}(G(n,r)) = \Theta( r\sqrt{n} )\) for all \(r > r_c\), in which \(r_c\) is the threshold radius for the appearance of the giant component. |
| Speaker: | Tom van der Zanden (Utrecht) |
| Title: | Subexponential Algorithms for Subgraph Isomorphism (and related problems) on Minor-Free Graphs |
| Abstract: | Subgraph Isomorpism is the problem of determining whether a host graph \(G\) contains a subgraph isomorphic to a pattern graph \(P\). We show that this problem can be solved in subexponential \((2^{O(n/\log n)})\) time if \(P\) excludes a fixed graph \(H\) as minor and \(G\) has sublinear treewidth. As a special case of our result, we can determine whether a planar graph \(G\) contains an arbitrary graph P as an isomorphic subgraph in \(2^{O(n/\log n)}\) time. We show that, under certain complexity-theoretic assumptions, our algorithm is optimal. |
| Speaker: | Josep Diaz (UPC Barcelona) |
| Title: | Moran Process for directed graphs |
| Abstract: |
We survey recent results on the Moran's process of infection on directed and undirected graphs. (joint work with L. Goldberg, D. Richerby, M. Serna) |
| Speaker: | Ross Kang (Radboud Universiteit Nijmegen) |
| Title: | Colourings involving sparse or dense sets |
| Abstract: |
Two of the most basic substructures in a graph are the cliques
(densest possible) and the stable sets (sparsest possible). The desire
to understand and quantify the behaviour of such sets is at the root
of long-standing and central questions in probabilistic and extremal
combinatorics. Even restricted to random (models of) graphs, their
study is of great importance because of connections to statistical
physics, optimisation, complex networks, machine learning and more. In certain situations, one might be satisfied with substructures that are "close" to cliques or stable sets. In this talk, we consider two classes of natural problems along these lines, where instead of cliques or stable sets, we seek "dense" or "sparse" sets. (The quoted terms could have different interpretations.) For the first, we describe generalisations of the well-known result of Bollobas (cf. Matula) on the chromatic number of the random graph. For the second, we consider the so-called quasi-Ramsey numbers as introduced by Erdos and Pach. Among other results, we answer one of their main questions. A basic link between these two classes of problems is that in both we need a good grasp of the largest dense or sparse subsets of the random graph. (Less importantly, both involve colourings.) The results mentioned are joint works with Colin McDiarmid; with Nicolas Broutin; with Eoin Long, Janos Pach, Viresh Patel and Guus Regts. |
| Speaker: | Mathew Penrose (Bath University) |
| Title: | Isolated points for inhomogeneous random graphs. |
| Abstract: | Consider a random graph with n vertices placed at random in some space (for example, Euclidean space) and each pair of points connected with a probability that depends on their location (for example, via the distance between them). We discuss Poisson approximation for the number of isolated vertices in this model as n becomes large with the connection function function varying with n. One reason to be interested is because absence of isolated points is necessary for connectivity and is often asymptotically sufficient, in probability. |
Sponsor
The workshop is made possible by the the Department of Mathematics of the University of Utrecht.
