Tuesday, November 23, 2004
| Title |
The Association Scheme and its Bose-Mesner algebra |
| Speaker |
Ibtisam Daqqa |
| Time |
2:00-3:00 p.m. |
| Place |
CHE 203 |
Abstract
I present some basic facts about the Association Scheme and its Bose-Mesner
algebra. I will give some examples and go through the eigenmatrices of this
algebra.
Tuesday, November 16, 2004
| Title |
Two-Dimensional Finite State Automata |
| Speaker |
Joni Pirnot |
| Time |
2:00-3:00 p.m. |
| Place |
CHE 203 |
Abstract
For two-dimensional shifts of finite type, we represent the shift by
constructing a directed graph having vertices with distinct labels. We then
construct a graph representation for one class of multidimensional sofic shifts
by changing the labels in the vertex shift representation of the shift of finite
type.
Tuesday, November 9, 2004
| Title |
A Self-Assembling DNA Model and related problems |
| Speaker |
Ana Staninska |
| Time |
2:00-3:00 p.m. |
| Place |
CHE 203 |
Abstract
I will describe a theoretical model of self-assembly inspired by DNA
nano-technology and DNA computing, and introduce related mathematical problems.
This model consists of tiles that assemble into graph-like complexes, which
assembled "properly" can represent a solution to a given problem. It can
be shown that the computational power is equivalent to solving NP-complete
problems.
Tuesday, November 2, 2004
| Title |
Radical Deformations of Polynomial Ideals |
| Speaker |
Professor Boris Shekhtman |
| Time |
2:00-3:00 p.m. |
| Place |
CHE 203 |
Abstract
It ought to be true that most (almost all, generic, &hellip) zero-dimensional
ideals are radical. We verify this for some special subclasses of ideals with an
eye for the hole ball of wax.
Tuesday, October 26, 2004
| Title |
A note on the Proof of a Theorem of Katz
(on the zeros of polynomials over a finite field) |
| Speaker |
Dr. Xiang-Dong Hou |
| Time |
2:00-3:00 p.m. |
| Place |
CHE 203 |
Abstract
Let $f_i\in\Bbb F_q[X_1,\dots, X_n]$ be polynomials of degree $d_i$, $1\le
i\le r$, where $d_1\ge\cdots\ge d_r\ge 1$. Denote the set of zeros of $f_i$
in $\Bbb F_q^n$ by $Z(f_i)$. N. Katz proved that $q^{\lceil\frac{n-d_1-\cdots-d_r}{d_1}\rceil}$
divides $|Z(f_1)\cap\cdots\cap Z(f_r)|$. A more elementary proof of this result
was given by D. Wan. We found a new and much shorter proof of this result.
Tuesday, October 19, 2004
| Title |
Inheritance of self-duality
in imprimitive distance-regular graphs |
| Speaker |
Dr. Brian Curtin |
| Time |
2:00-3:00 p.m. |
| Place |
CHE 203 |
Abstract
We discuss the dual nature of the block and quotient Bose-Mesner algebras
constructed from an imprimitive Bose-Mesner algebra. We focus on the case where
the imprimitive Bose-Mesner algebra is self-dual. Again, we illustrate these
properties on the Hamming cubes.
Tuesday, October 12, 2004
| Title |
Imprimitivity in distance-regular graphs |
| Speaker |
Dr. Brian Curtin |
| Time |
2:00-3:00 p.m. |
| Place |
CHE 203 |
Abstract
We survey some results concerning imprimitivity of Bose-Mesner algebras and
distance-regular graphs. We focus on the constructions of block and quotient
Bose-Mesner subalgebras from an imprimitive Bose-Mesner algebra. We shall
illustrate these constructions on the Hamming cubes.
Tuesday, October 5, 2004
| Title |
Elementary calculations in twisting knots |
| Speaker |
Dr. Masahico Saito |
| Time |
2:00-3:00 p.m. |
| Place |
CHE 203 |
Abstract
A knot diagram is a projection usually only with double points. When we twist
a knot, three segments may intersect at one point in projection during the
movement of a twist. How many times this occures in a single twist is the question
we ask. Elementary calculations of polynomials can be used for giving lower
bounds, and I explain how.
This happens to work for specific polynomials, and it remains a mystery
why this works and how we can generalize this method.
Tuesday, September 28, 2004
| Title |
A Proof that NP is not Equal to P |
| Speaker |
Viktor Ivanov
(Formerly) Glushkov Institute of Cybernetics
|
| Time |
2:00-3:00 p.m. |
| Place |
CHE 203 |
Abstract
This proof is a rigorous diagonalization-kind one based on better estimates of
lower bounds on time complexity that hold for all solution algorithms. Almost no
special knowledge other than logical and combinatorial efforts is needed to
understand the proof.
Tuesday, September 21, 2004
| Title |
Non-ribbon surface braids whose closures are ribbon |
| Speaker |
Isao Hasegawa |
| Time |
2:00-3:00 p.m. |
| Place |
CHE 203 |
Abstract
Markov's theorem gives the necessary and sufficient condition for closures of
two braids to represent the same link. It is known that the stabilization, a kind
of Markov moves, is indeed necessary even if two braids of the same degree
represent the same link. In this talk, we make a similar example for surface-knot
theory.
| Title |
The braid index of surface-knots and quandle colorings |
| Speaker |
Kokoro Tanaka |
| Time |
2:00-3:00 p.m. |
| Place |
CHE 203 |
Abstract
The braid index of a surface-knot F is the minimal number among the
degrees of all simple surface braids whose closures are ambient isotopic to
F. We prove that there exists a surface-knot with braid index
k for any positive integer k. To prove it, we use colorings
of surface-knots by quandles and give lower bounds of the braid index of
surface-knots.
Tuesday, September 14, 2004
| Title |
Dimension: the Iteration-by-Iteration Space Measure, Part
II |
| Speaker |
Professor Greg McColm |
| Time |
2:00-3:00 p.m. |
| Place |
CHE 203 |
Tuesday, August 31, 2004
| Title |
Dimension: the Iteration-by-Iteration Space Measure |
| Speaker |
Professor Greg McColm |
| Time |
2:00-3:00 p.m. |
| Place |
CHE 203 |
Abstract
One of the standard representations of PTIME is by Least Fixed Point logic.
Given an input (e.g., a graph, a string, etc.), one uses a (monotonic) operator
develop a relation by repeated iterations until a “fixed point” is
reached. An immediate examination of the fixed point relation determines whether
the inputted structure satisfies the PTIME query.
One of the measures used is the arity or dimension of the relation that was
developed. Call a PTIME query “k-dimensional” if it can be
answered by developing a k-dimensional relation as above. In 1982,
Chandra and Harel asked if there existed a k such that all PTIME
queries are k-dimensional. In 1996, Grohe proved that all DLOGSPACE
queries are 2-dimensional, raising the stakes on Chandra & Harel's question.
We will look at a variation of Least Fixed Point logic, one using bounded
quantification, and find that this variant does admit, for each k, a
PTIME query that is not k-dimensional. Alas, it is not clear what the
dimension of DLOGSPACE is when quantification is bounded.