Jan 25 | Mark A. Fitch | Clemson University | A Clarification of Allowable Sequences |

Feb 1 | Shuhong Gao | Clemson University | Factoring polynomials via PDE |

Feb 8 | Jenny Key | Clemson University | Permutation Decoding |

Feb 15 | Gretchen Matthews | University of Tennessee | Gap sets and minimum distances of algebraic geometry codes |

Feb 22 | Martyn Mulder | Erasmus Universiteit Rotterdam, Holland | Constant tolerance graphs on subtrees of a tree |

Feb 26 | Hiren Maharaj | Institute of Discrete Mathematics, Austria | Asymptotic results in coding theory and curves over finite fields |

Mar 1 | Arthur Sherk | University of Toronto | THE GEOMETRY OF REGULAR SPREADS IN FINITE PROJECTIVE SPACES |

Mar 8 | Renling Jin | College of Charleston | Density Problems in Additive Number Theory |

Mar 15 | Renu Laskar | Clemson University | On Grundy, Partial Grundy and Parsimonious colorings of Graphs |

Mar 29 | Tom Mcdonald | Clemson University, ECE | Error-control codes for packet-radio networks |

Apr 5 | Petter Kristiansen | University of Bergen, Norway | Generalized H-coloring of Graphs |

Apr 12 | Erich Kaltofen | North Carolina State University | Symbolic computation in the new century: The road ahead |

Apr 19 | Virginia Rodrigues | Clemson University | Irreducibility of Polynomials Modulo p via Newton Polytopes |

January 25, 2001

TITLE: A Clarification of Allowable
Sequences

SPEAKER: Mark A. Fitch

AFFILIATION: Clemson University

ABSTRACT:

Allowable sequences are a combinatorial structure that encodes information about point configurations in the affine plane. In 1979 Jacob Goodman and Richard Pollack developed allowable sequences in order to classify "essentially different," non-degenerate point configurations. Subsequently allowable sequences have been developed to study various questions involving point configurations and convexity.

In this talk I present the geometric derivation of allowable sequences
and proceed to develop three, complementary structures that represent an
allowable sequence. I will also develop various geometric properties and
symmetries in

allowable sequences. As a motivation for this work, the construction
of a non-realizable, slope critical double polygon will be presented.

February 1, 2001

TITLE: Factoring polynomials via
PDE

SPEAKER: Shuhong Gao

AFFILIATION: Clemson University

ABSTRACT:

A new method is presented for factorization of bivariate polynomials
over an arbitrary field. It is based on a simple partial differential
equation that gives a system of linear equations. Like Berlekamp's and
Niederreiter's algorithms for factoring univariate polynomials, the dimension
of the solution space of the linear system is equal to the number of absolutely
irreducible factors of the polynomial to be factored and any basis for
the solution space gives a complete factorization by computing gcd and
by factoring univariate polynomials over the ground field. The new method
finds absolute and rational

factorizations simultaneously and is easy to implement for finite fields,
local fields, number fields, and the complex number field. The theory
of the new method allows an effective Hilbert irreducibility theorem, thus
an efficient reduction of polynomials from multivariate to bivariate.

February 8, 2001

TITLE: Permutation decoding

SPEAKER: J. D. Key

AFFILIATION: Clemson University

ABSTRACT:

Permutation decoding was first developed by Jesse MacWilliams in the
early 60's. It can be used when a code has sufficient automorphisms
to ensure the existence of set of automorphisms that satisfy certain conditions:
a PD-set for a code is a set S of automorphisms of the code which is such
that, if the code can correct t errors, then every possible error vector
of weight t or less can be moved by some member of S out of the information
positions. That such a set will fully use the error-correction potential
of the code follows from an early result which we will prove, but that
such a set exists at all is

clearly not always true. There is a bound on the minimum size that
the set S may have, which we will quote.

This talk will mostly simply explain the method, and some ways of finding such sets for some particular codes with large groups, for example cyclic codes, or those with some of the classical groups acting. A short Magma demonstration of the decoding might be included, finding some PD-sets for some binary codes of length 28 with a unitary group acting, and some 5-ary cyclic codes of length 31 with the projective general linear group acting, and showing how they work.

February 15, 2001

TITLE: Gap sets and minimum distances of algebraic
geometry codes

SPEAKER: Dr. Gretchen L. Matthews

AFFILIATION: University of Tennessee, Knoxville

ABSTRACT:

A primary goal of algebraic coding theory is to construct error-correcting codes over finite fields for which the dimension and minimum distance are large with respect to the length. This yields codes with high information rates and error-correcting capabilities. In 1981, V.D. Goppa discovered that curves over finite fields may be used to construct a large class of codes, called algebraic geometry codes. He then obtained bounds on the dimension and minimum distance of these codes. We will show how gap sets allow one to improve Goppa's bound on the minimum distance of certain algebraic geometry codes.

February 22, 2001

TITLE: Constant tolerance graphs
on subtrees of a tree

SPEAKER: Professor Henry Martyn Mulder

AFFILIATION: Econometrisch Institut, Erasmus Universiteit Rotterdam,
Holland

ABSTRACT:

Given a constant t, a host tree T and a family of subtrees of T, we
can construct a new graph G that has the subtrees as vertices, where two
vertices of G are joined whenever the corresponding subtrees share at least
t nodes of the host tree T. Such a graph G is a tolerance graph. These
tolerance graphs are a generalization of the well-known chordal graphs.
In

the talk we survey the state of the art in the area of these tolerance
graphs, and present some challenging open problems.

February 26, 2001

TITLE: Asymptotic results in coding
theory and curves over finite fields

SPEAKER: Dr. Hiren Maharaj

AFFILIATION: Institute of Discrete Mathematics, Austria

ABSTRACT:

The distribution of parameters of arbitrarily long codes is a central problem in coding theory. Interest in this problem has its roots in an important theorem of Shannon which states that it is possible to transmit information in such a way that the probability of error decreases as the length of the codes increase. In the 1970's, the introduction of algebraic-geometric codes by Goppa eventually resulted in much progress in this direction. Ihara defined the quantity A(q), which is the lim sup as g approaches infinity of the ratio of the maximum number of rational points a curve of genus g defined over a finite field F_q may have over its genus g. This quantity is of great relevance in the study of the asymptotics of algebraic-geometric codes. It is known that A(q) <= q^(1/2)-1 and equality holds when q is a square.

When q is not a square, A(q) is unknown.

In the talk, we describe the importance of this quantity A(q) and, in this context, a generalisation of the Tsfasman-Vladut-Zink bound. We will describe some of the techniques used to find improvements of lower bounds of A(q) when q is not a square. Finally, if time permits, we briefly indicate current lines of research in this area.

March 1, 2001

TITLE: THE GEOMETRY OF REGULAR
SPREADS IN FINITE PROJECTIVE SPACES

SPEAKER: Professor Arthur Sherk

AFFILIATION: University of Toronto

ABSTRACT:

A spread in PG(2t+1, q) is a set of (t+1)-flats, called components,that partition the space.

Any set of 3 mutually skew (t+1)-flats in PG(2t+1, q) generate a regulus. A spread is said to be regular if with any 3 of its components it contains the entire regulus generated by these components.

The components of a regular spread are the points of what may be called a finite inversive space of dimension t+1, and the reguli are the circles. We examine some of the unfamiliar properties possessed by a finite inversive space of dimension 3.

March 8, 2001

TITLE: Density Problems in Additive
Number Theory

SPEAKER: Professor Renling Jin

AFFILIATION: College of Charleston

ABSTRACT:

Let A and B be sets of natural numbers. In additive number theory, people are interested in finding relations between the sizes of A, B and the size of A+B. The size of a set can be the cardinality of the set if the set is finite or can be one of several densities if the set is infinite. Using nonstandard analysis, I recently discovered some new results about upper asymptotic density or upper Banach density. These results witness the following three general phenomena in additive number theory.

(1) Sumset phenomenon: If A and B are "large in terms of measure", then A+B is not "small in terms of order-topology".

(2) Buy one get one free scheme: For every theorem about Shnirel'man density or lower asymptotic density, there is a parallel theorem about upper Banach density.

(3) Inverse phenomenon: If A+A is small, then A must have some structure.

In the talk I shall, in layman's language, present the ideas in nonstandard analysis and explain how these ideas are applied to density problems in additive number theory.

March 15, 2001

TITLE: On Grundy, Partial Grundy
and Parsimonious colorings of Graphs

SPEAKER: Professor Renu Laskar

AFFILIATION: Clemson University

ABSTRACT:

A (proper) k-coloring of a graph G=(V,E) is a partition of V(G) into k independent sets, called color classes. In a k-coloring f, a vertex v in V_i is called a Grundy vertex if v is adjacent to at least one vertex in every color class V_j, for every j, 1<=j<=i. A k-coloring is called a Grundy coloring if every vertex is a Grundy vertex. A k-coloring is called a partial Grundy coloring if every color class contains at least one Grundy vertex. We introduce partial Grundy colorings and relate them to parsimoneous proper colorings introduced by Simmons in 1982.

