The Down-Arrow Ramsey Set of a Graph

Proof. First, consider the red-blue coloring of $C_n$ for which the red and blue subgraphs are both $P_{\frac{n}{2}+1}$. Thus, if $G\in \downarrow C_n$, then $G\subseteq P_{\frac{n}{2}+1}$. Additionally, consider the red-blue coloring of the edges of $C_n$ such that both the red and blue subgraphs are $\frac{n}{2}$ disjoint copies of $K_2$. This implies that if $G\in \downarrow C_n$, then $G\subseteq (\frac{n}{2})K_2$. Therefore, if $G\in \downarrow C_n$, then these two requirements imply that in fact $G\subseteq \lceil \frac{n}{4}\rceil K_2$.

Now, we show that $\lceil \frac{n}{4}\rceil K_2\in \downarrow C_n$. Let there be any red-blue coloring of $C_n$. Then, there must be at least $\frac{n}{2}$ edges of the same color. Say there are $k\ge \frac{n}{2}$ blue edges. Then at least $\lceil \frac{k}{2}\rceil$ of these edges are independent, which implies that there are at least $\lceil \frac{k}{2}\rceil \ge \lceil \frac{n}{4}\rceil$ independent blue edges. Therefore, we have a monochromatic $\lceil \frac{n}{4}\rceil K_2$. 

Proof. Suppose there is a red-blue coloring of $C_3$ whose color classes are $G_r$ and $G_b$. Since $C_3$ has 3 edges, it follows that some color class has at least two edges. Without loss of generality, assume that $G_r$ has two edges. Then we have two adjacent red edges, hence a red $P_3$. This shows $⟨P_3⟩\subseteq \downarrow C_3$. For the reverse inclusion, let $G\in \downarrow K_3$. The red-blue coloring of $C_3$ with $P_3$ as the red subgraph and $K_2$ as the blue subgraph shows that either $G\subseteq P_3$ or $G\subseteq K_2$. Hence, $G\subseteq ⟨P_3⟩$. 

Proof. It follows from a similar argument from above that $⟨\lceil \frac{n}{4}\rceil K_2⟩\in \downarrow C_n$ for odd $n$ as well.

To show that $P_3\cup \lfloor \frac{n-3}{4}\rfloor K_2$ must be in $\downarrow C_n$, we consider two cases, depending on the order of $C_n$ modulo 4.

Case 1: Suppose $n=4k+1$, for $k\ge 1$. Note that $\lfloor \frac{n-3}{4}\rfloor =k-1$ in this case, so we are aiming to show that $P_3\cup (k-1)K_2\in \downarrow C_n$. Let there be a red-blue coloring of $C_n$. We know that there are at least $\lceil \frac{n}{2}\rceil =2k+1$ edges of one color. Without loss of generality, say there are at least $2k+1$ blue edges. Of these blue edges, at least $k+1$ of them are independent. Let $S=\{e_1,e_2,\dots e_k,e_{k+1}\}$ be a set of $k+1$ independent blue edges.

Since the independence number of $C_n$ is $\lfloor \frac{n}{2}\rfloor =2k$, then we know there are at most $2k$ independent blue edges. Hence, there are at least two blue edges that are adjacent to each other. Label these edges as $a$ and $b$, and label the other edges adjacent to $a$ and $b$ to be $c$ and $d$ respectively. Notice that at most two of the four edges $a$, $b$, $c$, $d$ are in the set $S$ of independent blue edges. Thus, if $k>1$, then there are still at least $k-1$ independent blue edges that are not $a$, $b$, $c$, or $d$. Therefore these independent edges together with $a$ and $b$ form a blue $P_3\cup (k-1)K_2$. If $k=1$, then we have formed a blue $P_3$ with edges $a$ and $b$, which follows the statement of the lemma.

