The network model for this problem is as follows:
and from the model, we see that it formed a circle and hence without any calculations, the upper and lower bounds for cell Delta/Ph.D. must be equal.
My question is that is the analysis above extensible to three-dimensional tables? My thought is it cannot be applied to a 3-D tables since I can hardly imagine the network model for these cases.. but I am not sure.. Can anybody give me a hint on this? Thanks!
Consider the graph with Alpha, Beta, Gamma, Delta and 1, 2, 3, 4 as vertices. Connect every pair of vertices as per your network model. Two vertices are connected if the corresponding cell which is the intersection of the two labels is a unknown.
The graph in the first example consist of 2 4-cycles and a bridge, for a total of 9 edges and thus 9 unknowns. We hope to find the range of possible values corresponding to (Delta, 4), the edge joining Delta and 4. Observe that for the edges incident to a particular vertex, if all but one of them have known values then by the boundary information we can determine the value corresponding to the last edge. Also, note that this graph is bipartite.
Define the sum at the vertex as the sum of all the values corresponding to the edges incident to that vertex. The sum of each vertex is known (from boundary conditions). Considering odd elements in any cycle, sum of odd vertices is equal to sum of even vertices, if only edges belonging to a cycle are considered. Hence, the graph may be reduced by removing the two 4-cycles, leaving the single edge (Delta, 4), because the other vertices in each cycle only have 2 incident edges.
To generalize to 3-D, suppose we have 3 different categories of labels: A, B, C, D 1, 2, 3, 4 W, X, Y, Z
We join each triplet of labels with 3 edges joining the vertices pairwise: for example, (A, 1, W) would be represented by three edges (A, 1), (1, W), (W, A). Each triangle formed has a corresponding unknown value we can maximize or minimize.
At each pair of vertices, if all triangles except 1 containing the pair of vertices has a known value, the last triangle's value can be found. However, cycles of triangles do not exist other than the base case of the complete 4-graph. Therefore, it would not be easy to generalise this situation into higher dimensions.