2
$\begingroup$

What research has been done on how many vertices of a complete graph are required to guarantee more than one complete monochromatic subgraph given a random red/blue edge coloring?

For example, how many vertices are required to guarantee two monochromatic triangles given a random red/blue edge coloring?

In terms of the friends and strangers theorem, how many people are required to guarantee at least two groups of three friends or strangers?

$\endgroup$
8
  • $\begingroup$ Is it important for the complete subgraphs to be the same monochromatic color? Is it important for them to be disjoint? $\endgroup$ Commented Jul 22, 2021 at 22:52
  • $\begingroup$ Good question! For simplicity’s sake, let’s say they are disjoint (but it might be interesting also to know when they are not) and need not be the same color. So there could be two groups of three friends, two groups of three strangers, or a group of three friends and a group of three strangers. $\endgroup$
    – B. Peet
    Commented Jul 22, 2021 at 23:00
  • 1
    $\begingroup$ This is covered in Ramsey theory. In fact, the complete graph on six vertices has at least two monochromatic triangles, but it could be one of each color. I have seen more interest in how many vertices it takes to guarantee a clique of some number of one color or some (perhaps different) number of the other color. $\endgroup$ Commented Jul 22, 2021 at 23:20
  • $\begingroup$ If you didn't require the two sens to be disjoint, the answer would be $6$: if the edges of $K_6$ are colored with two colors, there are at least two monochromatic triangles, not necessarily disjoint and not necessarily the same color. $\endgroup$
    – bof
    Commented Jul 22, 2021 at 23:21
  • 1
    $\begingroup$ See the answer to this old question for the number of (not necessarily disjoint) monochromatic triangles: math.stackexchange.com/questions/2216943/… $\endgroup$
    – bof
    Commented Jul 22, 2021 at 23:26

1 Answer 1

4
$\begingroup$

For $n \ge 2$ vertex-disjoint triangles, not necessarily of any particular color, $3n+2$ vertices are required.

To see that $3n+1$ vertices are not enough, take a red complete bipartite graph $K_{3n-1,2}$, and color all its missing edges blue. There are no red triangles, and all blue triangles are on the side with $3n-1$ vertices: so there can be at most $n-1$ vertex-disjoint blue triangles.

To see that $3n+2$ vertices are enough, we should first prove that any red-blue coloring of $K_8$ contains two vertex-disjoint monochromatic triangles. I can prove this, but only by some tedious casework, which follows later in this answer.

Anyway, from then on, we can induct on $n$ when $n>2$: find a monochromatic triangle in the coloring of $K_{3n+2}$, delete its vertices, and find $n-1$ more monochromatic triangles in the remaining coloring of $K_{3n-1} = K_{3(n-1)+2}$. This eventually reduces to the $K_8$ case.


Here's my current best attempt at proving that any red-blue coloring $K_8$ contains two disjoint monochromatic triangles.

Suppose not. Then if you remove any monochromatic triangle, what's left must be a coloring of $K_5$ with no monochromatic triangles, which is unique: it must contain a red $5$-cycle and a blue $5$-cycle. This does not lead to a contradiction immediately...

...but it does if we assume that the graph contains both a blue triangle and a red triangle. They are not disjoint, by assumption, so suppose they have vertices $\{a,b,c\}$ and $\{c,d,e\}$ respectively, with vertices $f,g,h$ left out. Then $K_8 - \{a,b,c\}$ contains a red edge $de$, which is part of a red cycle on $d,e,f,g,h$. At least two edges of that red cycle must be between $f,g,h$. Similarly, we prove that at least two edges of a blue cycle on $a,b,f,g,h$ must be between $f,g,h$, which is impossible.

So we have a coloring of $K_8$ that contains, by assumption, only one color of triangle: say, blue. Let $\{a,b,c\}$ form one blue triangle; since $K_8 - \{a,b\}$ still has $6$ vertices, there must be another blue triangle among them, using for example vertices $\{c,d,e\}$. We have already seen that the blue subgraphs of $K_8 - \{a,b,c\}$ and $K_8 - \{c,d,e\}$ must be $5$-cycles; by symmetry, say that these visit vertices $d,e,f,g,h$ and $a,b,f,g,h$ respectively in that order.

Then edges $af$ and $df$ are red, so edge $ad$ must be blue; similarly, edges $bh$ and $eh$ are red, so edge $be$ must be blue. This creates disjoint blue triangles on vertices $\{a,c,d\}$ and $\{b,e,f\}$.


Relatedly, Burr, Erdős and Spencer show that if you want to find vertex-disjoint triangles of a specific color, then:

  • to find $n$ disjoint triangles, all of one color, $5n$ vertices are required;
  • more generally, to find either $m$ red triangles or $n$ blue triangles, where $m \ge n \ge 1$ and $m \ge 2$, $3m+2n$ vertices are required.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .