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

Mathematics & Statistics

# Discrete Mathematics (Leader: Prof. Greg McColm)

## Monday, April 28, 2003

Title
Speaker
Time
Place

Morphisms and Continuous Maps on the Space of Formal Languages
Daniela Genova
2:00pm-3:00pm
PHY 109

Abstract

The set of all languages consisting of finite words over a finite alphabet equipped with the standard language metric is homeomorphic to the Cantor space. We characterize the continuous morphisms on this space and discuss morphic properties of forbidding-enforcing families.

## Monday, April 21, 2003

Title
Speaker
Time
Place

An Introduction to Back-Circulant Graphs
Nathan Chau
4:00pm-5:00pm
PHY 108

Abstract

We will look at some basic properties and examples of “back-circulant&rdquo graphs, which are defined as follows:

Let $$S$$ be a subset of $$Z_n$$, the group of integers $$\operatorname{mod} n$$. The back-circulant graph $$BC(S,n)$$ has vertex set $$Z_n$$, and vertex $$u$$ is adjacent to vertex $$v$$ iff $$u+ v$$ is in $$S$$ and $$u$$ is not equal to $$v$$. (The restriction $$u$$ not equal to $$v$$ is necessary to avoid loops in $$BC(S,n)$$).

Theorems involving the connectivity, degree sequence, and (partial) classification of these graphs will be discussed.

## Monday, April 14, 2003

Title
Speaker
Time
Place

Languages From and for DNA Sequences
Kalpana Mahalingam
4:00pm-5:00pm
PHY 108

Abstract

In DNA nanotechnology and DNA based computations the design of DNA sequences that are error resistant is of essential importance. The set of all sequences that are generated by a biomolecular protocol forms a language over the four letter alphabet $$\mathrm{DELTA}=\{A,G,C,T\}$$. This alphabet is associated with a natural involution mapping $$A\mapsto T$$, $$G\mapsto C$$, which is an antimorphism of $$\mathrm{DELTA}^*$$. In order to avoid undesirable Watson-Crick bonds between the words (undesirable hypridizaation), the language has to satisfy certain coding properties. In particular for DNA, no involution of a word is a subword of another word, or no involution of a word is a subword of a composition of two words. The set of code words that satisfy these properties forms a language. We give necessary and sufficient conditions for a finite set of code words to generate (through concatenation) an infinite set of code words with the same properties.

## Monday, April 7, 2003

Title
Speaker
Time
Place

Modular Leonard Triples
Brian Curtin
4:00pm-5:00pm
PHY 108

Abstract

Let $$V$$ denote a vector space of finite positive dimension. A Leonard triple is a triple $$A$$, $$A^*$$, $$A^{\#}$$ of linear operators on $$V$$ such that for each choice of $$A$$, $$A^*$$, and $$A^{\#}$$, there is a basis for $$V$$ such that the matrix representing the chosen operator is diagonal and the matrices representing the other two are irreducible tridiagonal. A Leonard triple $$A$$, $$A^*$$, $$A^{\#}$$ is called modular when for each choice $$A$$, $$A^*$$, and $$A^{\#}$$, there is an antiautomorphism of $$\operatorname{End}(V)$$ which fixes the chosen operator and swaps the other two.

We describe a complete charaterization of modular Leonard triples which gives the entries of the matrices representing the three operators with respect to one of the above mentioned bases. We also discuss how instances of modular Leonard triples arise from distance-regular graph which support a spin model.

## Monday, March 31, 2003

Title
Speaker
Time
Place

Leonard Pairs, Part II
Hassan Al-Najjar
4:00pm-5:00pm
PHY 108

## Monday, March 24, 2003

Title
Speaker
Time
Place

Leonard Pairs
Hassan Al-Najjar
4:00pm-5:00pm
PHY 108

Abstract

Let $$F$$ denote a field, and let $$V$$ denote a vector space over $$F$$ with finite positive dimension. We consider a pair of $$F$$-linear maps $$(A,B)$$ from $$V$$ to $$V$$ satisfying the following conditions:

1. there exists a basis for $$V$$ with respect to which the matrix representing $$A$$ is diagonal, and the matrix representing $$B$$ is irreducible tridiagonal.
2. there exists a basis for $$V$$ with respect to which the matrix representing $$B$$ is diagonal, and the matrix representing $$A$$ is irreducible tridiagonal. We call such a pair a Leonard pair on $$V$$.

## Monday, February 10, 2003

Title
Speaker

Time
Place
Note

Cographic Excluded Minors for the Classes of Gain-Graphic Matroids
Hongxun Qin
Department of Mathematics
Ohio State University
4:00pm-5:00pm
PHY 108
Stephen Suen
Speaker is a candidate for Asst. Prof. in Algebra.

Abstract

A gain graph is a graph with edges labeled by elements of a group. A matroid can then be defined on its edge set. For a finite group $$A$$, the class of gain-graphic matroids $$Z(A)$$ forms a minor-closed class. Hence a natural problem is to determine the excluded minors for the class. We characterize the graphs whose dual matroids are excluded minors for $$Z(A)$$. Let $$G$$ be a 2-connected graph and let $$N$$ be the dual of its cycle matroid. If the order of $$A$$ is odd, then $$N$$ belongs to $$Z(A)$$ if and only if $$G$$ is planar; if the order of $$A$$ is even, then $$N$$ belongs to $$Z(A)$$ if and only if $$G$$ is projective planar.

This is joint work with Thomas Dowling.

## Monday, January 27, 2003

Title
Speaker
Time
Place

Negation and Failure, Part III
Greg McColm
4:00pm-5:00pm
PHY 108

Abstract

In first order logic, negation is effected by plopping a negation sign in front of a formula. In infinitary (game-theoretic) logics, things are not so simple.

We look at a fragment of least fixed point logic: the logic where all but a fixed number of moves is made by Player E. (This logic is commonly called “Existential Fixed Point logic”.) We look at what Immerman's theorem says — and does not say — about negation in this logic.

## Friday, January 24, 2003

Title
Speaker
Time
Place

Negation and Failure, Part II
Greg McColm
4:00pm-5:00pm
PHY 108

Note: There will be another organizational meeting prior to the talk.

## Friday, January 17, 2003

Title
Speaker
Time
Place

Negation and Failure
Greg McColm
4:00pm-5:00pm
PHY 108

Abstract

In first order logic, negation is effected by plopping a negation sign in front of a formula. In infinitary (game-theoretic) logics, things are not so simple.

We start with a game-theoretic view of Least Fixed Point logic, and find that just because a relation can be expressed in that logic doesn't mean that its negation can be so expressed.

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

## Wednesday, January 8, 2003

Title
Speaker

Time
Place

Orbits of Acyclic Group and the $$q$$-binomial Coefficient
Dennis Stanton
University of Minnesota
3:00pm-4:00pm
CHE 203