Aug 24	Professor J. D.  Key	Clemson University	Rigidity Theorems for Some Affine Resolvable Designs
Aug 31	Professor P. Dankelmann	University of Natal, Durban, South Africa	Aspects of Connectivity
Sep   7	Professor Robert E. Jamison	Clemson University	Transitive Edge Colorings and Sums of Singular Sets in Cyclic Groups
Sep 13	None		Clemson Mini-Confernce on Discrete Math.
Sep 21	Professor Robert E. Jamison	Clemson University	Affine Geometry and Reduced Cliques  inTransitively Edge-Colored Graphs
Sep 28	Professor Douglas R. Shier	Clemson University	Randomization, Majorization, and Algebraic Structures
Oct  5	Professor Renu Laskar	Clemson University	On Harmonious and related colorings of Graphs
Oct 12	Professor Neil Calkin	Clemson University	Tossing Coins with a Variable Bias
Oct 19	None		Fall Break
Oct 26	Professor Shuhong Gao	Clemson University	Computing Roots of Polynomials over Function Fields of Curves
Nov  2	Mr. Peng Ding	Clemson University	The dual codes from hyperplane designs
Nov  9	Professor David Peifer	The University of North Carolina at Asheville	An Introduction to Geometric Group Theory
Nov 16	Professor Jean E. Dunbar	Converse College	Path Partitions and Maximal (Maximum) $P_n$-free Subgraphs
Nov 23	Professor Mahesh C. Bhandari	Indian Institute of Technology, Kanpur, India	Z_4-Simplex Codes and Their Gray Images
Nov 30	Professor Joel Brawley	Clemson University	Involutory Matrices

TITLE:                      Rigidity Theorems for Some Affine Resolvable Designs
SPEAKER:               Professor J. D. Key
AFFILIATION:     Clemson University

ABSTRACT:

Designs that have the same parameters as those from finite projective or affine geometries are of interest as their comparison with the designs from the geometries can provide a basis for rigidity theorems for these designs and their codes. The codes from the geometries are generalized Reed-Muller codes, and a standing conjecture of Hamada asserts that these codes will have the smallest dimension amongst those from designs with the same parameters.

The affine resolvable 2-$(27,9,4)$ designs were classified recently by Lam and Tonchev; the parameters are those of the affine geometry design $AG_{3,2}(F_3)$ of points and planes in $AG_3(F_3)$. We use Lam and Tonchev's construction of the designs to examine the ternary codes of the designs and show, with the help of the computer language Magma, that each of the codes, apart from two, contains, amongst its constant weight-9 codewords, a copy of the ternary code of the affine geometry design $AG_{3,2}(F_3)$.  We also show how the ternary codes of the 68 designs and of their dual designs, together with properties of the automorphism groups of the designs, can be used to characterize the designs.

This is joint work with K. Mackenzie-Fleming.

TITLE:                     Aspects of Connectivity
SPEAKER:              Professor P. Dankelmann
AFFILIATION:     University of Natal, Durban, South Africa

ABSTRACT:

A graph G is connected, if between every two vertices u,v of G,  there is a path from u to v. Otherwise G is disconnected. The edge-connectivity of G, denoted by lambda(G), is the minimum  number of edges one has to remove from G to obtain a disconnected graph. Since it is always possible to disconnect a graph by deleting the edges incident with a particular vertex, we  have

    lambda(G) <= delta(G),

where delta(G) is the minimum degree of the vertices of G. In the first part of the talk we present various conditions on G that guarantee equality of lambda(G) and delta(G).  The second part of the talk deals with the vertex connectivity of G, defined as the minimum number of vertices whose removal renders G disconnected. We will also consider a variant of the vertex connectivity,
the average connectivity.
 

TITLE:                      Transitive Edge Colorings and Sums of Singular Sets in Cyclic Groups
SPEAKER:              Professor Robert E. Jamison
AFFILIATION:     Clemson University

ABSTRACT:

An edge coloring of a graph is transitive provided that whenever two incident edges share a color, the third edge of the triangle exists and also shares that color. The singularity graph of a finite ring  has the ring elements as vertices with edges joining pairs whose difference is not invertible.  In this paper we will examine the notion of transitive edge coloring as it relates to the structure of cliques in the singularity graph modulo an integer n.  We will characterize  the cliques when n has at most three prime factors and use this to show that the maximum number of distinct pairwise sums from such a clique is at most n - phi(n), where phi(n) denotes the Euler totient function.
 

