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.
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.
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.
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.
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)).
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.
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 .
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 ofG
by subtrees of a spanning tree of G.
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.