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?
Asked By : Erel Segal-Halevi
Answered By : András Salamon
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).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/12275
0 comments:
Post a Comment
Let us know your responses and feedback