Furnishing a Hypercube: An Algebraic Approach to Arrangements of Zeroes and Ones

Prof. William J. Martin
Depts. of Mathematical Sciences and Computer Science, WPI

November 22, 2002
11 a.m. - 12 noon
Fuller Labs 320

Abstract

Suppose you lived inside a hypercube (without any concept of which way is "up", of course) and you want to put furniture in various corners subject to restrictions. For example, in a 3-cube, how many pieces of furniture could you use if you were required to traverse at least two edges (segments where two walls meet) to get from any piece to any other? (How about the same question with "at least three"?) On the other hand, suppose you wanted each of the six walls to have exactly two pieces of furniture touching it; how would you arrange that? (Try the same question with "exactly one".)

Of course, we are talking about collections of 01-strings with prescribed restrictions. In this talk we will introduce an algebraic approach to such generic structures called "codes" and "designs". The prototypical examples are error-correcting codes for digital communications and designs of statistical experiments. However, we will need to imagine uses for these structures far beyond what was originally envisioned. Arrangements of this sort arise in cryptography, numerical integration, software testing and are often connected to beautiful objects in algebra, geometry and combinatorics.

One of the main tools in our study of such configurations is the linear programming bound of Delsarte. Even at the very practical level of implementing this technique, we encounter interesting computational challenges such as "How does one efficiently (i.e. using only a few CPU months and a few Gb of RAM) and accurately (i.e. to some believable, yet non-trivial level) solve linear programs involving thousands of variables and constraints wh40-digit integer coefficients?"

Refreshments will be served in FL 320 beginning at 10:50 a.m.

Maintained by webmaster@wpi.edu
Last modified: Sep 27, 2006, 16:05 EDT