An explicit construction for a Ramsey problem
Given graphs \(G\) and \(H\), an \((H, q)\)-coloring of \(G\) is a coloring of the edges of \(G\) such that every subgraph of \(G\) isomorphic to \(H\) receives at least \(q\) colors. The minimun munber of colors needed is \(r(G, H, q)\), for details see \textit{M. Axenovich, Z. Füredi} and \textit{D. Mubayi} [J. Comb. Theory, Ser. B 79, No. 1, 66--86 (2000; Zbl 1023.05101)]. For \(G=K_n\) and \(H=K_p\), \(f(n, p, q)\) is used instead of \(r(G, H, q)\). \textit{P. Erdős} and \textit{A. Gyárfás} [Combinatorica 17, No. 4, 459--467 (1997; Zbl 0910.05034)] investigated the growth rate of the function \(f\) when \(p\) is fixed. In particular, they showed that \(d \log n/\log \log n \leq f(n, 4, 2) \leq d' \log n\), and \(f(n, 4, 4) =O(n^{2/3})\) by a probabilistic argument. The main result of this paper gives an explicit (algebraic, with some modifications) coloring that proves \(f(n, 4, 4) < n^{1/2}e^{c \sqrt{\log n}}\). From Turán's celebrated theorem follows easily that \(\Omega(\sqrt{n})= f(n, 4, 4)\), and the author conjectures that indeed, \(f(n, 4, 4)= \Theta (\sqrt{n})\). The proof nicely blends some simple computation over finite fields with graph theoretic ideas.
- Weighted arcs, the finite Radon transform and a Ramsey problem
- A generalized Ramsey problem
- A simple and non-trivial Ramsey test
- An explicit edge-coloring of K_n with six colors on every K₅
- On colorful edge triples in edge-colored complete graphs
- Coloring triple systems with local conditions
- Ramsey classes: examples and constructions
- When is an Almost MonochromaticK4Guaranteed?
- Colorings generated by monotone properties
- A (5,5)-Colouring of Kn with Few Colours
- Color isomorphic even cycles and a related Ramsey problem
- Explicit Construction of RIP Matrices Is Ramsey‐Hard
- Ramsey-type problem for an almost monochromatic \(K_4\)
- Explicit constructions of triple systems for Ramsey–Turán problems
- New upper bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers
- Lower bounds on the Erdős–Gyárfás problem via color energy graphs
- New bounds on the generalized Ramsey number \(f(n, 5, 8)\)
- The Erdős-Gyárfás function \(f(n, 4, 5) = \frac{5}{6} n + o(n)\) -- so Gyárfás was right
- Ramsey theory constructions from hypergraph matchings
- Growth rates of the bipartite Erdős-Gyárfás function
- Generalized Ramsey numbers of cycles, paths, and hypergraphs
- A random coloring process gives improved bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers
- A construction for Ramsey numbers for \(K_{m,n}\)
- Edge-colorings avoiding rainbow and monochromatic subgraphs
This page was built for publication: An explicit construction for a Ramsey problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q705745)
