University of South Florida

College of Arts and Sciences

Search

Menu

Give Now

Title: The Association Scheme and its Bose-Mesner algebra Speaker: Ibtisam Daqqa Time: 2:00pm‐3:00pm Place: CHE 203

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:00pm‐3:00pm Place: CHE 203

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:00pm‐3:00pm Place: CHE 203

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

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

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.

Title: Inheritance of self-duality in imprimitive distance-regular graphs Speaker: Brian Curtin Time: 2:00pm‐3:00pm Place: CHE 203

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: Brian Curtin Time: 2:00pm‐3:00pm Place: CHE 203

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:00pm‐3:00pm Place: CHE 203

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:00pm‐3:00pm Place: CHE 203

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:00pm‐3:00pm Place: CHE 203

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

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: Greg McColm Time: 2:00pm‐3:00pm Place: CHE 203

Title: Dimension: the Iteration-by-Iteration Space Measure Speaker: Greg McColm Time: 2:00pm‐3:00pm Place: CHE 203

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.