This is a joint work with S.T. Hedetniemi

March 29, 2001

TITLE: Error-control codes for packet-radio
networks

SPEAKER: Tom Macdonald (Ph.D. candidate, ECE)

AFFILIATION: Clemson University

ABSTRACT:

The performance of many communication systems can be improved by using error-control codes. Examples of systems that use error-control codes include cell phones, CD players, and many deep-space missions. In this talk a brief overview of basic communication theory will be presented, and the motivation behind using error-control codes will be discussed. The use of coding in one particular application, packet-radio networks, will be coverd in detail. Often Reed-Solomon codes are used in packet radio networks, but Hermitian codes are an attractive alternative. The performance of systems using each type of coding will be evaluated, and the advantages of each type of coding will be explained.

April 5, 2001

TITLE: Generalized H-coloring of
Graphs

SPEAKER: Petter Kristiansen (PhD Candidate)

AFFILIATION: University of Bergen, Norway

ABSTRACT:

In this talk, a generalization of H-coloring of graphs is introduced. The relation among these colorings will be discussed and the related computational issues (e.g. NP-complete) will be emphasized.

April 12, 2001

TITLE: Symbolic computation in the
new century: The road ahead

SPEAKER: Professor Erich Kaltofen

AFFILIATION: North Carolina State University

ABSTRACT:

Symbolic mathematical computation in the past 40 years has brought us
remarkable theory: Groebner bases, the Risch

integration algorithm, polynomial factorization, lattice reduction,
hypergeometric summation algorithms, sparse polynomial interpolation, etc.
And our discipline produced remarkable software, like the Mathematica or
the Maple system, which deliver implementations of these algorithms to
the masses. Several system designers even became rich by selling
their software. As it turned out, a killer application of computer algebra
is high energy physics, where a special purpose computer algebra system,
SCHOONSHIP, helped in work worthy of a Nobel Prize in physics in 1999.

With such a stellar track record it becomes difficult to foretell the future. I will speak about trends that I myself can observe: black box objects, plug-and-play software components and data exchange standards and protocols (e.g., MathML), heuristics vs. algorithms, imprecise data (e.g., floating point scalars). Finally, I will state my favorite problems in computer algebra left open in the last century whose resolution I believe would be of great help to us.

Short Bio:

Erich Kaltofen received both his M.S. degree in Computer Science in 1979 and his Ph.D. degree in Computer Science in 1982 from Rensselaer Polytechnic Institute. He was an Assistant Professor of Computer Science at the University of Toronto and an Assistant, Associate, and full Professor at Rensselaer Polytechnic Institute. Since 1996 he is a Professor of Mathematics at North Carolina State University. Kaltofen has held visiting positions at the Mathematical Sciences Research Institute in Berkeley, California (2000 and 1985), at the University of Grenoble (2000 and 1999), at Simon Fraser University (1998), and at the Tektronix Computer Research Laboratory in Oregon (1985).

His current interests are in computational algebra and number theory, design and analysis of sequential and parallel algorithms, and symbolic manipulation systems and languages. Kaltofen was the Chair of ACM's Special Interest Group on Symbolic & Algebraic Manipulation 1993 - 95. He serves as associate editor on several journals on symbolic computation. From 1985 - 87 he held an IBM Faculty Development Award. From 1990 - 91 he was an ACM National Lecturer. He has edited 3 books, published over 100 research articles, and has contributed to the Waterloo Maple system and written symbolic computation software in Lisp and C++ (the Dagwood, FoxBox, and LinBox systems).

[URL: http://www.math.ncsu.edu/~kaltofen]

April 19, 2001

TITLE: Irreducibility of Polynomials
Modulo p via Newton Polytopes

SPEAKER: Virginia Rodrigues (PhD Candidate)

AFFILIATION: Clemson University

ABSTRACT:

It is well known that for an absolutely irreducible polynomial over the rationals, its reduction modulo a prime p remains absolutely irreducible if p is sufficiently large (due to Ostrowski, 1919).

In this talk we are interested in the problem of finding explicit bounds for the size of such primes. We present a new bound based on the existence of solutions of a partial differential equation and the number of integral points in the Newton polytope of the polynomial. This result improves previous estimates given by Ruppert(1986, 1999) and Zannier (1997).

Joint work with Shuhong Gao

Back to ADM Seminar Page