Past Combinatorial Theory Seminar

16 January 2018
14:30
Katherine Staden
Abstract

A famous theorem of Mantel from 1907 states that every n-vertex graph with more than n^2/4 edges contains at least one triangle. In the 50s, Erdős asked for a quantitative version of this statement: for every n and e, how many triangles must an n-vertex e-edge graph contain?

This question has received a great deal of attention, and a long series of partial results culminated in an asymptotic solution by Razborov, extended to larger cliques by Nikiforov and Reiher. Currently, an exact solution is only known for a small range of edge densities, due to Lovász and Simonovits. In this talk, I will discuss the history of the problem and recent work which gives an exact solution for almost the entire range of edge densities. This is joint work with Hong Liu and Oleg Pikhurko.

  • Combinatorial Theory Seminar
27 November 2017
14:30
Mathias Schacht
Abstract

The interplay of minimum degree and 'structural properties' of large graphs with a given forbidden subgraph is a central topic in extremal graph theory. For a given graph $F$ we define the homomorphism threshold as the infimum $\alpha$ such that every $n$-vertex $F$-free graph $G$ with minimum degree $>\alpha n$ has a homomorphic image $H$ of bounded size (independent of $n$), which is $F$-free as well. Without the restriction of $H$ being $F$-free we recover the definition of the chromatic threshold, which was determined for every graph $F$ by Allen et al. The homomorphism threshold is less understood and we present recent joint work with O. Ebsen on the homomorphism threshold for odd cycles.

  • Combinatorial Theory Seminar
21 November 2017
16:00
Sophia Saller
Abstract

Understanding the distribution of subgraph counts has long been a central question in the study of random graphs. In this talk, we consider the distribution of Sn, the number of K4 subgraphs, in the Erdös Rényi random graph G(n, p). When the edge probability p \in (0, 1) is constant, a classical central limit theorem for Sn states that (Sn−µn)/σn converges in distribution. We establish a stronger form of convergence, namely the corresponding local limit theorem, which is joint work with O. Riordan.
 

  • Combinatorial Theory Seminar
21 November 2017
14:30
Zdenek Dvorak
Abstract

A class C of graphs has polynomial expansion if there exists a polynomial p such that for every graph G from C and for every integer r, each minor of G obtained by contracting disjoint subgraphs of radius at most r is p(r)-degenerate. Classes with polynomial expansion exhibit interesting structural, combinatorial, and algorithmic properties. In the talk, I will survey these properties and propose further research directions.

  • Combinatorial Theory Seminar
14 November 2017
14:30
Abstract

The edge isoperimetric problem for a graph G is to find, for each n, the minimum number of edges leaving any set of n vertices.  Exact solutions are known only in very special cases, for example when G is the usual cubic lattice on Z^d, with edges between pairs of vertices at l_1 distance 1.  The most attractive open problem was to answer this question for the "strong lattice" on Z^d, with edges between pairs of vertices at l_infty distance 1.  Whilst studying this question we in fact solved the edge isoperimetric problem asymptotically for every Cayley graph on Z^d.  I'll talk about how to go from the specification of a lattice to a corresponding near-optimal shape, for both this and the related vertex isoperimetric problem, and sketch the key ideas of the proof. Joint work with Joshua Erde.

  • Combinatorial Theory Seminar
7 November 2017
14:30
Abstract

Reed conjectured in 1998 that the chromatic number of a graph should be at most the average of the clique number (a trivial lower bound) and maximum degree plus one (a trivial upper bound); in support of this conjecture, Reed proved that the chromatic number is at most some nontrivial convex combination of these two quantities.  King and Reed later showed that a fraction of roughly 1/130000 away from the upper bound holds. Motivated by a paper by Bruhn and Joos, last year Bonamy, Perrett, and I proved that for large enough maximum degree, a fraction of 1/26 away from the upper bound holds. Then using new techniques, Delcourt and I showed that the list-coloring version holds; moreover, we improved the fraction for ordinary coloring to 1/13. Most recently, Kelly and I proved that a 'local' list version holds with a fraction of 1/52 wherein the degrees, list sizes, and clique sizes of vertices are allowed to vary.
 

  • Combinatorial Theory Seminar
30 October 2017
14:30
Liana Yepremyan
Abstract

Aharoni and Berger conjectured that in any bipartite multigraph that is properly edge-coloured by n colours with at least n+1 edges of each colour there must be a matching that uses each colour exactly once (such a matching is called rainbow). This conjecture recently have been proved asymptotically by Pokrovskiy. In this talk, I will consider the same question without the bipartiteness assumption. It turns out that in any multigraph with bounded edge multiplicities, that is properly edge-coloured by n colours with at least n+o(n) edges of each colour, there must be a matching of size n-O(1) that uses each colour at most once. This is joint work with Peter Keevash.

  • Combinatorial Theory Seminar
24 October 2017
14:30
Nina Kamcev
Abstract

A subset S of initially infected vertices of a graph G is called forcing if we can infect the entire graph by iteratively applying the following process. At each step, any infected vertex which has a unique uninfected neighbour, infects this neighbour. The forcing number of G is the minimum cardinality of a forcing set in G. It was introduced independently as a bound for the minimum rank of a graph, and as a tool in quantum information theory.

The focus of this talk is on the forcing number of the random graph. Furthermore, we will state our bounds on the forcing number of pseudorandom graphs and related problems. The results are joint work with Thomas Kalinowski and Benny Sudakov.

  • Combinatorial Theory Seminar
17 October 2017
14:30
Michelle Delcourt
Abstract

Enumerating families of combinatorial objects with given properties and describing the typical structure of these objects are fundamental problems in extremal combinatorics. In this talk, we will investigate intersecting families of discrete structures in various settings, determining their typical structure as the size of the underlying ground set tends to infinity. Our new approach outlines a general framework for a number of similar problems; in particular, we prove analogous results for hypergraphs, permutations, and vector spaces using the same technique. This is joint work with József Balogh, Shagnik Das, Hong Liu, and Maryam Sharifzadeh.

  • Combinatorial Theory Seminar
10 October 2017
14:30
Oliver Riordan
Abstract

Given a graph $G$, we can form a hypergraph $H$ whose edges correspond to the triangles in $G$. If $G$ is the standard Erdős-Rényi random graph with independent edges, then $H$ is random, but its edges are not independent, because of overlapping triangles. This is (presumably!) a major complication when proving results about triangles in random graphs.  However, it turns out that, for many purposes, we can treat the triangles as independent, in a one-sided sense (and losing something in the density): we can find an independent random hypergraph within the set of triangles. I will present two proofs, one of which generalizes to larger complete (and some non-complete) subgraphs.

  • Combinatorial Theory Seminar

Pages