Case 2: Suppose $n=4k+3$, for $k\ge 1$. Here we have $\lfloor \frac{n-3}{4}\rfloor =k$ in this case, so we need to show that $P_3\cup k{K}_2\in \downarrow C_n$. Let there be a red-blue coloring of $C_n$. We must have at least $\lceil \frac{n}{2}\rceil =2k+2$ edges of one color, say blue. Of these blue edges, we have that at least $k+1$ of them are independent and at most $\lfloor \frac{n}{2}\rfloor =2k+1$ of them are independent.

Notice that if there are at least $k+2$ independent blue edges, then we could use the same argument in the previous case to show that there must be a blue $P_3\cup k{K}_2$. Assume that there are exactly $k+1$ independent blue edges, and let $S=\{e_1,e_2,\dots ,e_k,e_{k+1}\}$ be the set of all independent blue edges. Since there are at least $2k+2$ blue edges, this means that there are at least $k+1$ blue edges that are adjacent to one or more blue edges in $S$. It follows that there must be at least one blue edge that is adjacent to exactly one edge in $S$. Call this edge $f$, and suppose it is adjacent to $e_j$, $1\le j\le k+1$. Thus, the set of edges $S-e_j$ forms a blue $k{K}_2$ and $f$ and $e_j$ together form a blue $P_3$. Therefore, we have a blue $P_3\cup k{K}_2$. 

Proof. Let $G_1=\left(\frac{n-3}{2}\right)K_2\cup P_3$ and $G_2=P_{\frac{n-1}{2}}\cup P_3$. It is clear that the reverse inclusion holds. For the forward inclusion, let $H\in ⟨G_1⟩\cap ⟨G_2⟩$ and notice that the edge independence number of $G_2$ is $\lfloor \frac{n-1}{4}\rfloor +1=\lfloor \frac{n+3}{4}\rfloor$. Hence, the edge independence number of $H$ is at most $\lfloor \frac{n+3}{4}\rfloor$. Since $H$ is also a subgraph of $G_1$ it follows that $H$ is a subgraph of $\lfloor \frac{n+3}{4}\rfloor K_2$ or a subgraph of $\lfloor \frac{n-1}{4}\rfloor K_2\cup P_3$. Since $\lfloor \frac{n+3}{4}\rfloor K_2$ is a subgraph of the latter graph, the result holds. 

Proof. Let $G_1=P_{\frac{n+3}{2}}$ and $G_2=\lfloor \frac{n-1}{4}\rfloor K_2\cup P_3$. It is clear that the reverse inclusion holds. For the forward inclusion, we consider two cases depending on whether $n\equiv 1(\mathrm{mod}4)$ or $n\equiv 3(\mathrm{mod}4)$.

Case 1: Suppose $n=4k+1$, for $k\ge 1$. In this case $G_1=P_{2k+2}$ and $G_2=k{K}_2\cup P_3$. Notice that deleting any edge of $G_2$ yields either $(k+1)K_2$ or $(k-1)K_2\cup P_3$ and that each of these is a subgraph of $P_{2k+2}$, while $G_2$ itself is not. Finally, notice that $k-1=\frac{n-5}{4}=\lfloor \frac{n-3}{4}\rfloor$ and $k+1=\lfloor \frac{n+3}{4}\rfloor$ when $n=4k+1$.

Case 2: Suppose $n=4k+3$, for $k\ge 1$. In this case $G_1=P_{2k+3}$ and $G_2=k{K}_2\cup P_3$. Hence, $G_2\subseteq G_1$ and so $⟨G_2⟩\cap ⟨G_1⟩=⟨G_2⟩$. However, $\lfloor \frac{n+3}{4}\rfloor K_2=(k+1)K_2$ and $\lfloor \frac{n-3}{4}\rfloor K_2\cup P_3=k{K}_2\cup P_3$. Since $(k+1)K_2\subseteq k{K}_2\cup P_3=G_2$, the result holds here as well. 

Proof. Due to Lemma 1, it suffices to show that $\downarrow C_n\subseteq ⟨P_3\cup \lfloor \frac{n-3}{4}\rfloor K_2⟩\cup ⟨\lceil \frac{n}{4}\rceil K_2⟩$.

Consider the following three red-blue colorings of $C_n$:

