Research

Discrete Mathematics

(Leader: Prof. Greg McColm)

Friday, April 30, 2004

Abstract

In the first half of the talk, definitions of knot colorings and knot “invariants” will be given, and we will explain what we are trying to compute using Maple. Then we will demonstrate how to use the Maple programs we wrote, that are posted at www.math.usf.edu/~saito/maple.html.

Friday, April 23, 2004

Friday, April 16, 2004

Abstract

We recall Bose-Mesner algebras, some examples, and some notions of duality for Bose-Mesner algebras.

Friday, April 9, 2004

Friday, April 2, 2004

Abstract

The behavior of a cellular automaton is the iteration of a locally deterministic rule on an array of “cells”. We summarize the main characteristics of cellular automata, including what is meant by chaotic behavior. We show how the non-trivial additive CAs produce chaos even in the one-dimensional case. We define the shift-invariant metric introduced by Cattaneo, Formenti, and Mazoyer $$ d(x,y)=\limsup_{k\to\infty}\frac{\#\{i : x_i\ne y_i, |i|\le k\}}{2k+1} $$ and present some of its unexpected side-effects. Finally, we discuss prospects for applying this style of metric to the space of formal languages.

Friday, March 26, 2004

Friday, March 19, 2004

Abstract

I will discuss a problem Xiang-dong Hou recently told to me at the dinner for a recent colloquium visitor. The problem apparently arose in cryptography, but I will not talk about that. Here's the problem: Let \(V(n,2)\) be the vector space of dimension \(n\) over the field with \(2\) elements. This is just all binary \(n\)-tuples with coordinate addition \(\operatorname{mod}\,2\). A \(2\)-dimensional affine subspace of \(V(n,2)\) is just a set \(\{x,y,z,w\}\) of 4 distinct vectors \(x\), \(y\), \(z\), \(w\) such that \(x+y+z+w=0\) (the zero vector). The question is: Does there exist a permutation \(p\) of \(V(n,2)\) such that whenever \(U\) is a \(2\)-dimensional affine subspace of \(V(n,2)\) then \(p(U)\) is NOT an affine subspace? It is known that this is true if \(n\) is odd. If \(n=2\) it is trivially false. If \(n=4\), Xiang-dong has proved it is false. The smallest open case is \(n=6\). Brute force search is out since the number of permutations of \(V(6,2)\) is \(64!\) which is larger than \(10^{90}\). I will discuss some progress on this case, a new conjecture and generalizations.

Friday, February 27, 2004

Friday February 20, 2004

Abstract

Let \(p\) be a prime and let \(r\), \(e\), \(m\) be positive integers such that \(r|e\) and \(e|m\). We introduce a partial order \(\prec\) in \(\mathcal{U}=\{0,1,\dotsc,\frac me(p-1)\}^e\) defined by an \(e\)-dimensional simplicial cone. We show that extended cyclic codes of length \(p^m\) over \(\mathbb{F}_{p^r}\) which are invariant under \(\mathrm{AGL}\left(\frac me,\mathbb{F}_{p^e}\right)\) can be enumerated by the ideals of \((\mathcal{U},\prec)\) which are invariant under the \(r\)th power of a circulant permutation matrix. When \(e=2\), we enumerate all such invariant ideals by describing their boundaries. Explicit formulas are obtained for the total number of \(\mathrm{AGL}(\frac m2,\mathbb{F}_{p^2})\)-invariant extended cyclic codes of length \(p^m\) over \(\mathbb{F}_{p^r}\) and for the dimension of such codes. We also enumerate all self-dual \(\mathrm{AGL}(\frac m2,\mathbb{F}_{2^2})\)-invariant extended cyclic codes of length \(2^m\) over \(\mathbb{F}_{2^2}\) when \(\frac m2\) is odd; the restrictions on the parameters are necessary conditions for the existence of self-dual affine invariant codes with \(e=2\).

Friday, February 13, 2004

Abstract

Let \(\mathcal{F}\) denote a field, and let \(V\) denote a vector space over \(\mathcal{F}\) with finite, positive dimension. Let \(\operatorname{End}(V)\) denote the \(\mathcal{F}\)-algebra consisting of all \(\mathcal{F}\)-linear transformations from \(V\) to \(V\). An ordered pair \(A\), \(A^*\) of elements from \(\operatorname{End}(V)\) is said to be a tridiagonal pair on \(V\) whenever the following four conditions are satisfied:

1. Each of \(A\) and \(A^*\) is diagonalizable over \(\mathcal{F}\);
2. there exists an ordering \(V_0,V_1,\dotsc,V_d\) of the eigenspaces of \(A\) such that \(A^{*}V_i\subseteq V_{i-1}+V_i+V_{i+1}\) (\(0\le i\le d\)), where \(V_{-1}=0\), \(V_{d+1}=0\);
3. there exists an ordering \(V^{*}_{0},V^{*}_{1},\dotsc,V^{*}_{\delta}\) of the eigenspaces of \(A^*\) such that \(AV^{*}_{i}\subseteq V^{*}_{i-1}+V^{*}_{i}+V^{*}_{i+1}\) (\(0\le i\le\delta\)), where \(V^{*}_{-1}=0\), \(V^{*}_{\delta+1}=0\);
4. there is no a subspace \(W\) of \(V\) such that both \(AW\subseteq W\) and \(A^{*}W\subseteq W\), other than \(W=0\) and \(W=V\).

Assume that \(A\), \(A^*\) is a mild tridiagonal pair on \(V\) of \(q\)-Serre type. First, we find a nice basis for \(V\) and describe the action of \(A\), \(A^*\) on this basis in terms of six parameters. Then, we relate \(A\), \(A^*\) to the quantum affine algebra \(U_q(\widehat{\mathrm{sl}_2})\). We show that \(A\), \(A^*\) can be endowed with the structure of an irreducible module for \(U_q(\widehat{\mathrm{sl}_2})\). Finally, we consider this \(U_q(\widehat{\mathrm{sl}_2})\)-module structure on \(A\), \(A^*\). We show that it is isomorphic to a tensor product of two particular evaluation modules for \(U_q(\widehat{\mathrm{sl}_2})\).

Friday, February 6, 2004

There will be no seminar this week.

Friday, January 30, 2004

Abstract

We consider codes that are extensions from comma-free and infix codes. These codes are defined through an involution (\(\theta\)) on the set of symbols. Although the background motivation for these codes comes from the cross hybridization of DNA strands, they define new classes of languages and as such present new models of codes. We present definitions and some basic properties of these codes and consider properties of their syntactic monoid. Necessary and sufficient conditions on a monoid to be the syntactic monoid of a \(\theta\)-infix or a \(\theta\)-k-codes are discussed.

Friday, January 23, 2004

Friday, January 16, 2004

Abstract

Some of the most popular logics in theoretical computer science are the “fixed point logics” that repeatedly iterate a formula or system of formulas. One of these popular logics is Least Fixed Point logic, which can be described in terms of 2-player games. Another is Datalog, which could be regarded as a near-solitaire version of the Least Fixed Point logic game, where the player associated with existential quantification gets to make most of the moves.

Both these logics can be used to characterize PTIME.

We review the least fixed point logic, and look at the Datalog-like logic where the universal quantification player makes most of the moves. We explore this “co-Datalog” logic and its strengths and weaknesses.

NOTE: There will be an organizational meeting prior to the talk.