• Search USF
• A-Z Index
• USF Home

Discrete Mathematics
(Leader: Prof. Greg McColm)

Friday, April 30, 2004

Title	Coloring Knots by Maple
Speaker	Dr. Masahiko Saito and Chad Smudde
Time	4:00-5:00 p.m.
Place	ENB 108

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

Title	Duality in Bose-Mesner Algebras, Part II
Speaker	Dr. Brian Curtin
Time	4:00-5:00 p.m.
Place	PHY 108

Friday, April 16, 2004

Title	Duality in Bose-Mesner Algebras
Speaker	Dr. Brian Curtin
Time	4:00-5:00 p.m.
Place	PHY 108

Abstract

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

Friday, April 9, 2004

Title	Cellular Automata: the Implications of an Alternative Metric on the Space of Configurations, Part II
Speaker	David Kephart
Time	4:00-5:00 p.m.
Place	PHY 108

Friday, April 2, 2004

Title	Cellular Automata: the Implications an Alternative Metric on the Space of Configurations
Speaker	David Kephart
Time	4:00-5:00 p.m.
Place	PHY 108

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)=\lim\sup_{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

Title	How far from an affine mapping can a permutation of a vector space be?, Part II
Speaker	Professor Edwin Clark
Time	4:00-5:00 p.m.
Place	PHY 108

Friday, March 19, 2004

Title	How far from an affine mapping can a permutation of a vector space be?
Speaker	Professor Edwin Clark
Time	4:00-5:00 p.m.
Place	PHY 108

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 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⁹⁰. I will discuss some progress on this case, a new conjecture and generalizations.

Friday, February 27, 2004

Title	Enumeration of Certain Affine Invariant Extended Cyclic Codes, II
Speaker	Dr. Xiang-Dong Hou
Time	4:00-5:00 p.m.
Place	PHY 108

Friday February 20, 2004

Title	Enumeration of Certain Affine Invariant Extended Cyclic Codes
Speaker	Dr. Xiang-Dong Hou
Time	4:00-5:00 p.m.
Place	PHY 108

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,\cdots,\frac me(p-1)\}^e$ defined by an e-dimensional simplicial cone. We show that extended cyclic codes of length p^m over ${\Bbb F}_{p^r}$ which are invariant under ${\rm AGL}(\frac me, {\Bbb F}_{p^e})$ can be enumerated by the ideals of $({\mathcal U}, \prec)$ which are invariant under the rth 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 ${\rm AGL}(\frac m2, {\Bbb F}_{p^2})$-invariant extended cyclic codes of length p^m over ${\Bbb F}_{p^r}$ and for the dimension of such codes. We also enumerate all self-dual ${\rm AGL}(\frac m2, {\Bbb F}_{2^2})$-invariant extended cyclic codes of length 2^m over ${\Bbb 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

Title	Tridiagonal Pairs
Speaker	Hasan Al-Najjar
Time	4:00-5:00 p.m.
Place	PHY 108

Abstract

Let ${\Fa}$ denote a field, and let V denote a vector space over ${\Fa}$ with finite, positive dimension. Let End(V) denote the ${\Fa}$-algebra consisting of all ${\Fa}$-linear transformations from V to V. An ordered pair A, A^* of elements from 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 $\Fa$;
2. there exists an ordering V₀, V₁, …, V_d of the eigenspaces of A such that A^* V_i ⊆ V_i-1 + V_i + V_i+1 (0 ≤ i ≤ d), where V_-1 = 0, V_d+1 = 0;
3. there exists an ordering $V^{*}_{0}, V^{*}_{1}, …, V^{*}_{δ}$ of the eigenspaces of A^* such that $AV^{*}_{i} ⊆ V^{*}_{i-1} + V^{*}_{i} + V^{*}_{i+1}$ (0 ≤ i ≤ δ), where $V^{*}_{-1} = 0$, $V^{*}_{δ+1}=0$;
4. there is no a subspace W of V such that both AW ⊆ W and A^*W ⊆ 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{sl₂}). We show that A, A^* can be endowed with the structure of an irreducible module for U_q(\widehat{sl₂}). Finally, we consider this U_q(\widehat{sl₂})-module structure on A, A^*. We show that it is isomorphic to a tensor product of two particular evaluation modules for U_q(\widehat{sl₂}).

Friday, February 6, 2004

There will be no seminar this week.

Friday, January 30, 2004

Title	Algebraic Properties of Involution Codes
Speaker	Kalpana Mahalingam
Time	4:00-5:00 p.m.
Place	PHY 108

Abstract

We consider codes that are extensions from comma-free and infix codes. These codes are defined through an involution (θ) 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 θ-infix or a θ-k-codes are discussed.

Friday, January 23, 2004

Title	Indefinite Sequences of Universal Quantifications: A Case Study in Fixed Point Logic, II
Speaker	Professor Greg McColm
Time	4:00-5:00 p.m.
Place	PHY 108

Friday, January 16, 2004

Title	Indefinite Sequences of Universal Quantifications: A Case Study in Fixed Point Logic
Speaker	Professor Greg McColm
Time	4:00-5:00 p.m.
Place	PHY 108

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.