TITLE:                     Affine Geometry and Reduced Cliques in Transitively Edge-Colored Graphs
SPEAKER:               Professor Robert E. Jamison
AFFILIATION:     Clemson University

ABSTRACT:

An edge coloring of a graph is transitive provided that whenever  two incident edges share a color, the third edge of the triangle exists and also shares that color. This talk will continue on the general theme of attempting to characterize or classify all possible cliques in transitively edge colored graphs. A reduction technique will be discussed which can be used to simplify the problem somewhat.  In particular,  I will show that there are only four possible types of reduced cliques  with three colors.

The slope patterns of affine geometries provide a large class of examples of reduced cliques.  This talk will also explore the construction of  new cliques from affine geometries by   1) relaxation (merging two or more parallel flats into a single class), and   2) extension (adding new points with a consistent coloring). As it turns out, applying these techniques leads directly to certain classical problems of discrete geometry -- namely, complete mappings, blocking sets, and spreads.

TITLE:                     Randomization, Majorization, and Algebraic Structures
SPEAKER:              Professor Douglas R. Shier
AFFILIATION:     Clemson University

ABSTRACT:

In a number of experimental situations, subjects are randomly allocated to treatment groups (e.g., those receiving a new drug and those receiving a placebo). Measurements are then made on the two groups to ascertain if there is in fact a statistically significant treatment effect. It turns out that the correct statistical model for this situation involves a certain  ``randomization distribution.'' Exact calculation of this distribution theoretically involves looking at all possible partitions of the original measurements into two appropriately-sized groups.

Since computing every possible partition is computationally wasteful, our objective is to devise a way of systematically enumerating such partitions starting from the ``tail'' of the randomization distribution. It turns out that there is an underlying algebraic structure that comes to our rescue: a partial order derived from the majorization of integer sequences. Spanning trees of the associated Hasse diagram come into play in designing an enumeration scheme.  Numerical computations are also presented to assess the effectiveness of this approach in practice.

The work reported here (with algebraic, computational, and statistical overtones) has been carried out jointly with Marie Coffin and Rick Jarvis.

TITLE:                    On Harmonious and related colorings of Graphs
SPEAKER:              Professor Renu Laskar
AFFILIATION:     Clemson University

ABSTRACT:

Coloring of a graph G = (V,E) plays an important role in the study of Graph Theory. Coloring problems arise in many contexts. We will study some recent developments of some coloring concepts such as line distinguishing, harmonious, pseudo harmonious, P-Q colorings of graphs, etc.

Joint work with Guantao Chen, Gayla Domke, Johan Hattingh, Steve Hedetniemi, Sandee Hedetniemi, Odile Favaron, Dieter Rautenbach.

TITLE:                     Tossing Coins with a Variable Bias
SPEAKER:              Professor Neil Calkin
AFFILIATION:     Clemson University

ABSTRACT:

We consider the following game.  You have n coins on a table:

    i) If n=0 then you lose

   ii) If n=1 then you win

  iii) If n>1 then you pick a random bias x in [0,1]  with distribution mu(x), and you toss all the coins with that bias (that is, the probability of any coin coming up heads is x, and of coming up tails is 1-x).

These are repeated until you either win or lose the game (with a new bias picked each round).

We consider the probability q_n of winning, given that you start with n coins, develop expressions for q_n, and as a corollary, obtain some (apparently new) inequalities for kth moments of probability distributions on [0,1].
 

TITLE:                     Computing Roots of Polynomials over Function Fields of Curves
SPEAKER:              Professor Shuhong Gao
AFFILIATION:     Clemson University

ABSTRACT:

Efficient algorithms for finding roots of (univariate) polynomials over function fields of curves are useful for list decoding of Reed-Solomon and algebraic-geometric codes. In the first half of the talk, we will focus on bivariate polynomials, i.e., polynomials over the coordinate ring of  an affine line; a Newton polygon method will be useful.  In the second half, we will give an algorithm for computing roots of polynomials over the function field of a nonsingular algebraic plane curve; the roots are limited to  the vector space of rational functions associated to a given divisor of the curve.

