Team construction in tri-partite graph

Question

The government wants to create a team with one alchemist, one builder, and one computer-scientist.

In order to have good cooperation, it is important that the 3 team-members like each other.

Therefore, the government gathers $k$ candidates of each profession, and creates their "liking" graph. This is a tri-partite graph, where there is an edge between $a$ and $b$ iff $a$ likes $b$.

(Note that the "like" relation is symmetric but not transitive, i.e.: if $a$ likes $b$ then $b$ likes $a$, but if $a$ likes $b$ and $b$ likes $c$, then not necessarily $a$ likes $c$).

Is this always possible to create a team? Of course not. For example, it is possible that no alchemist likes any builder.

However, suppose the "liking" graph has the following property: in each group of 3 alchemists and 3 builders, there is at least a single alchemist-builder pair that like each other; ditto for alchemists-computerists and builders-computerists.

Given this property, is this always possible to create a team where all 3 members like each other? If so, what is the minimum number of candidates of each type ($k$) that the government will have to gather?

I would like to both find k and prove that it is the minimum.

A possibly related sub-question is: in a group of $k$ alchemists and $k$ builders, what is the minimum number of pairs that like each other? For $k=3$, by the assumption of the question, that number is 1. What about $k>3$?

A third question is: what is the name of this kind of problems?

Answer 1

The summary so far (as CW).

Yuval Filmus rephrased the question in more conventional terms, as

What is the minimal $k$ such that for every red/blue-coloring of the edges of $K_{k,k,k}$ (the complete 3-partite graph with $k$ vertices in each partition) there is either a red triangle or a blue $K_{3,3}$?

Erel proved that the lower bound on $k$ is at least 5, and then using a SAT formulation that $k \ge 8$.

frafl showed that the upper bound on $k$ is at most 15. Aravind sketched a nice argument for a better upper bound.

Here is a more detailed form of Aravind's argument.

If a vertex $u$ in partition $A$ is red-connected to 3 vertices $S$ in partition $B$ and 3 vertices $T$ in partition $C$, then there is either a red triangle involving $u$ and one vertex from each of $S$ and $T$, or otherwise $S\cup T$ induces a blue $K_{3,3}$. So no vertex can have more than 2 red-connected neighbours in both of its neighbour partitions.

Hence every vertex has at least $k-2$ blue-connected neighbours in at least one of its neighbour partitions. Let $S$ be the vertices in $A$ which have at least $k-2$ blue-connected neighbours in $B$, and $T$ be those vertices in $A$ which have at least $k-2$ blue-connected neighbours in $C$; note that $A = S\cup T$. If $S\cap T$ is non-empty, then switching colours yields a contradiction since $k\ge 5$. So assume $S$ and $T$ are disjoint. In fact, each vertex in $S$ must be blue-connected to at most 2 vertices in $C$ (so red-connected to at least $k-2$ vertices in $C$), and each vertex in $T$ must be blue-connected to at most 2 vertices in $B$ (and red-connected to at least $k-2$ vertices in $C$).

Now $k \ge 6$ so without loss of generality suppose that $S$ contains a subset $S'$ with at least 3 vertices. They are each blue-connected to at least $k-2$ vertices in $B$, so these neighbourhoods must have a common intersection $U$ with at least $k-6$ vertices. If $k\ge 9$, then $U$ contains at least 3 vertices, so $S'\cup U$ induces a blue $K_{3,3}$.

This shows that $k\ge 9$ is enough to always meet the conditions, and 9 is therefore an upper bound on the desired quantity.

What remains is to either demonstrate a counterexample with $k=8$ (which would show that the desired quantity is 9), or to show that $k=8$ is always enough to guarantee a red triangle or a blue $K_{3,3}$ (which would show it is 8).

Answer 2

An upper bound on the first question is $k\leq 15$: Take a set of $5$ $a$s $A=\{a_1,\dots,a_5\}$, $5$ $b$s $B_1=\{b_1,\dots,b_5\}$ and $5$ $c$s $C_1=\{c_1,\dots,c_5\}$. We know that at most 2 of the $a$s don't have a neighbor among the $B$s, otherwise we found a complement of a $K_{3,3}$, which is forbidden. The same holds for $a$s and $c$s. Thus there must be one $a_1'$ that has a neighbor among both sets. We call these neighbors $b_1'$ and $c_1'$ respectively.

We now fix the set $A$ and consider $10$ additional pairs of sets of $b$s and $c$s $(B_i,C_i)_{i\in\{2,\dots,11\}}$ with $$B_i=\{b_{i+4}\}\cup(B_{i-1}\setminus \{b_{i-1}'\})$$ and $$C_i=\{c_{i+4}\}\cup(C_{i-1}\setminus \{c_{i-1}'\})$$ and choose $b_i'$ and $c_i'$ such that they're both neighbors of the same $a_i' \in A$ (which all exist by the observation above).

Now at least $3$ pairs of sets agree on the same $a$ by the pigeonhole principle, i.e. there is an $a_l\in A$ and pairwise different $m_1,m_2,m_3 \in \{1,\dots,11\}$ such that $a_l = a_{m_1}' = a_{m_2}' = a_{m_3}'$. Now $b_{m_p}'$ and $c_{m_p}'$ are neighbors of $a_l$ for $p\in\{1,\dots,3\}$. Thus for some $p,p'\in \{1,2,3\}$ the set $\{a_l,b_{m_p}',c_{m_{p'}}'\}$ induces a triangle of friends.

Answer 3

Following András Salamon's comment, I decided to pose my question as a SAT problem. I created a Javascript application that takes as input the number of candidates per profession ($k$), and generates a CNF formula that defines a graph with k candidates per profession, that contains an edge between each two triples, but does NOT contain a triangle of candidates.

