SiGMa 2017

Abstracts for the invited talks

Nathan Bowler, Locally finite matroids

Topological infinite graph theory is built on the fact that many statements which are true for finite graphs and false for infinite graphs can be rescued by interpreting statements about paths or cycles as about topological arcs or circles in the so-called end compactification of the graph. One reason this works is that there is an associated infinite matroid whose cycles are the edge sets of these topological circles. However, many results in topological infinite graph theory rely on the assumption that the graph is locally finite (all vertices have finite degree). After surveying some of this background, we will show how a new notion of local finiteness for infinite matroids allows us to understand this phenomenon from a matroidal perspective.

Johannes Carmesin, Embedding 2-complexes in 3-space

We present an analogue of Kuratowski’s theorem for embeddability in 3-space of simply connected 2-complexes.

Maria Chudnovsky, Coloring graphs with forbidden induced subgraphs

The problem of testing if a graph can be colored with a given number $k$ of colors is NP-complete for every $k>2$. But what if we have more information about the input graph, namely that some fixed graph $H$ is not present in it as an induced subgraph? It is known that the problem remains NP-complete even for $k=3$, unless $H$ is the disjoint union of paths. We consider the following two questions:

For which graphs $H$ is there a polynomial time algorithm to $3$-color (or in general $k$-color) an $H$-free graph?
For which graphs $H$ are there finitely many $4$-critical $H$-free graphs?

This talk will survey recent progress on these questions, and in particular give a complete answer to the second one.

Penny Haxell, Algorithms for independent transversals

An independent transversal (IT) in a vertex-partitioned graph $G$ is an independent set in $G$ consisting of one vertex in each partition class. This is a very basic notion that comes up in many combinatorial problems. There are various criteria that guarantee the existence of an IT in a given graph $G$. For example, if each partition class has size at least $2\Delta(G)$ then $G$ has an IT. The known proofs of these criteria do not give efficient algorithms for actually finding an IT. Here we discuss appropriate weakenings of such results that do have effective proofs.

Dan Král, Analytic models of large graphs

The theory of graph limits provides analytic tools to study large graphs. Such tools have found applications in various areas of computer science and mathematics; they are also closely linked to the flag algebra method, which changed the landscape of extremal combinatorics. We will present an introduction to this rapidly developing area of graph theory and survey some of the recent results obtained in this area.

Sergey Norin, Relaxations of Hadwiger's conjecture

Hadwiger's conjecture states that every simple graph with no $K_{t}$ minor can be properly colored with $t-1$ colors. While the conjecture in full generality appears to be out of reach, in the last three years several relaxations have been proven. In these relaxations one considers colorings such that every color class induces a subgraph with bounded maximum degree or with bounded component size. We will survey recent results on such improper colorings of minor-closed classes of graphs.

James Oxley, Structural tools for $2$-polymatroids

For a graph $G$ and a subset $X$ of $E(G)$, let $r(X)$ be the number of vertices incident with some edge in $X$. From the pair $(E(G),r)$, which is an example of a $2$-polymatroid, one can detemine $G$ up to isolated vertices, and one can recognize matchings in $G$. The cycle matroid in $G$ does not allow the determination of either of these things. Loosely speaking, a $2$-polymatroid is like a matroid except that individual elements can have rank $2$ instead of just $0$ or $1$. A representable $2$-polymatroid arises from a collection of points and lines in a projective space. There are a number of natural questions for such $2$-polymatroids including whether an analogue of Rota's Conjecture holds for them. However, there few known tools for deriving structural results for $2$-polymatroids. This talk will introduce $2$-polymatroids and will present some results of joint work with Charles Semple and Geoff Whittle in which our goal was to obtain connectivity results for $2$-polymatroids that resemble Tutte's Wheels-and-Whirls Theorem and Seymour's Splitter Theorem.

Rudi Pendavingh, Counting matroids

Around 1970, Crapo and Rota conjectured that 'paving matroids will predominate in any asymptotic enumeration of matroids', Piff gave an upper bound on the number of matroids, Knuth described a machine for making a 'random' matroid, and Higgs pointed out how essential flats are a remarkably efficient way to describe a matroid.

We survey several techniques for counting matroids developed in recent years, based on entropy, algorithmic complexity, and various 'machines' for making short, faithful descriptions of a matroid. We show that most matroids are mostly paving, that with a slight twist to the argument Piff's bound can be improved significantly, and that Knuth's machine does not need that many random bits to make a matroid, because Higgs was right.

Alex Scott, Graphs of large chromatic number

Let $G$ be a graph with large chromatic number. What induced subgraphs must it contain? It may contain a large complete subgraph, but what can we say if this is not the case? We will survey recent work on this topic. In particular, we will discuss a recent sequence of papers with Paul Seymour; parts are also joint with Maria Chudnovsky and Sophie Spirkl.

Geoff Whittle, Quasi-graphic matroids

Members of certain classes of matroids exhibit clear graphic structure. Graphic matroids form the most obvious example, but so too do the generalisations to the classes of frame matroids and lifted-graphic matroids. These two classes have a common generalisation to the class of quasi-graphic matroids. In the talk I will introduce quasi-graphic matroids and discuss some of their interesting and perhaps surprising properties. My aspiration is that, for the uninitiated, the talk will also serve as an introduction to the topic of matroids associated with graphs. This is joint work with Jim Geelen and Bert Gerards.

Paul Wollan, A shorter proof for the graph minor structure theorem with explicit bounds

The graph minor structure theorem of Robertson and Seymour gives an approximate characterization of graphs excluding a fixed minor. It has had a profound impact on the field with numerous applications, both in graph theory and in theoretical computer science. In this talk, we discuss a new proof of the theorem which seeks to simplify and shorten what is a notoriously difficult proof. One advantage of the new proof is that it now allows the calculation of explicit bounds on the parameters involved. This is joint work with Ken Kawarabayashi and Robin Thomas.

Links

Go to the full schedule or index.