Joint work with M. Amin Shokrollahi (AT&T Bell Labs).

TITLE:                     The dual codes from hyperplane designs
SPEAKER:               Mr. Peng Ding
AFFILIATION:     Clemson University

ABSTRACT:

We investigate the minimum-weight codewords in the dual of the binary code generated by the incidence vectors of hyperplanes of an m-dimensional projective space over a finite field of even order. First we establish the geometric properties of the minimum-weight codewords, and then we  demonstrate the role of the minimum-weight codewords in the code.  Finally we present some open problems.

The talk will be presented in the language of finite geometry, linear algebra and group theory in such a way that people without a coding  theory background will be able to follow.

Joint work with Dr. J.D. Key.

TITLE:                    An Introduction to Geometric Group Theory
SPEAKER:              Professor David Peifer
AFFILIATION:    The University of North Carolina at Asheville

ABSTRACT:

In 1987, M. Gromov published an extensive paper defining a new type of group. He calls these groups hyperbolic. His definition is based on the geometry of the Cayley graph associated to the group. Shortly after, W. Thurston defined another new type of group he  calls automatic. Similar to Gromov's hyperbolic groups, automatic groups can be defined by geometric properties of their Cayley graphs. Over the last 12 years, the study of these new groups has lead to a new branch of infinite group theory, called Geometric Group Theory. I will present a brief introduction to some of the main topics in this area. The talk will be accessible to anyone who knows some basic group theory.

TITLE:                     Path Partitions and Maximal (Maximum) $P_n$-free Subgraphs
SPEAKER:              Professor Jean E. Dunbar
AFFILIATION:     Converse College

ABSTRACT:

The detour order of a graph G is defined to be the length of a longest path in G.  A partition (A,B) of the vertices of G is called
an (a,b)-partition if the induced graphs G[A] and G[B] have detour orders at most a and b, respectively.

The Path(ological) Partition Conjecture is the following:

Conjecture 1:  For any graph G, with detour order a + b, there exists an (a,b)-partition of its vertices.

A graph is called $P_n$-free if it has no paths of order n. We examine two stronger conjectures:

Conjecture 2:  Every graph G has a maximal $P_n$-free subgraph for each positive integer n.

Conjecture 3:  Let n be a positive integer smaller than the detour order of G. If M is a $P_n$-free subgraph of G with maximum number of vertices then deleting the vertices of M from G decreases the detour order of G by at least n.

We investigate the relationships among these conjectures and find classes of graphs for which the conjectures hold.

Joint work with Marietjie Frick (University of South Africa).

TITLE:                     Z_4-Simplex Codes and Their Gray Images
SPEAKER:              Professor Mahesh C. Bhandari
AFFILIATION:     Indian Institute of Technology, Kanpur, India

ABSTRACT:

We consider linear codes over Z_4, the ring of integers modulo 4. In 1994 Hammons et al showed that, under the Gray map, linear codes over Z_4 give nonlinear binary codes including the Kerdock, Preparata and Goethals codes.  The present talk gives a brief survey of  known results and determine such fundamental properties as 2-dimension, Hamming and Lee weight distributions, weight hierarchy, etc.

TITLE:                     Involutory Matrices
SPEAKER:              Professor Joel Brawley
AFFILIATION:     Clemson University

ABSTRACT:

An nxn matrix K over a field F is said to be involutory if and only if K^2 = I, where I is the identity matrix (or equivalently if and only if K^(-1) = K).  Such matrices have applications in classical cryptography.

In this talk, after a short discussion of cryptographic applications, we will summarize some known facts about involutory matrices including formulas (with derivations) for their number when F is a finite field. One of the cryptographic problems we discuss, a so-called two message problem, leads to the following question:  When is a given matrix A the product of two involutory matrices? We will answer this question as well as the related question: What is the subgroup of the general linear group generated by the involutory matrices?

Note: This talk involves joint work with Andrea McMakin who is writing a master's paper on involutory matrices.  It will be accessible to all students who have completed a matrix analysis course (e.g., Mth Sc 853); however, a brief review of the appropriate canonical form theory will be included to make it as self-contained as possible.