Professor Henry Martyn  Mulder
Econometrisch Institut
Erasmus Universiteit Rotterdam

Sylvester and Petersen, and the Emergence of Graph Theory

James Joseph Sylvester (1814 - 1897) may be considered to be the founding father of graph theory. Not only did he inspire his friend Cayley to use rooted trees to solve a problem on differential operators, but he also coined the term graph (while at the Johns Hopkins University, Baltimore). He envisioned a great future for his new Theory of Graphs: it would become the basic theory for modern mathematics and modern sciences.  Although his own contributions were only minor, he played a key role in the creation of the one fundamental graph theory paper of the nineteenth century: "The theory of regular graphs" by the Danish mathematician Julius Petersen (1839 - 1910). In this talk the emergence of graph theory
in the nineteenth century is traced, and its adventures until the early twentieth century are discussed.

TITLE:       Computing Grobner Bases with Hilbert Lucky Primes
SPEAKER:     Elizabeth Arnold
AFFILIATION: University of Maryland

ABSTRACT:

During the execution of Buchberger's algorithm, many intermediate polynomials are generated and then discarded before the final reduced Grobner basis is reached. It is possible for the coefficients of these intermediate polynomials to grow to enormous size, limiting the applicability of this algorithm.  Algorithms using $p$-adic methods have been proposed to control such growth. The success of these algorithms depends on using a ``lucky" prime $p$, that is, a prime $p$
for which algebraic information about the ideal is preserved modulo $p$. After a brief introduction to Grobner bases and their significance, the concept of a ``Hilbert lucky" prime for an ideal will be introduced. Then a method for finding such primes with high probability will be presented.  Finally, an implementable $p$-adic algorithm for the computation of Grobner bases will be discussed and illustrated by an example.

TITLE:       Double (k,s)-gons: Intriguing Point Configurations
SPEAKER:     Mark Fitch
AFFILIATION: Clemson University

ABSTRACT:

Slope critical configurations are sets of points in the affine plane that generate a minimum number of slopes. A search for the minimal configurations brought to light an interesting class of configurations: the double polygons.  These include the well known fano triangle and pentagram. In order to better understand this class Goodman and Pollack's technique of allowable sequences was used.

This talk will present three basic aspects of double polygons as allowable sequences. First geometric and combinatoric definitions of double polygons will be given. Second constructions for critical double polygons will be given. Finally a subclass of double polygons will be shown that are not critical even as allowable sequences.

Dhruv Mubayi
Georgia Institute of Technology

"Explicit Constructions for a Ramsey Problem and Hypergraph Turan Numbers"

The Ramsey number R(p,p) is the minimum n such that every 2-coloring of the edges of the complete graph on n vertices yields a monochromatic copy of a complete subgraph on p vertices. Given an r-uniform hypergraph (or r-graph) H, the Turan number ex(n, H) is the maximum number of edges in an n vertex r-graph containing no copy of H.  Determining R(p,p) or ex(n,H) is a notoriously hard problem in combinatorics, the latter even for very simple hypergraphs. In many
cases, the best known lower bounds for both these problems arise from probabilistic constructions. It is therefore interesting to find good explicit constructions.

We will describe two such recent constructions. The first arises from a set-system, and answers a question in Ramsey Theory due to Erdos and Gyarfas. The second  is obtained by algebraic methods, and yields new asymptotics for an infinite class of Turan numbers for r-partite r-graphs. This addresses (and positively answers in some cases) a question of Erdos  from the 60's. Several related results will also be presented.

TITLE:       Tolerance Representations of Graphs in Trees
SPEAKER:     Robert E. Jamison
AFFILIATION: Clemson University

ABSTRACT:

   A graph G = (V,E) is a tolerance graph with tolerance t provided there is a map v --> Sv from the vertex set V of G into subtrees of a tree T such that vertices v and w are adjacent in G iff the representing subtrees Sv and Sw have at least t nodes in common.  The tree T will be called the host tree for the representation.  By a now classical result of Gavril and Renz, the tolerance t=1 graphs are precisely the chordal graphs (graphs with no induced cycles of length 4 or more).  It is easy to see that every graph G is a tolerance t = 2 graph.

  This might appear to be the end of the story, but it turns out that by placing certain restrictions on either the host tree or the representing subtrees, a very rich theory arises.  The classical case is that in which the host tree is required to be a path.  Then the representable graphs for any tolerance) are the interval graphs.  Although many restrictions are possible, among the simplest and most natural are degree restrictions.  Specifically, we shall call v --> Sv an (h,s,t)-representation provided the maximum degree of the host tree T is at most h, every representing subtree  Sv  has maximum degree at most s, and the tolerance is t.  The class of all (h,s,t)-representable graphs will be denoted for simplicity by just [h,s,t].  This talk will present examples, review the long history, and discuss recognition and inclusion issues for these classes.

