Algebra and Discrete Math Seminar
Spring 2002

 Jan 24 Shuhong Gao Clemson University A new algorithm for decoding Reed-Solomon codes Jan 31 John Villalpando Clemson University L(2,1) Colorings and its Application to the Channel Assignment Problem Feb   7 David Penniston Furman University Ramanujan congruences for m-regular partition functions Feb 14 Wayne Goddard University of Natal, South Africa Mastermind and Static Mastermind Revisited Feb 21 Jeff Stroomer Xilinx, Inc. Robinson-Schensted-Knuth Insertion and the Jeu de Taquin Feb 28 David P. Jacobs CS, Clemson University Designing Self-stabilizing Algorithms Mar  7 Mike Pursley* ECE, Clemson University Binary Shift-Register Sequences:  Correlation Properties andApplications Mar 14 Gilberto Bini University of Michigan, Ann Arbor Some families of finite commutative rings and their applications to Coding Theory Mar 15 Ken Ono* University of Wisconsin at Madison The Number Theory of Partitions Spring Break  March 18--22 Mar 26 Arthur Sherk University of Toronto Metric Geometry Induced by a Field Mar 28 Warren Adam Clemson University Computing Linear Programming Relaxations of Discrete Sets:  A Special Case yielding the Convex Hull Apr  4 Hiren Maharaj Clemson University Explicit towers of function fields over finite fields Apr 11 Robert E. Jamison Clemson University Meet-Tolerance Graphs Apr 18 John Swallow Davidson College Galois module structure of the group of p-th power classes of a cyclic field Apr 25 J. D. Key Clemson University Binary codes of triangular graphs and permutation decoding

* indicates Dept Colloquium speaker.

January 24, 2002

TITLE:                  A new algorithm for decoding Reed-Solomon codes
SPEAKER:           Shuhong Gao
AFFILIATION: Clemson University

ABSTRACT:

We develop a simple new algorithm for decoding Reed-Solomon codes. Our method uses fast Fourier transforms and computes the message  symbols directly without finding error locations or error magnitudes. Compared with the Berlekamp-Massey algorithm which was discovered in the late 1960's, the new method has a similar time complexity but  requires simpler structures in both hardware and software implementations.

January 31, 2002

TITLE:                    L(2,1) Colorings and its Application to the Channel Assignment Problem
SPEAKER:            John Villalpando
AFFILIATION:  Clemson University

ABSTRACT:

The channel assignment problem is the problem of assigning frequencies to radio transmitters in such a way that the communications do not  interfere.  Two transmitters are considered to interfere with each other if they share similar frequencies and are at a prescribed distance from one another.

An L(2,1) coloring of a graph G is a non-negative labeling f of V(G)  such that adjacent vertices differ in color by two and vertices at distance  two differ in color.  The span \lambda(G) on a graph G is the smallest k such that there exists an L(2,1) coloring using only the colors {0,1, ... , k} to color the vertices of G.

In this presentation we begin by discussing the channel assignment problem.  We focus on L(2,1) colorings and their relationship to the channel assignment problem.  We introduce no-hole and irreducible L(2,1) colorings, and consider the lower no-hole span $\lambda_f(G)$ and the upper no-hole span \Lambda_f(G) of a graph G.  We determine the lower and upper no-hole span for paths and cycles.  We finish by demonstrating the existence of an irreducible no-hole coloring on all trees that are not stars.

February 7, 2002

TITLE:                      Ramanujan congruences for m-regular partition functions
SPEAKER:              David Penniston
AFFILIATION:     Furman University

ABSTRACT:

The great Indian mathematician S. Ramanujan proved that the unrestricted partition function p(n) has the remarkable property
that for every nonnegative integer n,

p(5n+4) is divisible by 5,
p(7n+5) is divisible by 7, and
p(11n+6) is divisible by 11.

Recently K. Ono has shown that p(n) satisfies similar "Ramanujan congruences" for every prime that is at least 5.

In this talk we focus on m-regular partitions, which are those partitions none of whose parts is divisible by m.  In particular, we will see that for certain values of m, the m-regular partition function satisfies Ramanujan congruences, and along the way see some (surprising?) connections with elliptic curves, K3 surfaces and representation theory.

February 14, 2002