• ${\mathcal{C}}_1$: $G_{r_1}\cong P_{\frac{n+1}{2}}$,$G_{b_1}\cong P_{\frac{n+3}{2}}$

• ${\mathcal{C}}_2$: $G_{r_2}\cong \left(\frac{n-1}{2}\right)K_2$,$G_{b_2}\cong \left(\frac{n-3}{2}\right)K_2\cup P_3$

• ${\mathcal{C}}_3$: $G_{r_3}\cong P_{\frac{n-3}{2}}\cup P_3$,$G_{b_3}\cong P_{\frac{n-1}{2}}\cup P_3$

Notice first that $G_{r_1}\subseteq G_{b_1}$, $G_{r_2}\subseteq G_{b_2}$, and $G_{r_3}\subseteq G_{b_3}.$ Hence, for odd $n$, $$\begin{array}{rl}\downarrow C_n\subseteq {\mathcal{C}}_1\cap {\mathcal{C}}_2\cap {\mathcal{C}}_3& =⟨G_{b_1}⟩\cap ⟨G_{b_2}⟩\cap ⟨G_{b_3}⟩\\ & =⟨P_{\frac{n+3}{2}}⟩\cap (⟨\left(\frac{n-3}{2}\right)K_2\cup P_3⟩\cap ⟨P_{\frac{n-1}{2}}\cup P_3⟩)\\ & =⟨P_{\frac{n+3}{2}}⟩\cap ⟨\lfloor {\displaystyle \frac{n-1}{4}}\rfloor K_2\cup P_3⟩\\ & =⟨\lfloor {\displaystyle \frac{n+3}{4}}\rfloor K_2⟩\cup ⟨\lfloor {\displaystyle \frac{n-3}{4}}\rfloor K_2\cup P_3⟩\end{array}$$

Finally, notice that when $n$ is odd, $\lfloor \frac{n+3}{4}\rfloor =\lceil \frac{n}{4}\rceil$. 

Proof. We can see that $⟨\lceil \frac{n-1}{4}\rceil K_2⟩\subseteq \downarrow P_n$. Now, let $G$ be a graph in the down-arrow Ramsey set of $P_n$. We will use two red-blue colorings of $P_n$ to show $G\subseteq \lceil \frac{n-1}{4}\rceil K_2$.

For ease of notation, let $k=\lfloor \frac{n-1}{2}\rfloor$ and $k^{\prime }=\lceil \frac{n-1}{2}\rceil$. Consider the red-blue coloring of the edges of $P_n$ for which the red subgraph is $P_{k^{\prime }+1}$ and the blue subgraph is $P_{k+1}$. This implies that $G\subseteq P_{k+1}$. Additionally, consider the red-blue coloring of the edges of $P_n$ for which the red subgraph is $(k^{\prime })K_2$ and the blue subgraph is $k{K}_2$. This coloring suggests that we also have $G\subseteq k{K}_2$. Hence,

Therefore we have $\downarrow P_n=⟨\lceil \frac{n-1}{4}\rceil K_2⟩$. 

Proof. By Proposition 3 it follows that $⟨P_3⟩\subseteq \downarrow K_4$. To see the reverse inclusion, consider the following two red-blue colorings of the edges of $K_4$.

1. $G_{r_1}\cong G_{b_1}\cong P_4$

2. $G_{r_2}\cong K_3$, $G_{b_2}\cong K_{1,3}$

So, $$\begin{array}{rl}\downarrow K_4& \subseteq (⟨K_3⟩\cup ⟨K_{1,3}⟩)\cap ⟨P_4⟩\\ & =(⟨K_3⟩\cap ⟨P_4⟩)\cup (⟨K_{1,3}⟩\cap ⟨⟨P_4⟩)\\ & =⟨P_3⟩\cup ⟨P_3⟩\\ & =⟨P_3⟩\end{array}$$ Thus, $\downarrow K_4=⟨P_3⟩$, as desired. 

