Algebra & Discrete Mathematics Seminar Spring 2003
Algebra & Discrete Mathematics Seminar Fall 2002
Algebra & Discrete Mathematics Seminar Fall 1999-Spring 2002
TITLE: Direction trees in centered polygons
SPEAKER: Robert E. Jamison
AFFILIATION: Clemson University
ABSTRACT:
A direction tree on a finite set of points X in the real plane R^2
is a tree whose vertices are the points of X and whose edges all have different
slopes, where the slope of an edge is the slope of the line passing through
its endpoints. One consequence of Ungar's celebrated result that
n noncollinear points determine at least n-1 slopes is that every noncollinear
set X has a direction tree. This paper is an investigation of the
restrictions on isomorphism types of direction trees for X where X = P_0(2k)
is the regular 2k-gon together with its center. The technique is
to reformulate the existence of a given tree T as a direction tree of P_0(2k)
into a labeling problem for the tree T.
A caterpillar is a tree from which the removal of all endnodes leaves a path, called the spine of the caterpillar. C[r,s] [resp., C[r,0,s]] denotes a caterpillar with a spine of two [resp., three] nodes with r and s leaves at the ends [resp., and no leaves in the middle]. We show that all caterpillars are direction trees of regular polygons, and present necessary and sufficient conditions, which depend on the number theoretic properties of r,s, and k, for C[r,s] and C[r,0,s] to be direction trees of P_0(2k).
TITLE: Groebner bases and fibre strutures
SPEAKER: Shuhong Gao
AFFILIATION: Clemson University
ABSTRACT:
Classical elimination theory deals mainly with when partial solutions
can be extended to complete solutions for a polynomial system. We
ask whether it is possible to predict the exact number solutions of a system
without actually solving it. In this talk, we present some relationships
between certain Groebner bases and the fibre structures of the solution
variety for a polynomial system that defines a 0-dimensional radical ideal.
From the Groebner basis we can read out immediately information about the
numbers of extensions of partial solutions, and we can decompose the system
into smaller systems that are easier to solve.
This is joint work with Virginia M. Rodrigues (PUCRS, Brazil) and Jeffrey Stroomer (Xilinx, Inc.).
TITLE: On some coloring concepts of graph theory
SPEAKER: Renu Laskar
AFFILIATION: Clemson University
ABSTRACT:
Graph coloring theory has a central position in discrete mathematics.
It appears in many places with seemingly no or little connection to coloring.
Graph coloring theory is of interest for its applications. It deals
with the fundamental problem of partitioning a set of objects into classes,according
to some rules. Time tabling, sequencing, and scheduling problems,
in their many forms, are basically of this nature. We intend to discuss
several coloring concepts including complete, harmonious, Grundy , partial
Grundy, fall coloring, distance coloring, etc. We will state some
open problems in these areas.
Many, many people have been working in these areas.
TITLE: Potentially graphic sequences - the other extremal
problem
SPEAKER: Ron Gould
AFFILIATION: Emory University
ABSTRACT:
Consider the following variation of the classic Turan-type extremal
problem. Let $\pi$ be an n-element graphical sequence, and $\sigma(\pi)$
be the sum of the terms in $\pi$. Let G be a graph. The problem
is to determine the smallest m such that any n-term graphical sequence
$\pi$, having $\sigma(\pi) \geq m$, has some realization containing G as
a subgraph. Here we present the (brief and still developing) history of
this problem.
Note that this problem varies from the Turan problem which requires all realizations of such sequences to contain G.
We also develop a more general problem by considering other properties. That is, we say S is potentially P-graphic, for some graph property P, if some realization G of S has property P. We also briefly survey several results of this type.
TITLE: Tackling two approximation problems in polynomial algebra
using Ruppert's theorem
SPEAKER: John May
AFFILIATION: North Carolina State University
ABSTRACT:
There are many problems in linear algebra that can be posed as approximation
problems. One example is the following: given an overdetermined
linear system A x = b, find the nearest (in the matrix two norm sense)
matrix to A which gives a consistent system. The solution to this
problem is just least-squares. Many problems in polynomial algebra can
also be considered this way.
We will consider the problem: given an irreducible multivariate polynomial,
find the closest factorizable polynomial. The problem is certainly
decidable, though currently there is no known polynomial time algorithm
to find the closest factorizable polynomial. There are several algorithms
that can find nearby factorizable polynomials in the case that a polynomial
is "nearly" factorizable. We present the other side of this problem
as first studied by Nagasaka: given an irreducible polynomial,
find a "good" lower bound on the distance to the closest factorizable
polynomial. Such good lower bounds allow one to declare certain polynomials
"approximately irreducible", and also helps measure how well approximate
factoring algorithms are doing.
One of the main tools in finding lower bounds is the curve irreducibility test discovered by Ruppert in the mid-1980's. His test reduces checking irreducibility of bivariate polynomials to testing the rank of a linear system. By further using the theory of low rank approximation from numerical linear algebra, we can find a lower bound on the distance to the nearest reducible polynomial. Our techniques can find the a lower bound for several coefficient norms. There is also hope that Shuhong Gao's factoring algorithm, which is based on Ruppert's theorem as well, may lead to a better method to find nearby factorizable polynomials.
Another approximation problem is as follows: given a univariate polynomial that does not have any (functional) decomposition factors, find the closest polynomial of the same degree that does decompose. That is, given f(x), find polynomials g(x) and h(x) so that g(h(x)) is as close to f(x) as possible. The functional decomposition problem can be reduced to the bivariate factorization problem. We will use this reduction to find a lower bound on the distance to the nearest decomposable polynomial.
TITLE: Partial zeta-functions and continued fractions
SPEAKER: Brett Tangedal
AFFILIATION: College of Charleston
ABSTRACT:
First derivatives of partial zeta-functions at s=0 play a crucial role
in Stark's conjecture. We will compare the computation of these first
derivatives over the rational number field with the computation over a
real quadratic number field. The computation over a real quadratic number
field is typically done without an appeal to continued fractions but we'll
discuss the algorithmic advantages of employing continued fractions.
TITLE: Clique hypergraphs of perfect graphs
SPEAKER: Dwight Duffus
AFFILIATION: Emory University
ABSTRACT:
Given a graph G = (V, E), the clique hypergraph of G is the hypergraph
H(G) = (V, E) where E = { K \subseteq E : K is a maximal clique of G}.
A k-coloring of any hypergraph H = (V, E) is an assignment of at most k
colors to V so that all non-singleton edges are assigned at least two colors.
The chromatic number \chi(H) is the least k for which a k-coloring exists.
In considering problems involving maximal antichains of finite partial orders [that is, maximal cliques in co-comparability graphs], Duffus, Sands, Sauer and Woodrow were led to ask about \chi(H(G))for co-comparability graphs G and wondered if this was bounded for the [much larger] collection of perfect graphs. Jensen and Toft upgraded the question to a problem.
Both comparability graphs and chordal graphs have 2-chromatic clique hypergraphs. Duffus, Kierstead and Trotter proved that for all co-comparability graphs G, \chi(H(G)) \le 3. Recently, Basco, Gravier, Gyarfas, Preissmann and Sebo showed that many families of perfect graphs have 3-chromatic clique hypergraphs. In this talk some of the arguments establishing these results are presented.
TITLE: Modular representations on Riemann-Roch spaces: computational
aspects
SPEAKER: David Joyner
AFFILIATION: US Naval Academy
ABSTRACT:
Let X be a smooth projective variety over an algebraically closed field
F and let G be a finite subgroup of automorphisms of X over F. If D is
a divisor of X which G leaves stable then G acts on the Riemann-Roch space
L(D). We answer the following questions in some cases.
1. Can any representation of G arise as an irreducible subrepresentation
of L(D) for some such D?
2. Is there an explicitly computable formula for the multiplicity of
a given irreducible representation of G in L(D)?
Note that this last question is tantamount to asking for a formula
for the trace of the representation of G on L(D). Such a formula
would generalize the Eichler trace formula.
TITLE: Value sets of polynomials over finite fields
SPEAKER: Gary Mullen
AFFILIATION: Pennsylvania State University
ABSTRACT:
Let F_q denote the finite field of order q. For a polynomial f over
F_q, let V_f ={f(a) : a \in F_q} denote the value set of f. We will
discuss a variety of problems and results concerning the cardinality of
the value set of a polynomial and present some joint work with Pinaki Das
which improves the best lower bound for the value set of a polynomial f
over F_q. Polynomials whose value set has maximal cardinality q are
called permutation polynomials. We will also discuss some results
related to permutation polynomials over finite fields along with some of
their applications.
TITLE: Sets of paritally orthogonal latin squares and projective
planes
SPEAKER: Gary Mullen
AFFILIATION: Pennsylvania State University
ABSTRACT:
We investigate the construction of sets of latin squares of a given
non-prime power order q which are as close as possible to being mutually
orthogonal sets. Using uniform cyclic neofields, for any even
q>2 we are able to construct q-1 latin squares of order q with the property
that, when we juxtapose any two of them, we obtain 5q-4 distinct ordered
pairs. More precisely, we obtain 4q-3 ordered pairs that occur exactly
once, q-1 pairs that occur exactly q-3 times, and q^2-5q+4 pairs that do
not occur.
Thus for example in the case when q=6 and there is not even a pair of orthogonal latin squares of order 6, we are able to construct 5 latin squares of order 6 so that when any two of them are juxtaposed, we obtain 26 distinct ordered pairs. And when q=10, using a uniform cyclic neofield we are able to construct 9 latin squares of order 10 with the property that when any two of them are juxtaposed we obtain 46 distinct ordered pairs.
It is conjectured, and very likely true, that D-neofields exist for any finite order q except for q=2,6. In cases where a D-neofield exists, one can do even better. For example when q=10, we can construct 9 latin squares of order 10 so that of the total possible \binom {9} {2} 10^2 =3600 possible ordered pairs in a complete set of 9 MOLS of order 10, we obtain 2952 distinct ordered pairs. This represents 82% of the total possible pairs in a complete set.
This is joint work with A. D. Keedwell (University of Surrey).
TITLE: Generic Cohen-Macaulay monomial ideals
SPEAKER: Abdul Jarrah
AFFILIATION: East Tennessee State University
ABSTRACT:
A monomial ideal in a polynomial ring is generic if whenever some variable
appears to the same degree in two different minimal generators, then there
is a third generator that divides their least common multiple properly
in all occurring variables. In 2000, Miller, Sturmfels and Yanagawa
proposed the problem to characterize those simplicial complexes whose Stanley-Reisner
ideal appears as the radical of generic monomial ideal which is Cohen-Macaulay.
In this talk, I construct generic Cohen-Macaulay ideals corresponding to
matroid complexes, shifted complexes and tree complexes.
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: Recent results on total domination in graphs
SPEAKER: Michael Henning
AFFILIATION: University of Natal
ABSTRACT:
A set S of vertices in a graph G without isolated vertices is a total
dominating set of G if every vertex of G is adjacent to a vertex in S.
The total domination number of G is the minimum cardinality of a total
dominating set in G. In this talk, we discuss recent results on total
domination in graphs.
TITLE: Quantum amplitude amplification
SPEAKER: Michele Mosca
AFFILIATION: University of Waterloo
ABSTRACT:
Quantum computers are devices that allow us to exploit the quantum
mechanical features of physical systems. One important problem that
can be solved more efficiently by quantum means is searching for a solution
to f(x)=1, where f isa "black-box" function from {0,1}^n - {0,1}.
The underlying tool is quantum amplitude amplification which uses O(\sqrt{N})
evaluations of f, where N=2^n. I will first describe this algorithm.
Now suppose that we are only able to compute f(x) with bounded error probability. I will describe a quantum algorithm that evaluates f(x) a number of times in O(\sqrt{N}) and with high probability finds a solution to f(x)=1 (if such an input exists). This shows that it is not necessary to first significantly reduce the error probability in computing f(x) to O(1/\poly(N)) (which would require O(\sqrt{N}\log N) evaluations of f in total). Our technique is a recursive interleaving of amplitude amplification and error-reduction, and may be of more general interest. Essentially, it shows that quantum amplitude amplification can be made to work also with a bounded-error verifier.
I will also briefly discuss the application of amplitude amplification to making quantum algorithms exact.
This is joint work with Peter Hoyer and Ronald de Wolf.