14
Apr
Title: A Polynomial Bound on Vertex Folkman Numbers
Speaker: Andrzej Dudek, Emory University
When: Tuesday April 15, 12:30-13:30
Where: Wean Hall 5304
Abstract:
In 1970, Folkman proved that for a given integer r and a graph G of order n there exists a graph H with the same clique number as G such that every r coloring of vertices of H yields at least one monochromatic copy of G. His proof gives no good bound on the order of graph H, i.e., the order of H is bounded by an iterated power function of n. In this talk we will give an alternative proof of Folkman’s theorem with the relatively small order of H bounded from above by O(n^3 log^3 n). This is joint work with Vojtech Rodl.
