Algebra & Discrete Mathematics Seminar Fall 2003
Algebra & Discrete Mathematics Seminar Spring 2003
Algebra & Discrete Mathematics Seminar Fall 2002
Algebra & Discrete Mathematics Seminar Fall 1999-Spring 2002
TITLE: A computer/human Mastermind player using grids
SPEAKER: Wayne Goddard
AFFILIATION: Computer Science, Clemson University
ABSTRACT:
In Mastermind, there are two players, CodeBreaker and CodeSetter.
The CodeSetter creates a secret code of 4 colored pegs, each peg one of
6 colors. The CodeBreaker must deduce the secret code by asking a series
of questions, each itself a
candidate code. Previous work on the game includes mathematical
results providing bounds and asymptotics, and actual strategies using the
computer's number-crunching abilities.
A fundamental difficulty for a human CodeBreaker is to understand all
information revealed so far. In this talk we introduce a grid-based
representation and strategy that allow for quick assimilation of new information.
The idea is that one needs
two pieces of information: the color representation and where
each color goes. As a human player, the approach provides a good
player, and with practice, can be used very fast. As a computer player,
its importance is that the player can explain its progress.
TITLE: An effective primitive element theorem for
field extensions
SPEAKER: Joel Brawley
AFFILIATION: Clemson University
ABSTRACT:
If K is an finite extension field of a field F, say K = F(a1,a2,
...,an), then an element a in K is called primitive over F if
K = F(a). The well-known "Primitive Element Theorem" states that
if K is a finite separable extension of F, then K contains a primitive
element. In this talk, we take K = F(a1,a2,
...,an) to be a finite separable extension of F with [K:F] =
m, and we show that for any finite subset S of F of k elements, the number
of primitive elements a of the form a = c1a1+c2a2+...+cn
an , ci in S is at least k^n(1-(m-1)/k). As
a consequence, if the number of elements in F is at least m, this result
yields an alternate proof of the Primitive Element Theorem.
This is joint work with Shuhong Gao.
TITLE: Polynomial algebra and the design of experiments
SPEAKER: John Little
AFFILIATION: College of the Holy Cross
ABSTRACT:
We will discuss some applications of polynomial algebra in the design
of statistical experiments. The starting point is the representation
of a design D as the solution set of a collection of polynomial equations
in several variables. Statistical models are then represented by
polynomial functions on this collection of points. We will see how
this set-up allows one to answer questions such as: Is a given model identifiable
by a given design D, or a given subset F of D? and Given a class of models,
which subsets F of D are sufficient to identify such a model? We
will follow a recent paper by Caboara and Robbiano which applies Groebner
bases and a generalization called border bases to problems of this type.
The key ideas will be introduced by means of concrete examples and no previous
exposure to these ideas should be needed to understand the talk.
TITLE: Graphs of association schemes, related chessboard
graphs, and some graph parameters
SPEAKER: Renu Laskar
AFFILIATION: Clemson University
ABSTRACT:
The rook's graph, in which the vertices represent the n2 positions
of an n x n chessboard and in which vw is an edge if and only if a rook
at position v can attack a rook at position w, corresponds to the graph
of the L2 association scheme, the edges indicating the first associates
of the scheme. Similarly, graphs of other association schemes can
be thought of as chessboard-like graphs. Mathematicians and puzzle
enthusiasts have long enjoyed combinatorial problems on chessboards; in
this talk, similar combinatorial problems are considered on chessboard-like
graphs whose definitions are based upon association schemes.
This is joint work with Stephen Hedetniemi, Clemson University, and Charles Wallis, Western Carolina University.
TITLE: The chromatic index of graph decompositions
SPEAKER: Eric Mendelsohn
AFFILIATION: University of Toronto
ABSTRACT:
If G=(V',E) is a graph and H=(V,H) is a graph whose edges can be decomposed
into edge disjoint isomorphic copies of G, then we define a k-block colouring
of a G-decomposition of H to be an assignment of k colours to the copies
of G so that no two copies of G having a vertex in common have the same
colour. A G-decomposition of H has chromatic index chi'=k if it is
k block colourable and not k-1 block colourable. We investigate The Minimal
Chromatic Index Problem: Given H, and G determine min{chi'(D) | D
is a G-decomposition of H} and exhibit a D that achieves this minimum.
We illustrate some design theory techniques (G-resolvable designs and G-frames
and hill climbing) and use them to solve the Minimal Chromatic Index
Problem, for the cases where H the complete graph on n vertices. and G
is the path of length 2 and 3.
TITLE: The evolution of intelligent designs
SPEAKER: Eric Mendelsohn
AFFILIATION: University of Toronto
ABSTRACT:
The ability to determine through a small number of experiments which
drugs have harmful or beneficial effects when used together, the ability
receive pictures from outer space clearly, the ability to map the human
genome even though some results are inconsistent, the ability to use digital
cellphones, listen to cds or write to computer discs, all involve the use
mathematical objects (highly structured finite sets) called combinatorial
designs. In this lecture we will show the evolution of concept of
a combinatorial design from its beginnings as a problem involving the Russian
military in the 1700's in St Petersburg through to the present day.
Except for some college algebra used in the last few minutes of the talk,
no mathematics beyond high school is needed.
TITLE: Integer solutions of equations
SPEAKER: Dino Lorenzini
AFFILIATION: University of Georgia
ABSTRACT:
This talk will be an introduction to the topic of 'solutions to equations
f(x,y)= 0'. This field has a geometric flavor, since when one considers
the solutions to such an equation in the plane, one obtains a curve (i.e.,
when f(x,y)= x^2 + y^2 - 9, one gets a circle of radius 3). The field
also has an arithmetical flavor, since one may ask for all solutions (x,y)
with both x and y integers, or fractions.
The main results in the field obtained in the 20th century will be reviewed, and some specific results obtained jointly with T. Tucker for Thue equations will be discussed.
TITLE: Non-intersecting arithmetic progressions
SPEAKER: Ernie Croot
AFFILIATION: Georgia Institute of Technology
ABSTRACT:
Suppose one has a set of arithmetic progressions a_i mod q_i, i=1,...,k,
where the q_i's are all distinct and \leq x. One says that such a
system is non-intersecting if no pair of such progressions has an integer
in common. For example, the progressions 1 mod 2 and 2 mod 4 are
non-intersecting, because the first progressions only contains odd numbers,
while the second only contains even numbers.
Erdos had asked how many such (non-intersecting) progressions one can have (with the q_i's all \leq x), and he and Szemeredi gave an ingenious construction of a set of {x/exp(c log^{1/2+o(1)} x)} such progressions; and, they proved that one cannot get any more than x/log^A x (for any A 0, there exists x_0 so that if x x_0, then there can be at most x/log^A x non-intersecting progressions with q_i \leq x) of them.
In this talk, I will discuss an improvement of this result, which shows that if k = k(x) is the maximum number of such progressions possible, then {x/exp(c_1(log x log log x)^{1/2})}<k<{x/exp(c_2(log x log log x)^{1/2})}, for constants c_1, c_2 0.
TITLE: Improving conformational searches by geometric screening
SPEAKER: Ming Zhang
AFFILIATION: University of Texas M. D. Anderson Cancer
Center
ABSTRACT:
Conformational search in molecular docking is an active research topic
with a wide range of applications such as computer-assisted drug design,
structural regulation and molecular recognition. The goal of conformational
searches is to find favorable conformations of ligand molecules that bind
with receptor molecules successfully so that the ligand-receptor complexes
remain stable. Usually some feature atoms of a ligand have their
target positions specified and the conformations of the ligand that meet
the target constraints are to be computed. Current conformational
search methods are mostly energy oriented. That is, a large number
of conformations are generated and the binding energy is examined. We add
a geometric screening phase before an energy minimization procedure to
improve conformational searches: only those conformations satisfying
the geometric constraints will be prompted for energy calculation.
The number of conformations to be examined can then be drastically reduced
from millions (or higher) to thousands (or lower).
TITLE: Algebra and the legacy of Oliver Heaviside
SPEAKER: Jason Huffman
AFFILIATION: Georgia College & State University
ABSTRACT:
Oliver Heaviside was a brilliant, self-trained thinker in late 19th-century
England whose unorthodox, but practical, approach to mathematics won him
fame with engineers and ignominy with professional mathematicians.
His innovative techniques in the theory of electric circuits and telegraphy
marked the dawn of a new era in analysis and set the stage for the theory
of generalized functions. However, Heaviside's turbulent career was
fraught with political battles, academic disagreements, and public posturing.
During his lifetime, Heaviside never felt that he achieved the recognition
that he deserved. Part of the reason for this lack of public acceptance
was the absence of mathematical rigor in Heaviside's work. A rigorous
mathematical setting was finally provided after Heaviside's death,
when many of his methods were justified by the Polish mathematician Jan
Mikusinski.
In this presentation, we examine the history of both Heaviside and Mikusinski and explore the mathematical connection between these two accomplished men. We shall find that their personalities, their philosophies on research, and even their views on life were diametrically opposed. Yet their mathematics inexorably links them together, and it provides us with a view of one of the more controvesial episodes in recent mathematical history. We shall see the brilliance of Mikusinski's approach, whereby several problematic ideas from analysis are made rigorous and tractable by placing them in an algebraic setting. The operational calculus which follows has become a vitally important tool for engineers and applied mathematicians. Finally, we shall trace the lineage of this theory to the present day, whereby the author has extended some of Mikusinski's work via a non-commutative version of the operational calculus and the algebraic solutions of certain Volterra integral and integro-differential equations.
TITLE: Unit points induced by fields
SPEAKER: Arthur Sherk
AFFILIATION: University of Toronto
ABSTRACT:
Let K be a cubic extension of a field F. Then K is a vector space
of dimension 3 over F, and therefore is an affine 3-space. The presence
of the norm mapping from K to F introduces a "metric" to the geometry,
and so K can be thought of as a 3-dimensional metric space. In particular
the points {U} of norm 1 form a surface, with properties very different
from those of the unit sphere, its analog in Euclidean 3-space.
Let q be any prime power. Taking F to be GF(q), we examine some properties of {U}. In the process, we develop a relatively efficient way of generating unit points for any prime power q.
TITLE: An introduction to distance-regular graphs
SPEAKER: Mark MacLean
AFFILIATION: University of North Carolina - Asheville
ABSTRACT:
The study of symmetry and regularity has been a focus of mathematics
since at least the age of the five platonic solids. Distance-regular
graphs provide a nice generalization of the platonic solids, and they're
a much more recent example of mathematical objects possessing a high degree
of symmetry. In this talk, we'll introduce the subject of distance-regular
graphs and look at how they are studied using techniques from algebra.
TITLE: Coding theory and the Cayley-Bacharach Theorem
SPEAKER: Leah Gold
AFFILIATION: Texas A&M University
ABSTRACT:
We will start out with some basics of coding theory and the definition
of an evaluation code. The question of how well such a code performs
when it comes to detecting and correcting errors is answered by a quantity
known as the minimal distance of the code. For a particular type
of evaluation code J. Hansen used cohomological methods to find a lower
bound for this minimal distance. We will explore a classical theorem
of algebraic geometry known as the Cayley-Bacharach Theorem, and see how
a modern version of this theorem may be used to shorten and generalize
Hansen's proof.
It will be assumed that the audience is familiar with topics from first course in abstract algebra (rings, fields). Definitions from coding theory, homological algebra, and algebraic geometry will be introduced as needed. This result is joint work with John Little (College of the Holy Cross) and Hal Schenck (Texas A&M University).
TITLE: Think positive, you might be a square!
SPEAKER: Victoria Powers
AFFILIATION: Emory University
ABSTRACT:
Given a real polynomial f in n variables of degree m, we say f is
positive semidefinite (psd) if f takes only non-negative values everywhere
in R^n; f is a sum of squares (sos) if f can be written as a sum of squares
of real polynomials. It's easy to see that f sos implies f psd and
it was well-known by the middle of the 19th century that if n = 1 or m
= 2, the converse is true. In 1888, David Hilbert showed that f psd
implies f sos for (n,m) = (2,4) and that for all other (n,m) there are
psd f which are not sos. Hilbert's preoccupation with psd and sos
polynomials was a catalyst for modern real algebra.
Recently, there has been a lot of interest in questions involving sos and psd polynomials because of applications in engineering and other areas. In this talk we will look at psd and sos polynomials, give some history and background, and discuss recent results and applications, in particular to optimization of polynomial functions.