Proof. We first show that $P_4\in \downarrow K_5$. Assume to the contrary that there is a red-blue coloring of $K_5$ that avoids a monochromatic $P_4$. Label the vertices of $K_5$ by $v_1,v_2,v_3,v_4,$ and $v_5$. By Proposition 5, we are guaranteed a monochromatic $P_3$. So, we may assume that $v_1{v}_2$ and $v_2{v}_3$ are red edges. If any of the edges $v_1{v}_4$,$v_1{v}_5$, $v_3{v}_5$, or $v_4{v}_5$ are red, then we have a red $P_4$. Hence, each of these edges is blue. However, then $(v_4,v_1,v_5,v_3)$ is a blue $P_4$. So, we have that $P_4\in \downarrow K_5$ and hence $⟨P_4⟩\subseteq \downarrow K_5$.

To see the reverse inclusion, consider the following red-blue colorings of the edges of $K_5$:

1. $G_{r_1}\cong G_{b_1}\cong C_5$

2. $G_{r_2}\cong K_4$, $G_{b_2}\cong K_{1,4}$

So, $$\begin{array}{rl}\downarrow K_5\subseteq ⟨C_5⟩\cap (⟨K_4⟩\cup ⟨K_{1,4}⟩)& =(⟨C_5⟩\cap ⟨K_4⟩)\cup (⟨C_5⟩\cap ⟨K_{1,4}⟩)\\ & =⟨P_4⟩\cup ⟨P_3⟩\\ & =⟨P_4⟩\end{array}$$ Thus, $\downarrow K_5=⟨P_4⟩$, as desired. 

Proof. Clearly, $K_3\in \downarrow K_6$ since the Ramsey number $R(K_3,K_3)=6$. To see that $K_{2,3}-e\in \downarrow K_6$, first note that $C_4\in \downarrow K_6$ since $R(C_4,C_4)=6$ [7].

Now, suppose that there is a red-blue coloring $\mathcal{C}$ of $K_6$ that avoids a monochromatic $H=K_{2,3}-e$. We know that there must be a monochromatic $C_4$, so let $(v_1,v_2,v_3,v_4,v_1)$ be a red $C_4$. All edges between $\{v_1,v_2,v_3,v_4\}$ and $\{v_5,v_6\}$ must be blue, else there would be a red $H$. However, now the blue subgraph is isomorphic to $K_{2,4}$, which contains $H$. Thus, $H=K_{2,3}-e\in \downarrow K_6$. 

Proof. Due to Lemma 4, we need only show that $\downarrow K_6\subseteq ⟨K_{2,3}-e⟩\cup ⟨K_3⟩$. So, consider the following four red-blue colorings of the edges of $K_6$:

1. $G_{r_1}\cong K_{2,4}+uv$, $G_{b_1}\cong K_4$

2. $G_{r_2}\cong K_{1,5}$, $G_{b_2}\cong K_5$

3. $G_{r_3}\cong K_{3,3}$, $G_{b_3}\cong K_3\cup K_3$

4. See Figure 2

We will show that the intersection of these four colorings is $⟨K_{2,3}-e⟩\cup ⟨K_3⟩$. First, using Example 1, we take the intersection of ${\mathcal{C}}_1$ and ${\mathcal{C}}_2$ to obtain the following. $$(⟨K_{2,4}+uv⟩\cup ⟨K_4⟩)\cap (⟨K_{1,5}⟩\cup ⟨K_5⟩)=⟨K_{2,3}+uv⟩\cup ⟨K_{1,5}⟩\cup ⟨K_4⟩$$

Next, we take the intersection of $(1)$ and ${\mathcal{C}}_3$ and use Observation 2 to reduce. $$(⟨K_{2,3}+uv⟩\cup ⟨K_{1,5}⟩\cup ⟨K_4⟩)\cap (⟨K_{3,3}⟩\cup ⟨K_3\cup K_3⟩)=⟨K_{2,3}⟩\cup ⟨K_3⟩$$ Finally, we find the intersection of $(2)$ and ${\mathcal{C}}_4$ using Example 1 and Observation 4. Notice here that $f_5\cong G_{r_4}$ and that $G_{b_4}\subseteq G_{r_4}$. $$\begin{array}{rl}(⟨K_{2,3}⟩\cup ⟨K_3⟩)\cap (⟨G_{r_4}⟩\cup ⟨G_{b_4}⟩)& =(⟨K_{2,3}⟩\cup ⟨K_3⟩)\cap ⟨G_{r_4}⟩\\ & =⟨K_{2,3}-e⟩\cup ⟨K_3⟩\end{array}$$

