Algebra & Discrete Math Seminar

August 30, 2001

TITLE: **Some
binary codes with automorphism group containing the symplectic group of
odd characteristic**

SPEAKER: Professor J. D. Key

AFFILIATION: Clemson University

ABSTRACT:

The finite symplectic groups are groups of isometries that preserve an alternating bilinear form defined on a vector space V(2m,q). They have a natural primitive rank-3 action on the points of the projective space of dimension 2m-1, thereby defining strongly regular graphs. When q is a power of an odd prime, and m > 1, this action gives rise to self-orthogonal binary codes through the span over GF(2) of an adjacency matrix for the graph. The symplectic geometry can be used to establish important properties of these codes, in particular some bounds for the minimum weight, and the nature of some classes of codewords. This talk will describe how the codes are constructed, and how these and other coding properties can be deduced from the symplectic geometry.

This is joint work with J. Moori and B. Rodrigues of the University of Natal.

September 6, 2001

TITLE: **The
fragmentability of d-regular graphs**

SPEAKER: Professor Neil Calkin

AFFILIATION: Clemson University

ABSTRACT:

In a recent paper, Edwards and Farr introduced the concept of fragmentability of a class of graphs: this measures how vulnerable the graphs in the class are to being broken into small components by removal of a set of vertices. For the class of graphs of maximum degree d they obtain the bounds

1/2 - 1/(2d-2) < c < 1 - 3/(d+1)

for the proportion c of the vertices needed to be removed to fragment a graph in the class. In this talk we will consider the fragmentability of the class of random d-regular graphs, and hence obtain better lower bounds: in particular, we show that c approaches 1 as d goes to infinity.

September 13, 2001

TITLE: **Recent
progress on the Lang-Trotter conjecture**

SPEAKER: Professor Kevin James

AFFILIATION: Clemson University

ABSTRACT:

Let E: y^2 = x^3 +Ax +B be an elliptic curve over the rational number field. As usual we will let a_p = p+1 - #E(F_p). Lang and Trotter have conjectured that, when x is large,

#{p < x : a_p = r} is asymtopically C(E,r) sqrt{x}/log(x)

for some constant C(E,r). Indeed, this conjecture has been proved to
hold in an average sense when one averages over all elliptic curves.
In this talk we will discuss similar average results over the somewhat
finer sets of elliptic curves with a prescribed torsion subgroup.

September 20, 2001

TITLE: **Roman
Domination in Graphs**

SPEAKER: Professor Steve Hedetniemi

AFFILIATION: Computer Science, Clemson University

ABSTRACT:

Around 250 AD, Emperor Constantine issued a decree concerning the deployment of Roman Legions at various outposts of the Roman Empire. The rules of deployment prohibited a legion from leaving one location to defend a nearby one, if in doing so, the originating location was left undefended. Thus, two legions would typically be stationed at a given location, thereby permitting one of the two legions to be used to help defend a neighboring one.

This suggests a constrained discrete optimization problem, in which one attempts to minimize the number of legions required to defend the Empire. We model this as a graph theory problem involving the concept of a dominating set, and we study the mathematical and algorithmic properties of this type of domination.

This reflects joint work with Paul Dreyer, Rand Corporation; E. J.
Cockayne, University of Victoria, British Columbia, Canada; Michael Henning,
University of Natal, Pietermaritzburg, South Africa; Alice McRae,
Appalachian State University; and Sandee

Hedetniemi, Department of Computer Science.

September 27, 2001

TITLE: **A
Slowly Converging Sequence**

SPEAKER: Jeffrey Farr

AFFILIATION: Clemson University

ABSTRACT:

We consider a sequence, p_n, defined by

p_0 = 0; p_1 = 1; p_n = 1/2 p_{n/3} + 1/2 p_{n/2}, for n >=2,

