FG1 Seminar talk

2007-10-05
Menachem Kojman
Induced Ramsey theory with symmetry

Abstract:
It will be shown that induced subgraph relations in which it is required that some of the automorphisms of the subgraph extend to automorphisms of the bigger graph are stable under vertex and edge colorings.
For example: for every finite graph H with n vertices there is a graph G with O(n^4) vertices such that for every vertex coloring of G by 2 colors there is an induced monochromatic copy of H so that every vertex of the copy can be moved to any other vertex of the copy by an automorphism of G.