
doi: 10.1007/bf02579159
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.
Ramsey graphs, coloring of edges, Generalized Ramsey theory, induced copy, Hypergraphs
Ramsey graphs, coloring of edges, Generalized Ramsey theory, induced copy, Hypergraphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 11 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
