Working Seminar on Formal Models, Discrete Structures, and Algorithms

On Induced Vertex Folkman Numbers

Reshma Ramadurai (Carnegie Mellon University)

When: October 10, 2pm

Where: room G2.91b


Let r be a natural number and G be a graph of order n. It is known that there exists a graph H such that the clique number of H is the same as that of G and every r-coloring of the vertices of H yields a monochromatic and induced subgraph isomorphic to G. The induced Folkman number, denoted by F(G,r), is the minimum order of a graph, H, satisfying the above properties.

This talk pertains to obtaining upper bounds for F(G,r). We are able to quantitatively extend previously known results about F(G,r), by conditioning on the clique number, \omega, of G; and show that using our proof technique, this bound is best possible up to a polylogarithmic factor.

I will also talk about some extensions and variations of the classical Folkman problem.