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

# Past Combinatorial Theory Seminar

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

We give a new proof of the Frankl-Rödl theorem on set systems with a forbidden intersection. Our method extends to codes with forbidden distances, where over large alphabets our bound is significantly better than that obtained by Frankl and Rödl. One consequence of our result is a Frankl-Rödl type theorem for permutations with a forbidden distance. Joint work with Peter Keevash.