Sorting networks and Dedekind's problem

By Ron Zeno
Thursday, July 11, 2002

I 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, 11111111
This 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
    }
}  // Hyper2
Copyright © 2002 Ron Zeno
Comparator network and corresponding Hasse diagram.

Home