# Research

## Discrete Mathematics

### Tuesday, November 23, 2004

Title: The Association Scheme and its Bose-Mesner algebra
Speaker: Ibtisam Daqqa
Time: 2:00pm‐3:00pm
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:00pm‐3:00pm
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:00pm‐3:00pm
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: Boris Shekhtman
Time: 2:00pm‐3:00pm
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.

### 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: Xiang-Dong Hou
Time: 2:00pm‐3:00pm
Place: CHE 203

#### Abstract

Let $$f_i\in\mathbb{F}_q[X_1,\dotsc,X_n]$$ be polynomials of degree $$d_i$$, $$1\le i\le r$$, where $$d_1\ge\dotsb\ge d_r\ge 1$$. Denote the set of zeros of $$f_i$$ in $$\mathbb{F}_q^n$$ by $$Z(f_i)$$. N. Katz proved that $$q^{\lceil\frac{n-d_1-\dotsb-d_r}{d_1}\rceil}$$ divides $$|Z(f_1)\cap\dotsb\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: Brian Curtin
Time: 2:00pm‐3:00pm
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: Brian Curtin
Time: 2:00pm‐3:00pm
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:00pm‐3:00pm
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:00pm‐3:00pm
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:00pm‐3:00pm
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:00pm‐3:00pm
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: Greg McColm
Time: 2:00pm‐3:00pm
Place: CHE 203

### Tuesday, August 31, 2004

Title: Dimension: the Iteration-by-Iteration Space Measure
Speaker: Greg McColm
Time: 2:00pm‐3:00pm
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.