Ramsey problems involving degrees in edge-colored complete graphs of vertices belonging to monochromatic subgraphs (Q1260770): Difference between revisions

This note concerns the degrees of vertices in the monochromatic subgraphs guaranteed by Ramseyian theorems. There are two theorems, using colorings \(g\) of edges into colors red and blue. Given a graph \(G\), let \(R\) be the graph of red edges and \(B\) the graph of blue edges. Let \(\deg_G(x)\) be the degree of the vertex \(x\) in \(G\). Given a regular graph \(G\) on vertices \(x\in X\), let \(\Delta_G=\max_{x\in X} \deg_G(x)- \min_{x\in X} \deg_G(x)\). If we color the edges of \(G\) red and blue, then \(\Delta_B=\Delta_R\), and we denote this common ``degree spread'' \(\Delta_\gamma\), where \(\gamma\) is the coloring. The first theorem is a formula for the minimal degree spread of vertices in the monochromatic subgraphs guaranteed by Ramsey's theorem. Given a graph \(G\) and a 2-coloring \(\gamma\) of its vertices, let \(\deg_R(x)\) be the degree of \(x\) in \(R\). The second theorem states that for any \(m\), if \(n=n(m)\) is sufficiently large, then any 2-coloring of the clique \(K_n\) admits a monochromatic bipartite \(K_{n,m}\) with two vertices \(x\) and \(y\) such that \(\deg_R(x)=\deg_R(y)\). This is also true of cycles \(C_m\).