Joint work with Henry Martyn  Mulder, Econometrisch Institut,  Erasmus Universiteit Rotterdam

TITLE:       GEOMETRIC REPRESENTATIONS OF SPREAD SETS
SPEAKER:     Arthur Sherk
AFFILIATION: University of Toronto

ABSTRACT:

   Let n be any positive integer > 1, and let q be any prime power.  A spread set S = S(n,q) is a maximal set of nxn matrices {Mi} over GF(q) with the property that Mi - Mj is non-singular for all (i,j).

   We describe three different geometrical representations of spread sets, in affine and projective spaces. The ultimate object of this exercise is to discover hidden properties of spread sets; different representations highlight different properties.

   We illustrate by considering some examples in the case n = q = 3.

TITLE:       Triple Features (But no extra charge at door!)
SPEAKERs:    Ted Doyle, Mark Fitch and John Villalpando
AFFILIATION: Clemson University

ABSTRACTs:

1.  Minimal Sum Covers of Small Cyclic Groups

Mark Fitch*  and  Robert E. Jamison

   A subset S of an abelian group (A,+) is a sum cover provided every element x in A can be expressed in at least one way as a sum x = s+t where s and t are in S.   If s^t is also required, then S is a strict sum cover.  Sum covers sometimes provide a means to approximate solutions to certain geometric  problems.  For example, consider the problem of determining a minimal set of points in the plane over a finite field F which determines lines in all directions.  A small such set can be constructed using a sum cover for the multiplicative group of F.  In this paper, we report on a computer search to determine all minimum cardinality sum covers in finite cyclic groups of orders up to 54.

2.  Caratheodory Number of the Pfaltz Closure in King's Graphs

Robert E. Jamison and John Villalpando*

 John Pfaltz has suggested the following closure in graphs in connection with image processing and recognition.  Let G = (V,E) be a graph and S any set of vertices.  Form the closed neighborhood N[S] consisting of S and the neighbors of all of its points.  Delete the vertices of N[V\N[S]].  This yields a smoothing closure operator  S --> N[S]\ N[V\N[S]].  In this paper, we evaluate the classical convexity invariant, the Caratheodory number, for this closure in the case of the king's graph.  The king's graph has as vertices the squares of a rectangular chessboard with two squares adjacent if they constitute an admissible move of a king.

3.  2-Split Graphs

Edward Doyle* and David P. Jacobs

A graph G is 2-Split if its vertices can be partitioned into three sets K, I_1 and I_2 such that two conditions hold.  First K induces a clique and I_1 and I_2 are independent sets.  Second, there are no edges in G between K and I_2.  Any of the three sets may be empty.  We will describe a polynomial time O(n^{3}) recognition algorithm for 2-split graphs.

TITLE:     Average number of points on curves over finite fields
SPEAKER:     Dr. Andrew Granville
AFFILIATION: University of Georgia

ABSTRACT:

In this talk we discuss a natural problem that arose recently about the distribution of the number of points on curves, of given genus, over finite fields. We will see how elementary approaches can give us valuable information, but for more information we revert to consequences of important works of Deligne (the equidistribution theorem as a consequence
of his Lefschetz fixed point formula), Weyl (probability distributions for eigenvalues on classical groups), Katz and Sarnak (piecing these ideas together), Selberg (the trace formula and its applications), etc. So this'll be a talk using ideas from group theory, classical analysis and modular forms, finite fields, arithmetic geometry, probability theory and algebraic geometry.

We end up with, more-or-less, the answers we sought but with no clear elementary heuristic as to why they must be true.

Andrew Granville is the David C. Barrow Professor of Mathematics at the University of Georgia.  He was educated at Cambridge University and received his PhD from Queens University in Canada.  He is the author of more than 70 refereed publications in various areas of mathematics, including analytic and algebraic number theory and combinatorics.  He has been awarded the Ribenboim prize by the Canadian Mathematical Society (1999), the Hasse prize by the MAA (1995), was an invited speaker at the International Congress of Mathematicians in Zurich (1994), and from 1994-1999 was a Presidential Faculty Fellow.

TITLE:     Decomposition of polytopes and polynomials
SPEAKER:     Dr. Alan G. B. Lauder
AFFILIATION: Oxford University

ABSTRACT:

Given a polynomial in n variables over a field one may associate with it a convex polytope in n-dimensional space called its Newton polytope. This is done in such a way that if the original polynomial f factors as f = gh, then its Newton polytope N_{f} decomposes, in the sense of Minkowski, into the sum of N_{g} and N_{h}. Thus the study of the Minkowski decomposition of polytopes, as well as being of independent interest, has applications in polynomial factorisation. In this talk, after explaining exactly what ``Minkowski decomposition'' is, I will describe some joint work with Shuhong Gao on algorithms for decomposing polytopes and factoring polynomials.

