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?
Team construction in tri-partite graph
graph theory;graphs;combinatorics
The summary so far (as CW).Yuval Filmus rephrased the question in more conventional terms, asWhat 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).