A note on the size-Ramsey number of long subdivisions of graphs
Let T(s)H be the graph obtained from a given graph H by subdividing each edge s times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in Proc. of the 13th annual ACM-SIAM Symposium on Discrete Algorithms ( SODA 2002) 321-328], we prove that, for any graph H, there exist graphs G with O(s) edges that are Ramsey with respect to T(s)H.
the size-ramsey number ramsey theory expanders ramanujan graphs explicit constructions