Ron's Site |
Ramblings in mathematics and computer science |
By Ron Zeno
Thursday, July 11, 2002I stumbled upon Dedekind's problem while investigating sorting networks, specifically when studying the properties of certain comparator networks.
Consider the comparator network of 8 inputs: [0:1],[2:3],[4:5],[6:7],[0:2],[1:3],[4:6],[5:7],[0:4],[1:5],[2:6],[3:7]. It can be analyzed by creating a Hasse diagram of the partial sortings that it produces. The first four comparators produce a diagram of four lines. The second four comparators combine the lines to produce two squares. The third four comparators combine the squares to produce a cube. (It is easy to generalize this type of comparator network of 2^n inputs with a corresponding Hasse diagram in the shape of a n-hypercube.)
A second way to analyze this network is by examining how the network maps the 2^8 sequences or zeros and ones. Using the Hasse diagram to assist, such an analysis results in twenty sequences:
00000000, 00000001, 00000011, 00000101, 00000111, 00001111, 00010001, 00010011, 00010101, 00010111, 00011111, 00110011, 00110111, 00111111, 01010101, 01010111, 01011111, 01110111, 01111111, 11111111This is the same list as that of the twenty monotone Boolean functions of three variables here. So, computing M(3) is equivalent to counting the number of ways that a Hasse diagram in the shape of a cube can be labeled with zeros and ones. In general, Dedekind's problem is equivalent to the number of ways a Hasse diagram in the shape of a n-hypercube can be labeled with zeros and ones.
Code to create the comparator network discussed (C, simplified for translation):
void Hyper2(int N) { int i, j, k, l; int comps = 0; // number of comparators i = 1; j = 2; // j starts as twice i while (i < N) { k = 0; while (k < N) { l = 0; while (l < i) { if (i + k + l < N) { // CompEx(k + l, k + l + i); comps++; } l = l + 1; // increment l by 1 } k = k + j; // increment k by j } i = i + i; // Double i j = j + j; // Double j } } // Hyper2Copyright © 2002 Ron Zeno
Comparator network and corresponding Hasse diagram.