# Past Combinatorial Theory Seminar

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).

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.

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

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.

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).