TITLE:                      Mastermind and Static Mastermind Revisited
SPEAKER:              Wayne Goddard
AFFILIATION:     University of Natal

ABSTRACT:

In Mastermind a codesetter creates an n-position secret code from a palette of k colours and a codebreaker must determine
the code with a series of questions. In the static version, the codebreaker must supply at one go a list of questions the answers to which must uniquely determine the secret code. In this talk we discuss what is known about the optimal strategies for the original game against a random opponent and against an adversary. For static mastermind we solve it for small cases. Possibly surprising is the solution for 4 positions and arbitrary k.

February 21, 2002

TITLE:                       Robinson-Schensted-Knuth Insertion and the Jeu de Taquin
SPEAKER:               Jeff Stroomer
AFFILIATION:      Xilinx, Inc.

ABSTRACT:

Most algorithms are understandable: one understands (perhaps after some study)  what makes the algorithm work.  A few, however, are mysterious: we are confident the algorithm works because we have proved it does, but it's not clear why the algorithm ought to work.   In this talk we discuss two mysterious algorithms, namely Robinson-Schensted-Knuth insertion, and Schützenberger's jeu de taquin.  Each is simple enough to describe in a few minutes, and can be performed by hand with pencil and paper.  Nevertheless, their results describe, in combinatorial terms, the workings of the  symmetric group, symmetric functions, and representations of the symmetric group and general linear group.

February 28, 2002

TITLE:                      Designing Self-stabilizing Algorithms
SPEAKER:              David Jacobs
AFFILIATION:     CS, Clemson University

ABSTRACT:

In the usual algorithmic model, many graph problems (like finding a maximal independent set) are trivial, requiring for example, only a simple greedy loop.  But in the self-stabilizing distributed model such problems are less obvious.  In this model, a node can read only its own variables and those of its neighbors.  This talk will explain the model,  give examples of several self-stabilizing algorithms discovered by our algorithms group (for finding maximal independent sets, minimal dominating sets, colorings, maximal matchings, and maximal k-dependent sets), and discuss some proof techniques that have been found useful.

March 7, 2002

TITLE:                  Binary Shift-Register Sequences:  Correlation Properties andApplications
SPEAKER:           Michael Pursley
AFFILIATION:  ECE, Clemson University

ABSTRACT:

Direct-sequence spread-spectrum systems employ pseudorandom and related sequences to permit reliable communications in the presence of various types of interference, such as multipath interference, multiple-access interference, and interference from narrow-band emitters operating in the same frequency band.  The sequences must be selected to have good correlation properties in order for the potential benefits of direct-sequence spread spectrum to be realized, and the correlation properties adopted for sequence selection must be matched to the intended applications for the spread-spectrum system.  The periodic and aperiodic correlation properties of some well-known sequences are presented and their relevance to system performance is described.

Biography for Michael B. Pursley

Michael Pursley was a faculty member in the Department of Electrical and Computer Engineering and the Coordinated Science Laboratory at the University of Illinois during 1974-93.  Since then he has been the Holcombe Professor of Electrical and Computer Engineering at Clemson University.  He has held visiting faculty positions at UCLA and the Caltech.

Dr. Pursley is a Fellow of the  Institute of Electrical and Electronics Engineers (IEEE), he has served on the Board of Governors of the IEEE Information Theory Society, and he served as president of the Information Theory Society.  He was a member of the Editorial Board of the Proceedings of the IEEE for the period 1984-1991.  He is currently a member of Editorial Advisory Board for the International Journal of Wireless Information Networks, and a senior editor for the IEEE Journal of Selected Areas in Communications.

Dr. Pursley was awarded an IEEE Centennial Medal in 1984, and in 1996 he received the Ellersick Award of the IEEE Communications Society.  In 2000 he received an IEEE Millennium Medal. He has also received several awards from Clemson University for research and scholarly achievement.

March 14, 2002

TITLE:                    Some families of finite commutative rings and their applications to Coding Theory
SPEAKER:            Gilberto Bini
AFFILIATION:   University of Michigan, Ann Arbor

ABSTRACT:

In the last decade, some nonlinear binary error-correcting codes have been viewed more easily as images of codes over Galois rings. In particular, the formal duality between binary Kerdock codes and Preparata codes has been interpreted as ordinary duality over the ring of integers modulo 4. In this talk, we shall give an overview on various significant properties of two families of finite commutative rings, i.e., the Galois rings and the Quasi-Galois rings. Additionally, some applications to Coding Theory will be discussed.

March 15, 2002

TITLE:                        The Number Theory of Partitions
SPEAKER:                 Ken Ono
AFFILIATION:        University of Wisconsin at Madison

ABSTRACT:

At first glance, the stuff of partitions seems like child's play. After all, 4=3+1=2+2=2+1+1=1+1+1+1, and so p(4)=5. We will discuss classical works of Hardy, Ramanujan and Rademacher on asymptotics and congruences and conclude with more recent works. Recently we have learned quite a bit about congruences for the number of partitions and have learned of new connections with deep and subtle questions in arithmetical algebraic geometry.

March 26, 2002

TITLE:                   Metric Geometry Induced by a Field
SPEAKER:            Arthur Sherk
AFFILIATION:   University of Toronto

ABSTRACT:

Let K be an n-fold extension of a field F. That is to say, K is an n-dimensional vector space over F, and K itself is a field. Using the Norm and Trace mappings of K onto F, we define measures of length and angle, thus turning K into a metric geometry, which we call G(K).

The classical example is G(C), where C is the field of Complex Numbers. It is well-known that G(C) is  Euclidean Plane Geometry.

In this talk, we examine G(K), where K is a quadratic extension of the finite field GF(q) (q odd), finding G(K) to be the "natural" finite equivalent of Euclidean Plane Geometry. We then study G(K), where K is a cubic extension of GF(q) ( q and 6 relatively prime). In this case, G(K) does not resemble Euclidean Geometry at all, but is a reasonable finite equivalent of classical Elliptic Geometry.

March 28, 2002

TITLE:                     Computing Linear Programming Relaxations of Discrete Sets:  A Special Case yielding the Convex Hull
AFFILIATION:     Clemson University

ABSTRACT:

Given a polyhedral set, a fundamental problem in integer programming is to obtain an explicit algebraic characterization of the convex hull of binary points that lie within the set.  Such a characterization reduces a 0-1 optimization problem to a much simpler linear program.  One method for accomplishing this is a reformulation-linearization technique (rlt).  As the name suggests, the method is a two-step procedure that first reformulates the problem through the construction of redundant nonlinear inequalities, and subsequently linearizes the resulting program by casting it in a higher dimensional space through a substitution of variables.  Depending on the manner in which the reformulation is computed, different polyhedral outer approximations of the set of desired 0-1 points are obtained.  The tightest approximation is the convex hull.  Unfortunately, the representation yielding the convex hull can have both an exponential number of constraints and variables. This talk gives an intuitive review of the rlt and then focuses on a discrete problem arising in cryptography.  The motivating challenge is to factor an integer into the product of primes.  A variant of this problem has been considered in the literature.  For this variant, the convex hull is characterized and the exponential number of facets provided.  We show how this characterization is readily available in terms of a straightforward application of the rlt.  In fact, we give a representation in a higher-variable space whose projection onto the space of the original variables gives the convex hull and all its facets.  The higher-dimensional polytope is polynomial in size in terms of the number of variables and constraints.

The original investigations in the rlt are joint work with Hanif Sherali of Virginia Tech, and the more recent advances in cryptography were performed in collaboration with Robin Lougee-Heimer of IBM TJ Watson Research Center and Shuhong Gao of Clemson University.

April 4, 2002

TITLE:                   Explicit towers of function fields over finite fields
SPEAKER:            Hiren Maharaj
AFFILIATION:   Clemson University

ABSTRACT:

Explicit towers of function fields over finite fields make it possible to explicitly construct asymptotically good sequences of algebraic geometric codes. By concatenation with short block codes, these codes have asymptotic performance close to  or exceeding the Gilbert-Varshamov bound. The first family of such towers was discovered in 1995 by  Garcia and Stichtenoth. Today, the search for further families of  towers is still on. This introductory talk will explain why this is the case and  also how one may go about finding towers.

April 11, 2002

TITLE:                    Meet-Tolerance Graphs
SPEAKER:             Robert E. Jamison
AFFILIATION:    Clemson University

