USF Home > College of Arts and Sciences > Department of Mathematics & Statistics

Mathematics & Statistics

# Discrete Mathematics (Leader: Prof. Greg McColm)

## Tuesday, November 23, 2004

Title
Speaker
Time
Place

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

Two-Dimensional Finite State Automata
Joni Pirnot
2:00pm-3:00pm
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
Speaker
Time
Place

A Self-Assembling DNA Model and related problems
Ana Staninska
2:00pm-3:00pm
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
Speaker
Time
Place

Boris Shekhtman
2:00pm-3:00pm
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
Speaker
Time
Place

A note on the Proof of a Theorem of Katz (on the zeros of polynomials over a finite field)
Xiang-Dong Hou
2:00pm-3:00pm
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
Speaker
Time
Place

Inheritance of self-duality in imprimitive distance-regular graphs
Brian Curtin
2:00pm-3:00pm
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
Speaker
Time
Place

Imprimitivity in distance-regular graphs
Brian Curtin
2:00pm-3:00pm
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
Speaker
Time
Place

Dimension: the Iteration-by-Iteration Space Measure, Part II
Greg McColm
2:00pm-3:00pm
CHE 203

## Tuesday, August 31, 2004

Title
Speaker
Time
Place

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