Algebra & Discrete Math Seminar

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 |

August 24, 1999

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.

August 31, 1999

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.

September 7, 1999

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.

September 21, 1999

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.

September 28, 1999

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.

October 5, 1999

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.

October 12, 1999

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].

October 26, 1999

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).

November 2, 1999

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.

November 9, 1999

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.

November 16, 1999

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).

November 23, 1999

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.

November 30, 1999

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.

Back to ADM Seminar Page