Fall 2001
Algebra & Discrete Math Seminar
Time: Thursday 3:30pm
Room: Martin Hall M102

Aug 23  None Fall Semester just started yesterday!
Aug 30 J. D. Key Clemson University Some binary codes with automorphism group containing the symplectic group of odd characteristic
Sep   6 Neil Calkin Clemson University The fragmentability of d-regular graphs
Sep 13 Kevin James Clemson University Recent progress on the Lang-Trotter conjecture
Sep 20 Steve Hedetniemi CS, Clemson University Roman Domination in Graphs
Sep 27 Jeff Farr Clemson University A Slowly Converging Sequence
Oct  4 Renu Laskar Clemson University Intersection Representation of a Chordal Graph
Representation by Subtrees of a Spanning Tree
Oct 11 Arkady Kholodenko Chemistry, Clemson University Some mathematical aspects of dynamics of 2+1 gravity with applications to natural sciences
Oct 18   Robert  Jamison Clemson University Decomposition Schemes for Computing the Independence Polynomial of a Graph
Oct 25 Shuhong Gao Clemson University Random Krylov spaces over finite fields
Nov  1 Douglas Shier Clemson University Paired Two-Sample Tests: An Algebraic Perspective
Nov  8 None Clemson Mini-Conference on Discrete Mathematics.
Nov 16 Michael Filaseta University of South Carolina The Irreducibility of Classical Polynomials and their Generalizations
Nov 22 None Thanksgiving Holidays  (Nov 21--23)
Nov 29  Robert E. Jamison and Gary E. Stevens Clemson University and Hartwick College Isomorphic Factorizations of Trees: Current Research
Dec   6   Guantao Chen Georgia State University Long Cycles in 3-Connected Graphs

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


      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


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


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


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


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


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


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


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 ofG 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


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.

November 1, 2001

 TITLE:          Paired Two-Sample Tests: An Algebraic Perspective

SPEAKER:              Professor Douglas Shier

AFFILIATION:     Clemson University


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.

November 16, 2001

 TITLE:          The Irreducibility of Classical Polynomials and their Generalizations

SPEAKER:              Professor Michael Filaseta

AFFILIATION:    University of South Carolina


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.

November  29, 2001

 TITLE:          Isomorphic Factorizations of Trees: Current Research

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

AFFILIATION:     Clemson University and Hartwick College


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.

December 6, 2001

 TITLE:             Long Cycles in 3-Connected Graphs

SPEAKER:              Professor Guantao Chen

AFFILIATION:     Georgia State University


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