Sparse Ramsey graphs (Q795843): Difference between revisions

Let H be a graph which is the union of copies of a graph G. Associated with H (and the specified copies of G) is the hypergraph \({\mathcal H}\) whose vertices are the edges of H and whose hyperedges are the edge sets of these specified copies of G. The graph H t-arrows G \((H\to(G)_ t)\) if for any coloring of the edges of H with t colors, there is an induced copy of G in at least one of the colors. The following, which implies that there are very sparse Ramsey graphs for any graph G, is the main result. Theorem: For every pair of integers m, t and for any graph G there exists a graph H which is the union of copies of the graph G such that \(H\to(G)_ t\) and \({\mathcal H}\) does not contain any cycle of length less m. In the case when G is a complete graph, as well as for other special classes of graphs, the previous result is valid when the specified copies of G are all copies of G.