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
Treewidth of random geometric graphs
14:35 - 14:50 Break
14:50 - 15:10 Tom van der Zanden
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)


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.


The workshop is made possible by the the Department of Mathematics of the University of Utrecht.

UU logo