where n/3 and n/2 rounded down to integers. This is a simple example of a sequence in which the n-th term is a weighted average of the preceding terms and the weights for p_n are heavily concentrated at two previous elements in the sequence. It is known that if the weights for the n-th term of a sequence are sharply concentrated around a single previous element and if the sequence appears to be oscillating at the beginning, then the sequence will continue to oscillate, hence it will not converge. Although the double-biased sequence which we consider appears to be oscillating at the beginning, we show that it does, in fact, slowly converge. Specifically, we prove that

p_n --> 2/(1 + log_2(3)).

October 4, 2001

TITLE: **Intersection
Representation of a Chordal Graph**
**
Representation by Subtrees of a Spanning Tree**

SPEAKER: Professor Renu Laskar

AFFILIATION: Clemson University

ABSTRACT:

For a vertex v of a graph G=(V,E), the closed neighborhood N[v] is the set consisting of v and all vertices adjacent to v. A vertex v is simplicial if N[v] is complete. An ordering \phi of the vertex set V(G), \phi: v_1, v_2,..., v_n is a perfect elimination ordering (PEO), if for each i, v_i is a simplicial vertex in the subgraph induced by {v_i, v_{i+1},..., v_n}. A graph G is chordal if every cycle C_k, k>3, has a chord. Two well known characterizations of chordal graphs are as follows:

** Theorem 1** (Gavril, Walter) A graph G is chordal if and
only if it is the intersection graph of a family of subtrees of a tree.

** Theorem 2**. (Dirac, Fulkerson & Gross) A graph
G is chordal if and only if it has a PEO.

The power and usefulness of chordal graphs arise largely from these two properties. For example, Barrett, Johnson, and Lundquist used properties of clique trees to derive formulae for matrix determinants. In a statistical application, Darroch, Lauritzen, and Speed used the clique tree of a chordal graph to simplify contingency computations. Perfect elimination orders were observed by Rose to yield a pivot order which avoids fill-in in solving a linear system by Gaussian elimination. In the literature relative to Theorem 1, the host trees that arise are usually constructed from the set of maximal cliques of the underlying chordal graph. The construction of these clique trees, as they are called,is not canonical and can be rather complicated. By constrast, the host trees constructed in this note are spanning trees of the underlying chordal graph G and arise in a natural way from a given PEO of G. More specifically, we prove the following result:

**Theorem**. Let G be a connected chordal graph, and
let \alpha be any PEO of G. Then \alpha determines a spanning tree T(G,\alpha)
of G and an intersection representation of G by subtrees of T(G,\alpha).

Joint work with Robert Jamison.

October 11, 2001

TITLE: **Some
mathematical aspects of dynamics of 2+1 gravity with applications
to natural sciences**

SPEAKER: Professor Arkady Kholodenko

AFFILIATION: Chemistry, Clemson University

ABSTRACT:

In my talk I discuss applications of Nielson-Thurston theory of surface
homeomorphisms (for which Wiliam Thurston was awarded the Fields medal)
to dynamics of 2+1 gravity, liquid crystals, etc.

**Note**: Professor Kholodenko's recent papers are available online
.

October 18, 2001

TITLE: **Decomposition
Schemes for Computing the Independence Polynomial of a Graph**

SPEAKER: Professor Robert E. Jamison

AFFILIATION: Clemson University

ABSTRACT:

The independence polynomial of a graph *G* is the generating function
for the independent subsets. That is, it is a polynomial in which
the coefficient of* x^k* is the number of independent sets with *k*
vertices. A graph *G* is chordal iff it does not contain an
induced cycle of length 4 or more. The goal of this paper is to show that
among all graphs, chordal graphs have the most easily computed independence
polynomials.

In any graph *G*, the independence polynomial can be computed recursively
by deleting vertices and their neighborhoods. This process leads
to a family of subgraphs of *G* which will be called a *decomposition
scheme* for *G*. The computation of the independence polynomial
is most efficient when the scheme is small. It will be shown that
the number of sets in a decomposition scheme is always at least the order
of the graph *G*. Moreover, this bound is achieved precisely when
*G*
is chordal.