TITLE:       The Geometry of Gaussian Elimination and the Rook's Pivoting Strategy*
SPEAKER:     Dr. George Poole
AFFILIATION: East Tennessee State University

ABSTRACT:

A geometric analysis of Gaussian elimination is presented to better understand several difficulties encountered when this algorithm is applied in a finite-precision environment (computers).  Based on this geometric analysis, a better understanding of Gaussian elimination (GE) is achieved which leads to a better understanding of the subject of scaling.  These new
insights also lead to a new a new pivoting strategy, Rook's Pivoting (RP), which encourages stability in the back-substitution phase of GE while controlling the growth of round-off error during the sweep-out.  In fact, Foster has already shown that RP, as with Complete Pivoting, cannot have exponential growth error.  Empirical evidence will be presented to show that RP produces computed solutions with consistently greater accuracy than Partial Pivoting, but with comparable costs.  That is, Rook's Pivoting is, on average, more accurate than Partial Pivoting, and the cost of implementing Rook's Pivoting in a scalar or serial environment is only about three times the cost of Partial Pivoting.  The theoretical proof establishing this fact is presented here, and is empirically confirmed in Foster's paper.

* Joint work with Larry Neal. On October 16, 1995, Larry Neal died after a nine-year, fiercely fought battle with cancer.  Larry Neal obtained his MS degree in Mathematics at Clemson in the late 60's before doing his Ph.D. in numerical analysis at the University of Southwestern Louisana.  Without his technical expertise, creative mind, and incomparable friendship,
this work could not have been completed. This work was sponsored in part by a grant from the East Tennessee State University Research Development Committee, #2-25417.

TITLE:       Life as a Non-Academic Mathematician
SPEAKER:     Dr. Clark T. Benson*
AFFILIATION: National Security Agency

ABSTRACT:

More and more graduate students in mathematics are considering jobs in industry or other non-academic positions as they finish their formal education. We will explore some of the differences between industrial and academic mathematics as well as describe some non-academic opportunities for employment at the National Security Agency, the nation's leading employer of mathematicians. We also will address the best preparation and attitudes necessary to be a successful applied mathematician.

*Clark Benson left academia after 25 years as a professor, the last 18 being at the University of Arizona. He has spent the last decade as a senior mathematician at the National Security Agency working on a variety of cryptologic problems.  Dr. Benson was named Research Scientist of the Year in 1992, and in 1997 was a co-winner of the Sir Peter Marychurch
award, given anually for the most significant cryptologic achievement in the United States and Britain.

TITLE:       Circulant Graphs
SPEAKER:     Dr. Gayla S. Domke
AFFILIATION: Georgia State University

ABSTRACT:

Set S be any subset of {1, 2, ..., n-1} such that S = -S mod n.  G = (V, E) is a circulant graph if V = {0, 1, 2, ..., n-1} and E = {ij | (i - j) mod n \in S}.  The adjacency matrix of this graph is the n x n matrix A(G) whose (i,j) entry is 1 if and only if ij \in E and is 0 otherwise.  Note that A(G) is a circulant matrix since the (i,j) entry equals the (i-1,j-1) entry (where subtraction is done mod n).  The rank of G is defined to be the rank of A(G).  We call G an r-circulant graph if |S| = r.

In this talk we will show how all disconnected r-circulant graphs are made up of connected r-circulant graphs.  We will also classify all connected 3-circulant and 4-circulant graphs as well as determine their ranks.

This talk will combine ideas from graph theory, abstract algebra, matrix theory and number theory.

This is joint work with George Davis and Charles Garner at Georgia State University.

TITLE:       Algebraic geometry codes and gap sets
SPEAKER:     Dr. Gretchen Matthews
AFFILIATION: University of Tennessee, Knoxville

ABSTRACT:

A primary goal of algebraic coding theory is to construct codes over finite fields for which the dimension and minimum distance are large with respect to the length.  The Reed-Solomon codes are a class of codes which are optimal in this sense.  However, these codes do not yield good asymptotic results as the length of a Reed-Solomon code is the size of
the field.  In 1980, V.D. Goppa realized that algebraic curves could be used to construct a large class of codes with more variable lengths.  These codes, called algebraic geometry codes or Goppa codes, are generalizations of Reed-Solomon codes.  An algebraic geometry code does not necessarily have maximum dimension and minimum distance for its
length, but Goppa did obtain bounds on these parameters.

One can investigate the parameters of algebraic geometry codes using algebraic properties of curves over finite fields.  In particular, we show how the gap set of an m-tuple of points on a curve may be used to construct codes with minimum distance larger than the Goppa lower bound.  Applying this construction, we see examples of codes defined using a
linear combination of two points that have better parameters than any code on the same curve defined using a multiple of a single point.