Spring 2001
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  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


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


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


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


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


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


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

SPEAKER:      Professor Arthur Sherk
AFFILIATION:  University of Toronto


    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


   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


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


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


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


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


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