Past Combinatorial Theory Seminar

21 October 2014
14:30
Richard Montgomery
Abstract
Given a tree $T$ with $n$ vertices, how large does $p$ need to be for it to be likely that a copy of $T$ appears in the binomial random graph $G(n,p)$? I will discuss this question, including recent work confirming a conjecture which gives a good answer to this question for trees with bounded maximum degree.
  • Combinatorial Theory Seminar
14 October 2014
14:30
Abstract

We study the properties of finite graphs in which the ball of radius $r$ around each vertex induces a graph isomorphic to some fixed graph $F$. (Such a graph is said to be $r$-locally-$F$.) This is a natural extension of the study of regular graphs, and of the study of graphs of constant link. We focus on the case where $F$ is $\mathbb{L}^d$, the $d$-dimensional integer lattice. We obtain a characterisation of all the finite graphs in which the ball of radius $3$ around each vertex is isomorphic to the ball of radius $3$ in $\mathbb{L}^d$, for each integer $d$. These graphs have a very rigidly proscribed global structure, much more so than that of $(2d)$-regular graphs. (They can be viewed as quotient lattices in certain 'flat orbifolds'.) Our results are best possible in the sense that '3' cannot be replaced with '2'. Our proofs use a mixture of techniques and results from combinatorics, algebraic topology and group theory. We will also discuss some results and open problems on the properties of a random n-vertex graph which is $r$-locally-$F$. This is all joint work with Itai Benjamini (Weizmann Institute of Science). 

  • Combinatorial Theory Seminar
17 June 2014
14:30
Louigi Addario-Berry
Abstract
<p>We use a growth procedure for binary trees due to Luczak and Winkler, a bijection between binary trees and irreducible quadrangulations of the hexagon due to Fusy, Poulalhon and Schaeffer, and the classical angular mapping between quadrangulations and maps, to define a growth procedure for maps. The growth procedure is local, in that every map is obtained from its predecessor by an operation that only modifies vertices lying on a common face with some fixed vertex. The sequence of maps has an almost sure limit G; we show that G is the distributional local limit of large, uniformly random 3-connected graphs. <br> A classical result of Brooks, Smith, Stone and Tutte associates squarings of rectangles to edge-rooted planar graphs. Our map growth procedure induces a growing sequence of squarings, which we show has an almost sure limit: an infinite squaring of a finite rectangle, which almost surely has a unique point of accumulation. We know almost nothing about the limit, but it should be in some way related to "Liouville quantum gravity". <br>Parts joint with Nicholas Leavitt. </p>
  • Combinatorial Theory Seminar
10 June 2014
14:30
Abstract

In the Erdös-Rényi random graph process, starting from an empty graph, in each step a new random edge is added to the evolving graph. One of its most interesting features is the `percolation phase transition': as the ratio of the number of edges to vertices increases past a certain critical density, the global structure changes radically, from only small components to a single giant component plus small ones.


In this talk we consider Achlioptas processes, which have become a key example for random graph processes with dependencies between the edges. Starting from an empty graph these proceed as follows: in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph. We discuss why, for a large class of rules, the percolation phase transition is qualitatively comparable to the classical Erdös-Rényi process.


Based on joint work with Oliver Riordan.

  • Combinatorial Theory Seminar
20 May 2014
14:30
Abstract
A system of linear equations is called partition regular if, whenever the naturals are finitely coloured, there is a monochromatic solution of the equations. Many of the classical theorems of Ramsey Theory may be phrased as assertions that certain systems are partition regular. What happens if we are colouring not the naturals but the (non-zero) integers, rationals, or reals instead? After some background, we will give various recent results.
  • Combinatorial Theory Seminar
6 May 2014
14:30
John Talbot
Abstract


Erdos, Faudree, Gould, Gyarfas, Rousseau and Schelp, conjectured that
whenever the edges of a complete graph are coloured using three colours
there always exists a set of at most three vertices which have at least
two-thirds of their neighbours in one of the colours.  We will describe a
proof of this conjecture. This is joint work with Rahil Baber

  • Combinatorial Theory Seminar
29 April 2014
14:30
David Conlon
Abstract
<p>Fix positive integers p and q with 2 \leq q \leq {p \choose 2}. An edge-colouring of the complete graph K_n is said to be a (p, q)-colouring if every K_p receives at least q different colours. The function f(n, p, q) is the minimum number of colours that are needed for K_n to have a (p,q)-colouring. This function was introduced by Erdos and Shelah about 40 years ago, but Erdos and Gyarfas were the first to study the function in a systematic way. They proved that f(n, p, p) is polynomial in n and asked to determine the maximum q, depending on p, for which f(n,p,q) is subpolynomial in n. We prove that the answer is p-1. <br /> <br />We also discuss some related questions. <br /> <br />Joint work with Jacob Fox, Choongbum Lee and Benny Sudakov. </p>
  • Combinatorial Theory Seminar
13 March 2014
16:00
Abstract
I will discuss a novel approach to estimating communication costs of an algorithm (also known as its I/O complexity), which is based on small-set expansion for computational graphs. Various applications and implications will be discussed as well, mostly having to do with linear algebra algorithms. This includes, in particular, first known (and tight) bounds on communication complexity of fast matrix multiplication. Joint work with Grey Ballard, James Demmel, Benjamin Lipshitz and Oded Schwartz.
  • Combinatorial Theory Seminar
25 February 2014
14:30
Alan Frieze
Abstract

We discuss some questions related to coloring the edge/vertices of randomgraphs. In particular we look at
(i) The game chromatic number;
(ii) Rainbow Matchings and Hamilton cycles;
(iii) Rainbow Connection;
(iv) Zebraic Colorings.

  • Combinatorial Theory Seminar
18 February 2014
14:30
Abstract

Several objects can be associated to a list of vectors with integer coordinates: among others, a family of tori called toric arrangement, a convex polytope called zonotope, a function called vector partition function; these objects have been described in a recent book by De Concini and Procesi. The linear algebra of the list of vectors is axiomatized by the combinatorial notion of a matroid; but several properties of the objects above depend also on the arithmetics of the list. This can be encoded by the notion of a "matroid over Z". Similarly, applications to tropical geometry suggest the introduction of matroids over a discrete valuation ring.Motivated by the examples above, we introduce the more general notion of a "matroid over a commutative ring R". Such a matroid arises for example from a list of elements in a R-module. When R is a Dedekind domain, we can extend the usual properties and operations holding for matroids (e.g., duality). We can also compute the Tutte-Grothendieck ring of matroids over R; the class of a matroid in such a ring specializes to several invariants, such as the Tutte polynomial and the Tutte quasipolynomial. We will also outline other possible applications and open problems. (Joint work with Alex Fink).

  • Combinatorial Theory Seminar

Pages