| 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
| 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.
| 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.
| 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,...) zero-dimensional ideals are radical. We verify this for some special subclasses of ideals with an eye for the hole ball of wax.
| 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.
| 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.
| 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.
| 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.
| 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.
| 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.
| Title | Dimension: the Iteration-by-Iteration Space Measure, Part II |
| Speaker | Professor Greg McColm |
| Time | 2:00-3:00 p.m. |
| Place | CHE 203 |
| 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.
Please direct questions to mthmaster@nosferatu.cas.usf.edu.
Last updated: 22-Nov-2004.
Copyright © 2000, USF Department of Mathematics.