Hence, $\downarrow K_6\subseteq ⟨K_{2,3}-e⟩\cup ⟨K_3⟩$ 

Proof. Assume to the contrary that there exists a red-blue coloring $\mathcal{C}$ of $K_7$ that avoids a monochromatic $G_1$. Since it is impossible to have a 3-regular graph of order 7, we know there must be a monochromatic $K_{1,4}$. Say there is a red subgraph isomorphic to $K_{1,4}$ in the coloring $\mathcal{C}$. Let the vertices of this subgraph be labeled $v_1,v_2,v_3,v_6,v_7$ as shown in Figure 3. Consider another vertex, $v_5$. Notice that $v_5$ can be adjacent to at most one of the vertices $v_2,v_3,v_6,v_7$ with a red edge, else a red $G_1$ will be formed. Thus, $v_5$ must be connected to at least three of $v_2,v_3,v_6,v_7$ with blue edges. Without loss of generality, assume edges $v_5{v}_2,v_5{v}_6,v_5{v}_7$ are blue. By the same argument, we know that $v_4$ must also be adjacent to at least three of $v_2,v_3,v_6,v_7$ with blue edges as well. We consider two cases.

Case 1. The edges $v_4{v}_2,v_4{v}_6,v_4{v}_7$ are blue. There is a blue $C_4$ formed, $(v_4,v_6,v_5,v_7,v_4)$. Since the edges $v_2{v}_4$ and $v_2{v}_5$ are also blue, then the following edges must be red to avoid a blue $G_1$: $v_1{v}_5$, $v_3{v}_5$, $v_1{v}_4$, $v_1{v}_5$. However, this produces a red $G_1$.

Case 2: The edges $v_4{v}_2,v_4{v}_3,v_4{v}_6$ are blue. Again, we have formed a blue $C_4$, $(v_2,v_4,v_6,v_5,v_2)$. Since the edges $v_5{v}_7$ and $v_3{v}_4$ are also blue, then the following edges need to be red: $v_1{v}_4$, $v_4{v}_7$, $v_1{v}_5$, $v_3{v}_5$.

Notice that if either are red, then the edges $v_4{v}_5$ and $v_3{v}_7$ would form a red $G_1$. Thus, they must both be blue. However, if they are both blue, then there will be a blue $G_1$.

Thus, no red-blue coloring of the edges of $K_7$ that avoids a monochromatic $G_1$ exists. 

Proof. Assume to the contrary that there exists a red-blue coloring $\mathcal{C}$ of the edges of $K_7$ that avoids a monochromatic $G_2$. Since the Ramsey number $R(K_3,K_3)=6$, we know that there must be a monochromatic triangle in $\mathcal{C}$. Assume without loss of generality that there is a red triangle, with vertices $v_1$, $v_2$, and $v_3$. Since $\mathcal{C}$ avoids a red $G_2$, then all edges between $\{v_1,v_2,v_3\}$ and $\{v_4,v_5,v_6,v_7\}$ must be blue. Furthermore, all edges between the vertices in $\{v_4,v_5,v_6,v_7\}$ will be red, else there will be a blue $G_2$. However, this then forms a red $K_4$, which clearly has a red $G_2$ as a subgraph. Hence, all red-blue colorings of the edges of $K_7$ must have a monochromatic $G_2$. 

