Friends and stranger theorem: more than one group of three strangers or three friends?

193 Views Asked by At

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?

1

There are 1 best solutions below

0
On BEST ANSWER

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.