patternMinor
Team construction in tri-partite graph
Viewed 0 times
graphconstructionteampartitetri
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#12275, answer score: 4
Revisions (0)
No revisions yet.