Proof. Again, let’s assume that there exists a red-blue coloring $\mathcal{C}$ of the edges of $K_7$ that avoids a monochromatic $K_3\cup K_2$. Since there must be a monochromatic triangle, let’s assume that it is red and it has vertices labeled $v_1$, $v_2$, and $v_3$. This time, all edges between the vertices in the set $\{v_4,v_5,v_6,v_7\}$ must be blue to avoid a red $K_3\cup K_2$. This creates several blue triangles, one of which is formed between $v_4$, $v_5$, and $v_6$. Thus, the edges $v_1{v}_7$, $v_2{v}_7$, and $v_3{v}_7$ must be red. Similarly, $v_5$, $v_6$, and $v_7$ form a blue triangle, so the edges $v_1{v}_4$, $v_2{v}_4$, and $v_3{v}_4$ must also be red. However, this forces a red $K_3\cup K_2$. 

Proof. Consider the following five colorings of $K_7$:

1. $G_{r_1}\cong K_{2,5}+uv$, $G_{b_1}\cong K_5$

2. $G_{r_2}\cong K_{1,6}$, $G_{b_2}\cong K_6$

3. $G_{r_3}\cong K_3\cup K_4$, $G_{b_3}\cong K_{3,4}$

4. See Figure 8.

5. $G_{r_5}\cong K_{3,3}$, $G_{b_5}\cong \overline{K_{3,3}}$

We now determine the intersection of these colorings by following Example 1 and Observation 2. First, we compute the intersection of colorings ${\mathcal{C}}_1$ and ${\mathcal{C}}_2$. $$\begin{array}{}\text{(1)}& {\mathcal{C}}_1\cap {\mathcal{C}}_2=⟨K_{1,6}⟩\cup ⟨K_5⟩\cup ⟨K_{2,4}+uv⟩\end{array}$$ We now find the intersection of $(1)$ and ${\mathcal{C}}_3$. The relevant intersections are computed below.

1. $⟨K_{2,4}+uv⟩\cap ⟨K_3\cup K_4⟩=⟨K_4-e⟩\cup ⟨K_2\cup K_{1,3}⟩$

2. $⟨K_{2,4}+uv⟩\cap ⟨K_{3,4}⟩=⟨G_2⟩\cup ⟨K_{2,4}⟩$

3. $⟨K_{1,6}⟩\cap ⟨K_3\cup K_4⟩=⟨K_{1,3}⟩$

4. $⟨K_{1,6}⟩\cap ⟨K_{3,4}⟩=⟨K_{1,4}⟩$

5. $⟨K_5⟩\cap ⟨K_3\cup K_4⟩=⟨K_4⟩\cup ⟨K_3\cup K_2⟩$

Hence, we have the following intersection. $$\begin{array}{}\text{(2)}& (⟨K_{1,6}⟩\cup ⟨K_5⟩\cup ⟨K_{2,4}+uv⟩)\cap {\mathcal{C}}_3=⟨K_4⟩\cup ⟨K_3\cup K_2⟩\cup ⟨G_2⟩\cup ⟨K_{2,4}⟩\end{array}$$ Now we take (2) and intersect with ${\mathcal{C}}_4$ after noting the following intersections.

1. $(⟨K_3\cup K_2⟩\cup ⟨G_2⟩)\cap (⟨G_{r_4}⟩\cup ⟨G_{b_4}⟩)=⟨K_3\cup K_2⟩\cup ⟨G_2⟩$

2. $⟨K_4⟩\cap (⟨G_{r_4}⟩\cup ⟨G_{b_4}⟩)=⟨C_4⟩\cup ⟨G_2⟩$

3. $⟨K_{2,4}⟩\cap (⟨G_{r_4}⟩\cup ⟨G_{b_4}⟩)=⟨G_1⟩\cup ⟨G_3⟩$

The intersection follows. $$\begin{array}{}\text{(3)}& (⟨K_4⟩\cup ⟨K_3\cup K_2⟩\cup ⟨G_2⟩\cup ⟨K_{2,4}⟩)\cap {\mathcal{C}}_4=⟨G_1⟩\cup ⟨G_3⟩\cup ⟨K_3\cup K_2⟩\cup ⟨G_2⟩\end{array}$$ Finally, we take the intersection of (3) and ${\mathcal{C}}_5$.