If that formula is satisfied, it means that $k$ is too small to guarantee that there is always a feasible team. If that formula is not satistied, it means that $k$ is large enough since there is always a feasible team.

I created MiniSAT input files for $k=3..8$. For $k<=7$, MiniSAT returned in less than a second, saying that it is satisfiable (i.e. k is too small). Here is the assignment MiniSAT found for $k=7$. This means that 8 is a lower bound on the number of required candidates (better than the lower bound of 7 that I found in the previous answer).

For $k=8$, I started MiniSAT several minutes ago, and it is still running. The input file contains 192 variables and 9920 clauses. I don't know how much time it will take it to finish.

Based on the slowness of computation (and assuming I don't have a bug in the implementation), I conjecture that 8 or at most 9 candidates are enough. But I still wait to see what MiniSAT says.

Here is the current output:

============================[ Problem Statistics ]=============================
|                                                                             |
|  Number of variables:           192                                         |
|  Number of clauses:            9920                                         |
|  Parse time:                   0.01 s                                       |
|  Simplification time:          0.03 s                                       |
|                                                                             |
============================[ Search Statistics ]==============================
| Conflicts |          ORIGINAL         |          LEARNT          | Progress |
|           |    Vars  Clauses Literals |    Limit  Clauses Lit/Cl |          |
===============================================================================
|       100 |     192     9920    86208 |     3637      100     16 |  0.003 % |
|       250 |     192     9920    86208 |     4001      250     22 |  0.003 % |
|       475 |     192     9920    86208 |     4401      475     25 |  0.003 % |
|       812 |     192     9920    86208 |     4841      812     29 |  0.003 % |
|      1318 |     192     9920    86208 |     5325     1318     31 |  0.003 % |
|      2077 |     192     9920    86208 |     5857     2077     32 |  0.003 % |
|      3216 |     192     9920    86208 |     6443     3216     35 |  0.003 % |
|      4924 |     192     9920    86208 |     7088     4924     34 |  0.003 % |
|      7486 |     192     9920    86208 |     7796     3907     35 |  0.003 % |
|     11330 |     192     9920    86208 |     8576     7751     36 |  0.003 % |
|     17096 |     192     9920    86208 |     9434     4866     39 |  0.003 % |
|     25745 |     192     9920    86208 |    10377     8762     36 |  0.003 % |
|     38719 |     192     9920    86208 |    11415     6081     39 |  0.003 % |
|     58180 |     192     9920    86208 |    12557     8338     35 |  0.003 % |
|     87372 |     192     9920    86208 |    13812    12272     37 |  0.003 % |
|    131161 |     192     9920    86208 |    15194     7495     36 |  0.003 % |
|    196845 |     192     9920    86208 |    16713    12107     38 |  0.003 % |
|    295371 |     192     9920    86208 |    18384     9989     32 |  0.003 % |
|    443160 |     192     9920    86208 |    20223    10152     40 |  0.003 % |
|    664843 |     192     9920    86208 |    22245    18854     37 |  0.003 % |
|    997368 |     192     9920    86208 |    24470    15595     40 |  0.003 % |
|   1496156 |     192     9920    86208 |    26917    15102     34 |  0.003 % |
|   2244338 |     192     9920    86208 |    29608    19091     42 |  0.003 % |
|   3366612 |     192     9920    86208 |    32569    16905     35 |  0.003 % |
|   5050023 |     192     9920    86208 |    35826    21640     37 |  0.003 % |
|   7575139 |     192     9920    86208 |    39409    34856     39 |  0.003 % |
|  11362814 |     192     9920    86208 |    43350    20735     38 |  0.003 % |
|  17044326 |     192     9920    86208 |    47685    35456     42 |  0.003 % |
|  25566595 |     192     9920    86208 |    52453    43639     34 |  0.003 % |
|  38349998 |     192     9920    86208 |    57699    48290     42 |  0.003 % |
|  57525103 |     192     9920    86208 |    63469    22810     40 |  0.003 % |
|  86287761 |     192     9920    86208 |    69816    55424     36 |  0.003 % |
| 129431749 |     192     9920    86208 |    76797    69548     43 |  0.003 % |

After additional 4 hours, still no result:

| 194147731 |     192     9920    86208 |    84477    67509     38 |  0.003 % |
| 291221704 |     192     9920    86208 |    92925    61375     34 |  0.003 % |

Answer 4

Upper bound of 9:

I am using the characterization of Yuval Filmus.

Suppose that a vertex in A has at least 3 red neighbors in both B and C. Then either there is a red edge across the two neighbor-sets, which results in a red triangle or there is a blue $K_{3,3}$.

So if k>=6, we obtain that there are three vertices in A each of which have at most 2 red neighbors in B (w.l.o.g- in B). Thus, these 3 vertices must have at least k-6 blue neighbors in common. If $k \geq 9$, we get a blue $K_{3,3}$.

Answer 5

As a lower bound, here is a proof that 5 candidates of each profession are not enough. Suppose there are $n=5$ candidates numbered $i=0..4$, with the following relations:

• Alchemist $i$ likes Builder $i$
• Builder $i$ likes Computerist $i$
• Computerist $i$ likes Alchemist $(i+1)\ mod\ n$.

By the pigeonhole principle, in every group of 3 alchemists and 3 builders there is at least 1 pair that like each other (ditto for the other professions). However, the entire graph is a single circle of length 15, and there is no circle of length 3.

The construction can be extended for $n=6$, by adding the following large circle:

• $A[i]$ likes $B[(i+1)\ mod\ n]$
• $B[i]$ likes $C[(i+1)\ mod\ n]$
• $C[i]$ likes $A[(i+2)\ mod\ n]$

Unfortunately, the construction doesn't work for $n>6$. There is still a wide gap between this lower bound and frafl's upper bound of 15.