Multi-color Ramsey number for triangles grows faster than for other odd cycles
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
For graphs \( G_i\), \( i=1,\dots,k\), let \( r(G_1,\dots,G_k)\) denote the smallest integer \( m\) satisfying the property that if the edges of the complete graph \( K_m\) are colored in \( k\) colors, then for some \( i\), \( 1\leq i\leq k\), there is a subgraph isomorphic to \( G_i\) with all edges in the \( i\)-th color.
A multi-colored Ramsey problem for odd cycles (proposed by Erdös and Graham [1])
Show that for \(n \geq 2\) and any \(k\), \[ \lim_{k \rightarrow \infty} \frac{r(\overbrace{C_{2n+1},\ldots,C_{2n+1}}^k)} { r(\underbrace{3,\ldots,3}_k)} = 0 \]This problem is open even for \( n=2\).
Bibliography | |
---|---|
1 |
P. Erdös,
Some new problems and results in graph theory and
other branches of combinatorial mathematics, Combinatorics and
graph theory (Calcutta, 1980), Lecture Notes in Math., 885,
9-17, Springer, Berlin-New York, 1981.
|