7
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ This problem is known as 3-Dimensional Matching. $\endgroup$ – A.Schulz May 25 '13 at 19:42
  • 2
    $\begingroup$ Thanks. But my problem is a little easier - I am not interested in a maximal matching, only in a single triple. $\endgroup$ – Erel Segal-Halevi May 25 '13 at 20:20
  • 5
    $\begingroup$ This sounds like Ramsey theory. You're asking for the minimal $k$ such that for every $2$-coloring of $K_{k,k,k}$ there is either a red triangle or a blue $K_{3,3}$. $\endgroup$ – Yuval Filmus May 30 '13 at 19:19
  • 2
    $\begingroup$ Not useful for an answer, but I like the name computerist. $\endgroup$ – Luke Mathieson May 31 '13 at 9:41
  • 3
    $\begingroup$ Most of the existing Ramsey theoretic bounds were obtained by posing the existence problem as a SAT instance. See ginger.indstate.edu/ge/RAMSEY/index.html for a summary of results. These do not apply to your problem, but the techniques do. $\endgroup$ – András Salamon Jun 5 '13 at 20:28
3
$\begingroup$

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).

$\endgroup$
4
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Interesting, thanks! Can you prove that this bound is tight (i.e. show a graph with 54 nodes and no triangle?) $\endgroup$ – Erel Segal-Halevi May 31 '13 at 11:18
  • 1
    $\begingroup$ Note that the upper bound proof uses only 5 alchemists out of the 55. Therefore it seems that the bound is not tight, but I am not sure. What do you think? $\endgroup$ – Erel Segal-Halevi May 31 '13 at 11:27
  • $\begingroup$ Actually, I don't believe it's tight, since I didn't use very sophisticated tools. It should be possible to "reuse" some of the $B$s and $C$s in a somewhat more complicated proof, but I haven't found one yet. Probably making the proof more symmetric could be a way. $\endgroup$ – frafl May 31 '13 at 11:27
  • 1
    $\begingroup$ @ErelSegalHalevi: Turned out not to be tight. I didn't see that we don't need disjoint sets, but only sets, that do not contain the fixed $(b,c)$-pairs of all previous sets. $\endgroup$ – frafl May 31 '13 at 16:46
  • $\begingroup$ Great! But you still use only 5 alchemists out of 15, which hints that there may be an even better bound. $\endgroup$ – Erel Segal-Halevi Jun 1 '13 at 18:19
4
$\begingroup$

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 % |
$\endgroup$
3
$\begingroup$

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}$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ At least for 7,8,9 it should be feasible to test them algorithmically. $\endgroup$ – frafl Jun 6 '13 at 10:42
  • $\begingroup$ You mean by trying all possible colorings? $\endgroup$ – Erel Segal-Halevi Jun 7 '13 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.