ABSTRACT:

Let $S_1, S_2, S_3, ..., S_d$ denote finite sets.  For any integral tolerance t with  $0 < t < d$, define the meet-tolerance graph $MG_t(S_1, S_2, S_3, ..., S_d)$ as follows.  The vertices are all vectors $[x_1, x_2, ..., x_d]$ where  $x_i \in S_i$.  Two vectors are adjacent iff they agree in at least $t$ coordinates.

The sets S_i will be called the (coordinate) {\em stacks}.  We may picture the meet-tolerance graph by imagining the stacks as lined up side by side with a vertex represented by a choice of one element from each stack.  The vertices thus represent the choice functions for the set system $[ S_1, S_2, S_3, ..., S_d ]$. Two such functions are adjacent iff they agree in at least t places.  For $t = 1$, the meet-tolerance graphs are the co-categorical products of complete graphs (independents sets).  These have been studied (sometimes in the complementary form) by Lovasz, Nesetril, Novick, Perkel, Putr, Rall, and others.

For $t = d-1$, the meet-tolerance graphs are box (Cartesian) products of complete graphs, called Hamming graphs by Bandelt and Mulder. For any integer $0 < p < t,$ it is easy to check that the $p$th power of the Hamming graph $MG_{d-1}(s_1, s_2, ..., s_d)$ is just $MG_{d-p}(s_1, s_2, ... , s_d)$. Here the $p$th power of a graph $G$ has $v$ and $w$ adjacent iff $distG(v,w) \leq p$.  Thus the meet-tolerance graphs are just powers of Hamming graphs.  For the purposes of the present investigation, however, it seems more natural to view the case $t=1$ as the base case with larger tolerances as generalizations ending in the Hamming graphs as an extreme case rather than the other way around.

This talk will survey meet-tolerance graphs, outline their origins in number theory, discuss the independence number $\alpha(G)$ , the chromatic number $\chi(G)$, and the clique number $\omega(G)$, and indicate their close connection with  finite geometries.

April 18, 2002

TITLE:                    Galois module structure of the group of p-th power classes of a cyclic field
SPEAKER:             John Swallow
AFFILIATION:    Davidson College

ABSTRACT:

Let p be a prime.  In Galois theory over a field K containing a primitive pth root of unity, field extensions L generated by a pth root of an element of K, say L=K(b^(1/p)), correspond to subgroups of order p of a certain group, namely the multiplicative group of pth power classes of the field K.  We denote this by K*/K*^p, where K* is the group of nonzero elements of K.  This correspondence is known as Kummer theory.

In this talk we consider the notion of "Kummer closure extensions": the normal closures of Kummer extensions L/K when K is itself a Galois extension of a field F.  The case of cyclic Galois extensions K/F of degree p^n is of
particular interest.  Waterhouse has determined the possible Galois groups for such extensions, and in joint work with Minac and Schultz we extend his result to determine the Galois group of the "maximal Kummer extension of K", that is, the Galois group of K({b^(1/p): b in K*}) over F.  This Galois group was essentially determined
by Faddeev for local fields, and, surprisingly, the general case displays the same local flavor.

April 25, 2002

TITLE:                     Binary codes of triangular graphs and permutation decoding
SPEAKER:              J. D. Key
AFFILIATION:     Clemson University

ABSTRACT:

For any n, the triangular graph T(n) is the line graph of the complete graph K_n, i.e. the vertices are the 2-subsets of Omega ={1,2,..,n} and vertices {a,b} and {c,d} are adjacent if they have one letter from Omega in common.  Thus the valency is 2(n-1).

If A is an adjacency matrix for T(n) the row span of A over the field GF(2) of order 2 forms a binary code with parameters [n(n-1)/2,n-1,n-1]_2 for n odd and [n(n-1)/2,n-2,2(n-1)]_2 for n even, and we take n >4 to avoid trivial cases. The weight enumerator of the code is known for any n and the minimum weight of the dual code is 3.

The automorphism group of the graph and code is S_n for n > 4 except for n=6 when the code has the larger group PGL_4(2) acting.  We obtain explicit permutation decoding sets in S_n for these codes.

This is joint work with J. Moori and B.~G. Rodrigues of the University of Natal-Pietermaritzburg.