Research

Discrete Mathematics

(Leader: Prof. Greg McColm)

Monday, April 28, 2003

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

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

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

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

Monday, March 24, 2003

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

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

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

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

Friday, January 17, 2003

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