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