MIT Combinatorics Seminar

Ramsey And Anti-Ramsey Theorems

Clifford Smyth, (Massachusetts Institute of Technology)

Wednesday, November 30, 2005   4:30 pm    Room 2-142


A coloring of the constituents of a combinatorial structure is k-finite (k-bounded) if it uses only k colors (uses each color only k times). A combinatorial structure is homogeneously (heterogeneously) colored if every constituent is colored the same (differently). A Ramsey-type theorem asserts that every k-finite coloring of a certain structure induces a homogeneous substructure of a certain size. An anti-Ramsey type theorem asserts that that every k-bounded coloring of a certain structure induces a heterogeneous substructure of a certain size. Clearly k-finiteness or something like it is necessary for the Ramsey theorems, otherwise the structure may be colored heterogeneously. Similarly k-boundedness is necessary for the anti-Ramsey type theorems.

We'll talk a little about anti-Ramsey theorems in general and thresholds for anti-Ramsey properties in random graphs.