Tag Archives: online talks
Online talk: Sarah Allred
Monday, November 23, 3pm ET (8pm GMT, 9am Tue NZDT)
Sarah Allred, LSU
Unavoidable Induced Subgraphs of Large 2-connected Graphs
YouTube
Abstract:
Online talk: Jakob Kneip
Monday, November 16, 3pm ET (8pm GMT, 9am Tue NZDT)
Jakob Kneip, Universität Hamburg
Tangles are decided by weighted vertex sets
Youtube,
Slides (view pdf)
Abstract:
Tangles are a way to capture clusters or highly cohesive regions in graphs: a tangle in a graph declares for each low-order separation one of the two sides of that separation as ‘big’, and does so in such a way that no three ‘small’ sides together cover the graph. Most types of clusters in graphs — for instance clique- or grid-minors — give rise to such a tangle by declaring as ‘big’ for each separation the side which contains the majority of the vertices of that cluster.
An open question in the theory of tangles is whether a converse to this holds: given a tangle in a graph, can we find a set of vertices such that the ‘big’ side of each separation is precisely the side which contains the majority of the set’s vertices? A positive answer to this would validate the intuition that the sides declared as ‘big’ by a tangle are in fact big in some sense.
In joint work with Christian Elbracht and Maximilian Teegen we show that a fractional version of this is true: given a tangle we construct a weight function on the vertices such the ‘big’ side of each separation is exactly the side with higher total weight. We also show that our result extends to tangles of hypergraphs as well as to edge tangles, which are based on cuts rather than vertex separations. Curiously though one cannot achieve both extensions simultaneously: there are edge tangles of hypergraphs that are not defined by such a weight function on the vertices.
Online talk: James Davies
Monday, November 9, 3pm ET (8pm GMT, 9am Tue NZDT)
James Davies, University of Waterloo
Geometric intersection graphs with large girth and chromatic number
Youtube
Abstract:
We prove that both the classes of intersection graphs of axis-aligned boxes in $\mathbb{R}^3$ and intersection graphs of straight line segments in $\mathbb{R}^3$ contain graphs with arbitrarily large girth and chromatic number.