Combinatorial Theory Seminar

The induced graph removal lemma states that for any fixed graph $H$ on $h$ vertices and any $e\textgreater 0$ there exists $d\textgreater0$ such that any graph $G$ with at most $d n^h$ induced copies of $H$ may be made $H$-free by adding or removing atmost $e n^2$ edges. This fact was originally proven by Alon, Fischer, Krivelevich and Szegedy. In this talk, we discuss a new proof and itsrelation to various regularity lemmas. This is joint work with Jacob Fox.

It is known that generic and universal structures and Ramsey classes are related. We explain this connection and complement it by some new examples. Particularly we disscuss universal and Ramsey classes defined by existence and non-existence of homomorphisms.

The 2-dimensional assignment problem (minimum cost matching) is solvable in polynomial time, and it is known that a random instance of size n, with entries chosen independently and uniformly at random from [0,1], has expected cost tending to π^2/6.  In dimensions 3 and higher, the "planar" assignment problem is NP-complete, but what is the expected cost for a random instance, and how well can a heuristic do?  In d dimensions, the expected cost is of order at least n^{2-d} and at most ln n times larger, but the upper bound is non-constructive.  For 3 dimensions, we show a heuristic capable of producing a solution within a factor n^ε of the lower bound, for any constant ε, in time of order roughly n^{1/ε}.  In dimensions 4 and higher, the question is wide open: we don't know any reasonable average-case assignment heuristic.

We consider random walks on two classes of random graphs and explore the likely structure of the the set of unvisited vertices or vacant set. In both cases, the size of the vacant set $N(t)$ can be obtained explicitly as a function of $t$. Let $\Gamma(t)$ be the subgraph induced by the vacant set. We show that, for random graphs $G_{n,p}$ above the connectivity threshold, and for random regular graphs $G_r$, for constant $r\geq 3$, there is a phase transition in the sense of the well-known Erdos-Renyi phase transition. Thus for $t\leq (1-\epsilon)t^*$ we have a unique giant plus components of  size $O(\log n)$ and for $t\geq (1+\epsilon)t^*$ we have only components of  size $O(\log n)$.

In the case of $G_r$ we describe the likely degree sequence, size of the giant component and structure of the small ($O(\log n)$) size components.

A random planar graph $P_n$ is a graph drawn uniformly at random from the class of all (labelled) planar graphs on $n$ vertices. In this talk we show that with probability $1-o(1)$ the number of vertices of degree $k$ in $P_n$ is very close to a quantity $d_k n$ that we determine explicitly. Here $k=k(n) \le c \log n$. In the talk our main emphasis will be on the techniques for proving such results. (Joint work with Kosta Panagiotou.)

We highlight a technique for studying edge colourings of multigraphs, due to Tashkinov. This method is a sophisticated generalisation of the method of alternating paths, and builds upon earlier work by Kierstead and Goldberg. In particular we show how to apply it to a number of edge colouring problems, including the question of whether the class of multigraphs that attain equality in Vizing's classical bound can be characterised.

This talk represents joint work with Jessica McDonald.

In 1961 Hajos conjectured that if a graph contains no subdivsion of a clique of order t then its chromatic number is less than t. In 1981, Erdos and Fajtlowicz showed that the conjecture is almost always false. We show it is almost always true. This is joint work with Keevash, Mohar, and McDiarmid.

I shall describe some recent results about the asymptotic behaviour of matroids.

Specifically almost all matroids are simple and have probability at least 1/2 of being connected.

Also, various quantitative results about rank, number of bases and number and size of circuits of almost all matroids are given. There are many open problems and I shall not assume any previous knowledge of matroids. This is joint work, see below.

1 D. Mayhew, M. Newman, D. Welsh and G. Whittle,

On the asymptotic properties of connected matroids, European J. Combin. to appear

2 J. Oxley, C. Semple, L. Wasrshauer and D. Welsh,

On properties of almost all matroids, (2011) submitted