The structure of minimum length decomposition schemes in a chordal graph
*G*
turns out to be directly related to intersection representations of*G*
by subtrees of a spanning tree of *G*.

October 25, 2001

TITLE: **Random
Krylov spaces over finite fields**

SPEAKER: Professor Shuhong Gao

AFFILIATION: Clemson University

ABSTRACT:

Solving linear systems is important in many scientific applications. Iterative methods for solving linear systems are based on Krylov subspaces generated by a fixed linear mapping and a set of elements in a vector space. We consider the probability that a random Krylov subspace in a vector space over a finite field equals the whole space itself. We present an exact formula for this probability, and from it we derive good lower bounds that approach 1 exponentially fast as the size of the set increases.

Joint work with Richard P. Brent and Alan G. B. Lauder of Oxford University.

Note that the talk should be accessible to students familiar with linear algebra.

TITLE: **Paired
Two-Sample Tests: An Algebraic Perspective**

SPEAKER: Professor Douglas Shier

AFFILIATION: Clemson University

ABSTRACT:

In this talk we discuss the classic two-sample test in which controls and treatments are assigned to each of a pair of items, with the object being to determine if the treatment makes a statistically significant difference. In the present context, items of a pair are randomly assigned to either group, giving rise to a distribution-free test based on a certain test statistic.

We view the problem of generating the distribution of this test statistic
in algebraic terms. A certain (distributive) lattice arises and an
algorithm for generating the required distribution is based on studying
the Hasse diagram of this lattice. In particular a certain (rooted) spanning
tree of the Hasse diagram is used to guide the generation algorithm. A
variant that can also be handled is

to determine the probability, under the randomization assumption, of
obtaining a value of the test statistic at least as extreme as that observed.

Several computational issues are also discussed, and it turns out that
a variant of Dijkstra's shortest path algorithm can be adapted

to the present problem.

In summary, we see an interesting interaction in this talk between statistics,
algebra, operations research, and computing.

TITLE: **The
Irreducibility of Classical Polynomials and their Generalizations**

SPEAKER: Professor Michael Filaseta

AFFILIATION: University of South Carolina

ABSTRACT:

This talk will center around formulating old and recent results on the irreducibility of classical polynomials over the rationals. Some emphasis will be placed on making connections with the distribution of primes, diophantine equations, combinatorics, inverse Galois theory, and applications to wavelets and dynamical systems. The talk is intended for a general audience.

TITLE: **Isomorphic
Factorizations of Trees: Current Research**

SPEAKER: Professors Robert E. Jamison and Gary E. Stevens

AFFILIATION: Clemson University and Hartwick College

ABSTRACT:

An isomorphic factorization of a graph is a partitioning (coloring) of the edge set so that the subgraphs generated by the color classes are all isomorphic. If there are k colors used to accomplish this then we say that the graph is k-splittable. Determining whether or not a graph is k-splittable is an NP-Complete problem and remains so even when restricted to trees. Work has been done to specify subclasses of graphs and trees which are k-splittable and our work continues to search for such classes. In this seminar we will discuss some of the history that led to our joint research in this area and present some of the results we have obtained and other results we are working on.

TITLE: **
Long Cycles in 3-Connected Graphs**

SPEAKER: Professor Guantao Chen

AFFILIATION: Georgia State University

ABSTRACT:

In 1963, Moon and Moser conjectured that if *G* is a 3-connected
planar graph on *n* vertices, then *G* contains a cycle of length
at least O(* n *^{log 3 2 }). In a joint
work with Yu, we proved the conjecture. In this talk, we will discuss the
proof and the following conjecture of Robin Thomas: For any positive
integer *t > 2*, there exist positive real numbers *alpha* and
*beta *such that every 3-connected graph *G* without *K_{3,t}*
as a minor contains a cycle of length at least *alpha n^{beta}*, where
*n* is the number of vertices in *G*.

Back to ADM Seminar Page