Jump to: 98-99 * 00-01 * 01-02 * 02-03 * 03-04 * 04-05 * 05-06 * 06-07 * 07-08 * 08-09 * 09-10 * F10

Fall 2010

(Leader: Prof. Greg McColm)

Monday, November 15, 2010

Title: Hierarchical Self Assembly: Physical Implementation of Substitution Rules to Produce Quasicrystalline Patterns
Speaker: Jennifer Padilla
Time: 3:05pm‐4:05pm
Place: LIF 263

Abstract

Substitution rules efficiently produce quasicrystalline patterns such as those found in the Penrose and Robinson tilings. A few simple modifications to the Tile Assembly Model allow tiles to follow a hierarchical self assembly pathway that can effect substitution rules in a physical assembly process. I will introduce these modifications along with a tile set that can self assemble into Robinson patterns via a hierarchical process. I will also discuss how these tiles could be built using DNA origami and DNA strand exchange mechanisms.

Monday, November 8, 2010

Title: Characterizing the Dynamics of an Asynchronous Automaton on a Family of Graphs
Speaker: Apurva Bhatty
Time: 3:05pm‐4:05pm
Place: LIF 263

Abstract

Parallel distributed algorithms can be modeled as the application of automata (with \(k\) states) on a single component undirected graph structure, \(G\) with \(n\) vertices. The dynamics of parallel asynchronous processing can be described as the transitions of the global state of the automata on the graph, defined by a directed graph \(G_d\) with \(k^n\) vertices. I will describe and define a polynomial which can encode the stability of automata over a family of graphs, along with a combinatorics technique for calculating (in polynomial time) the sizes of the congruence classes defined by the number of unstable vertices over the graph. This allows the characterization of the directed graph \(G_d\) by the number of directed edges in it.

Monday, November 1, 2010

Title: Statistical Models for Social Networks: Biased Nets vs. Exponential Random Graphs
Speaker: John Skvoretz, USF Department of Sociology
Time: 3:05pm‐4:05pm
Place: LIF 263

Abstract

I review two types of statistical models for social networks: ones rooted in the random and biased net theory first proposed by Rapoport in the 1950s and ones in the exponential family based on the Hammersley-Clifford Theorem applied to network data. In the context of social science, models of the first type are theoretical models while models of the second are methodological models. In either case the basic challenge raised by network data is massive interdependency among the random variables defining the presence or absence of a tie. The two families of models approach the problem differently but seek to incorporate similar effects determining the outcome of tie formation processes. Several specific models are set out to illustrate the types of effects commonly assumed to govern the formation of social ties.

Monday, October 18, 2010

Title: Assembly Graphs and Assembly Polynomials
Speaker: Egor Dolzhenko
Time: 3:05pm‐4:05pm
Place: LIF 263

Abstract

Assembly graphs are used to model gene recombination in ciliates. We associate an assembly polynomial to each assembly graph. In the talk, I will discuss a few basic properties of the assembly polynomials and show their relationship to circle graphs.

Monday, October 4, 2010

Title: Negative binomials: properties and applications
Speaker: Arcadii Grinshpan
Time: 3:05pm‐4:05pm
Place: LIF 263

Abstract

We will discuss the recursive, asymptotic, and other properties of the negative binomial coefficients. The recent pure binomial results and some applications involving general binomial and exponential inequalities, hypergeometric series, special functions and conformal maps will be presented.

Monday, September 27, 2010

Title: Modeling Enforcement Mechanisms with Security Automata
Speaker: Jay Ligatti, USF Computer Science Engineering Department
Time: 3:05pm‐4:05pm
Place: LIF 263

Abstract

This talk will present recent work on modeling security mechanisms as automata. The mechanisms monitor the runtime behavior of software and modify that behavior when it violates a mechanism's policy. We will discuss the mechanisms' operational semantics and the transition function it implies. After defining a model for security automata, which includes definitions of automaton traces, policies, and policy enforcement, we will briefly analyze the sorts of policies these security automata can enforce.

Monday, September 20, 2010

Title: A Manifesto for Reticular Geometry, Part II
Speaker: Greg McColm
Time: 3:05pm‐4:05pm
Place: LIF 263

Abstract

In our previous episode, we decided that a good place to start devising a “reticular geometry” was with CW complexes. After a brief review, we will look at how the tools of geometric group theory and other even more sinister areas can be adapted to address the objects of reticular geometry.

Monday, September 13, 2010

Title: A Manifesto for Reticular Geometry
Speaker: Greg McColm
Time: 3:05pm‐4:05pm
Place: LIF 263

Abstract

By “Reticular Geometry”, we mean the study of the articulation of many geometric components and their assembly or arrangement into larger structures. Reticular geometry, like “prose”, is something many people (mathematicians and otherwise) have been doing for a long time without treating it as a field in itself. However, some polemical chemists suggest that there is a demand for reticular geometry as a coherently organized body of knowledge developed by some kind of scholarly community. We will look at what this demand consists of, and what resources mathematicians may offer in the near future.

Tuesday, September 7, 2010

Title: Notes on unknotting operations
Speaker: Takuji Nakamura, Department of Engineering Science, Osaka Electro-Communication University, Osaka, Japan
Time: 3:30pm‐4:00pm
Place: NES 102

Abstract

A knot is a knotted loop in a \(3\)-dimensional space. For a given knot, When we want to know how much it is being knotted we consider the number of times to apply a certain operation to untie it. We call such an operation an unknotting operation. In this talk, we will introduce several unknotting operations and show recent results about “sharp unknotting operation”.

Title: Open book decomposition of \(3\)-manifold and intersection numbers of arc system
Speaker: Ryosuke Yamamoto, College of Science and Engineering
Ritsumeikan University
Kyoto, Japan
Time: 4:00pm‐4:30pm
Place: NES 102

Abstract

Every closed orientable \(3\)-manifold has a structure called open book decomposition, which is determined by an orientable surface with boundary and an automorphism of the surface fixing the boundary pointwise. Such an automorphism is completely described by an arc system on the surface and its image of the automorphism. We will focus on (geometric and algebraic) intersection numbers of arcs with their images and discuss relations between such intersection numbers and some topological properties of open book decomposition.

Spring 2010

(Leader: Prof. Greg McColm)

Monday, April 26, 2010

Title: Graph Transversals and Transversals of Faces
Speaker: Joy D'Andrea
Time: 3:05pm‐3:55pm
Place: PHY 108

Abstract

In graph theory, a transversal, given a partition of vertices and edges, will consist of one vertex and one edge from each orbit of a group of automorphisms. We are expanding this concept to finding “transversals” of the faces on CW-Complexes of Polyhedra. We are looking for a transversal of faces that will be connected. In this talk we will provide a construction of a proof and show some examples.

Monday, April 19, 2010

Title: Factorial-local Cellular Automata
Speaker: Egor Dolzhenko
Time: 3:05pm‐3:55pm
Place: PHY 108

Abstract

The time evolution of a bi-infinite configuration of a one-dimensional cellular automaton (CA) can be visualized as a half-plane array of symbols. The set of rectangular blocks extracted from such arrays forms a two-dimensional (picture) language. If this picture language is factorial-local, we call the cellular automaton factorial-local. We show that the class of factorial-local CA is properly included in the class of regular cellular automata and that it contains nilpotent cellular automata. We give a characterization of factorial-local CA and show that it is decidable whether a given set of blocks defines a factorial-local CA with a given radius, but the general membership problem for this class of cellular automata is undecidable.

Monday, April 12, 2010

Title: Involution codes applied to DNA Coding
Speaker: Andrew Burruss
Time: 3:05pm‐3:55pm
Place: PHY 108

Abstract

DNA and RNA molecules are composed of sequences of nucleotides. DNA sequences form a language with a four element alphabet. Hybridization errors can interfere with DNA coding by creating unwanted structures. These errors can be reduced by utilizing particular involution codes.

Monday, March 29, 2010

Title: The Acceptance Urn Model
Speaker: Kevin Wagner
Time: 3:05pm‐3:55pm
Place: PHY 108

Abstract

An urn contains \(p\) balls of value \(t\), and \(m\) balls of value \(-s\), where \(s\) and \(t\) are positive real numbers. The balls are drawn from the urn uniformly at random, without replacement, until the urn is empty. Before each draw, a player is asked whether he would like to accept the next ball drawn from the urn. If the player accepts, his payout will be the value of the next ball drawn. If the player does not accept, the next ball is drawn, but otherwise nothing happens. In this talk, we examine the acceptance urns for which \(s=t=1\), giving the distribution of the gain using an optimal strategy that maximizes the expected gain, via the reflection method. We then examine the broader collection of acceptance urns for which \(s=1\) and \(t\) is a positive integer, calculating the expected gain and finding the distribution of the gain using a different geometric approach, rotation.

Monday, March 22, 2010

Title: Anonymous ID Assignment for Data Mining
Speaker: Larry Dunning
Time: 3:05pm‐3:55pm
Place: PHY 108

Abstract

Each node \(n\) of a computer network \(\mathbf{N}\) holds an integer quantity \(Q_n\). The secure sum operation computes \(\operatorname{Sum}\{Q_n,n\in\mathbf{N}\}\) making the sum available to all nodes without revealing any individual contributions. Methods for computing secure sum include the use of network Edge-Disjoint Hamiltonian Cycles. The secure sum operation will be used as the basis of an iterative method for assigning each node in the network a unique number ID\(n\) in \(\{1,\dotsc,\mathbf{N}\}\).

The IDs are anonymous in that each node will have knowledge of only its own ID. The number of iterations required by the Anonymous ID Assignment algorithm (AIDA) can be assessed by use of a Markov Chain model. A second version of the AIDA protocol which transmits significantly shorter messages will be based on use of the Newton-Girard formulae. Implementation of the protocol can be facilitated by using a distributed algorithm for solving a resulting polynomial \(p(x)\) over \(\mathrm{GF}(P)\), where \(p(x)\) is expressed in terms of the Newton basis polynomials.

Monday, March 15, 2010

Title: Forbidding-Enforcing Classes of Graphs
Speaker: Daniela Genova, University of North Florida
Time: 3:05pm‐3:55pm
Place: PHY 108

Abstract

A forbidding-enforcing system (fe-system) defines a class of graphs using two sets of boundary conditions. To comply with the restrictions imposed by a forbidding set, a graph should not contain certain combinations of subgraphs specified by this set. An enforcing set on the other hand, requires that certain subgraphs induce larger subgraphs in the graph structure. Thus, an fe-system defines a class of graphs consisting of the graphs that satisfy both the forbidding restrictions and the enforcing restrictions imposed by the system. The talk will include some properties of fe-systems, as well as, characterizations of some well-known classes of graphs by fe-systems.

Monday, March 1, 2010

Title: Coherence in Random Number Generators used in Parallel Distributed Systems
Speaker: Apurva Bhatty
Time: 3:05pm‐3:55pm
Place: PHY 108

Abstract

Simulation of probabilistic automata, synchronous and asynchronous, in serial and parallel computational architectures requires the use of pseudo-random number generation algorithms. PRNG and QRNG (quasi-random) algorithms are deterministic and cyclic with very long periods, and can also show coherence over various multiple phases. I will describe various issues with parallel random number generation for multiple threads, multiple processors, and multiple architectures (including GPU's) and a possible improvement which I will test with simulation.

As a continuation of a previous talk, I will also show how the stochastic matrix of a probabilistic automaton computed asynchronously on a graph can be simplified with two specific examples of metrics and equivalence classes. I will show how the \(16\times 16\) stochastic matrix of a specific automaton on \(\mathrm{C}_4\) can be reduced to a \(3\times 3\) stochastic matrix by using a stability metric as an equivalence class; and I will show how the \(2^{n+1}\times 2^{n+1}\) stochastic matrix of this automaton on a star-graph \(S_n=K_{1,n}\) can be reduced to matrix of size \((2n+2)\times (2n+2)\) by using Hamming distance from a particular state as an equivalence class.

Monday, February 8, 2010

Title: A Matrix form of the Jacobi-Trudi Identity
Speaker: Neranga Fernando
Time: 3:05pm‐3:55pm
Place: PHY 108

Abstract

The Jacobi-Trudi Identity is a well known formula which expresses the Schur functions as a determinant of the complete homogeneous symmetric functions. We found a matrix form of the Jacobi-Trudi Identity.

Monday, February 1, 2010

Title: Combinatorial Dynamics, Part II
Speaker: Erik Lundberg
Time: 3:05pm‐3:55pm
Place: PHY 108

Abstract

We will continue to consider iteration of a continuous function as a dynamical system. After finishing a sketch of the proof of Sharkovsky's Theorem, we will raise a related question which turns out to reduce to a problem purely in combinatorics. Namely, how often do cyclic permutations \(p\) have the property that for some \(i < j\), \(p(i) < i < j < p(j)\)? We give an asymptotic answer, which appends a statistical “however” to Sharkovsky's Theorem.

Monday, January 25, 2010

Title: Combinatorial Dynamics
Speaker: Erik Lundberg
Time: 3:05pm‐3:55pm
Place: PHY 108

Abstract

We will consider iteration of continuous functions as a simple example of a deterministic dynamical system where space is one-dimensional and time is discrete. An initial state that returns to itself after \(n\) iterations is called a period-\(n\) point, and its trajectory induces a cyclic permutation of size \(n\).

The occurrence of a period-\(n\) point can guarantee the occurrence of a period-\(m\) point for values of \(m\) depending on \(n\). Surprisingly, a period-\(3\) point guarantees periodic points of every period. Sharkovsky's Theorem gives an exhaustive description of the coexistence of periodic points. To glimpse the proof and to ask questions not answered by Sharkovsky's Theorem requires attention to the combinatorial structure of periodic trajectories. This will be our main focus. We will see that in spite of the strict ordering given by Sharkovsky's Theorem, there is a statistical “however” when all orbit types (induced cyclic permutations) are taken into account. Time permitting, we will briefly discuss knot types of periodic trajectories in three-dimensional flows as another instance of “combinatorial dynamics”.

Fall 2009

(Leader: Prof. Greg McColm)

Monday, November 30, 2009

Title: Biased Random Walks on Hypercubes, on \(K_{2^n}\), and on derived digraphs
Speaker: Apurva Bhatty
Time: 3:05pm‐3:55pm
Place: LIF 263

Abstract

Last year, Dr. Stark presented a \(4\)-node asynchronous probabilistic automaton, showing a technique to generate its Stochastic Matrix of size \(16\times 16\) (exponential space, \(2^n\times 2^n\) for a graph of \(n\) vertices) to describe the dynamics of that automaton.

In this talk, I will present:

the results of numerical simulation of biased and unbiased Random Walks on degraded Hypercube network topologies (digraphs with select arcs removed) derived from instances of various families of graphs of size up to \(n=1024\) vertices
a representational scheme for these automata
a technique to generate approximate Stochastic matrices which take up polynomial space of size \(\left(n^2\times n^2\right)\)
a conjecture on the scaling of the dynamics of these automata, and describe future simulations to test the conjecture.

Monday, November 23, 2009

Title: On monotone and hereditary properties of graphs and hypergraphs
Speaker: Brendan Nagle
Time: 3:05pm‐3:55pm
Place: LIF 263

Abstract

A property \(\Pi\) of graphs (\(k\)-uniform hypergraphs) is a collection of graphs (\(k\)-uniform hypergraphs) that is closed under isomorphism. A property \(\Pi\) is said to be monotone if it is closed under taking subgraphs (subhypergraphs), and is said to be hereditary if it is closed under taking induced subgraphs (subhypergraphs). For a property \(\Pi\), let \(\Pi_n\) denote the subcollection of elements from \(\Pi\) defined on vertex set \(\{1,\dotsc,n\}\). The problem of estimating \(\left|\,\Pi_n\right|\) for monotone or hereditary properties \(\Pi\) is a very well studied problem, and includes work of many authors.

In this talk, we shall survey some known results in this area, including recent work of the speaker and R. Dotson.

Monday, November 16, 2009

Title: Witten multiple zeta functions associated with Lie algebras, Part II
Speaker: Jianqiang Zhao, Eckerd College
Time: 3:05pm‐3:55pm
Place: LIF 263

Abstract

After briefly recalling the basic properties of the Witten multiple zeta functions I will describe some of the recent works on the special values of these functions. These special values are closely related to the special values of multiple polylogarithms and classical multiple zeta functions. So I will also comment on some recent progress on multiple polylogarithms and classical multiple zeta functions in general. This work is partly joint with X. Zhou.

Monday, November 9, 2009

Title: Witten multiple zeta functions associated with Lie algebras, Part I
Speaker: Jianqiang Zhao, Eckerd College
Time: 3:05pm‐3:55pm
Place: LIF 263

Abstract

In this talk I will first describe the origin of Witten multiple zeta functions, with the basics of Lie algebras sketched. Then I will explain some of the most important properties of these functions, mostly discovered recently by Matsumoto and his collaborators using a combination of analytic and arithmetic tools.

Monday, October 26, 2009

Title: Some properties of assembly graphs associated with DNA recombination in ciliates
Speaker: Tilahun Muche
Time: 3:05pm‐3:55pm
Place: LIF 263

Abstract

Motivated by DNA recombination events that appear in certain species of ciliates we consider graphs with \(4\)-valent rigid vertices and two end-points, called assembly graphs. DNA recombination is modeled by smoothing of the \(4\)-valent vertices which is guided by certain types of paths in the graph, called polygonal paths. If \(k\) is the minimal number of polygonal paths that visit every vertex in a graph with precisely \(k-2\) vertices then this graph is called a realization graph. We define height sequence as a sequence of integers indicating the number of vertices in polygonal path and characterize all possible polygonal paths in certain realization graphs.

Monday, October 19, 2009

Title: Leonard pairs of classical type constructed from Lie algebra \(\operatorname{sl}(2)\)
Speaker: Brian Curtin
Time: 3:05pm‐3:55pm
Place: LIF 263

Abstract

We describe a construction of Leonard pairs from the Lie algebra \(\operatorname{sl}(2)\). It turns out that this construction yields all Leonard pairs of classical type — Racah, Hahn, dual Hahn, and Krawtchouk types. We describe some aspects of this result.

Monday, October 12, 2009

Title: CA-generated Two-dimensional Languages
Speaker: Egor Dolzhenko
Time: 3:05pm‐3:55pm
Place: LIF 263

Abstract

Understanding the long-term dynamics of cellular automata has been one of the central problems in the use of cellular automata as models to study physical and natural processes. One of the notions employed for this purpose is the trace of a (one-dimensional) cellular automaton.

I will introduce a notion of factorial-local cellular automata and emphasise its close relationship to two-dimensional factorial-local languages. Moreover, I will state some of the basic properties of factorial-local cellular automata.

In particular, I will prove that the factorial-local cellular automata have sofic traces.

Monday, October 5, 2009

Title: Nested ideals and the Tomas Sauer conjecture
Speaker: Tom McKinley
Time: 3:05pm‐3:55pm
Place: LIF 263

Abstract

Tomas Sauer conjectures that if an ideal complements polynomials in several variables of degree less than \(n\), then it is contained in a larger ideal that complements polynomials of degree less than \(n-1\). Clearly, this is the case for one variable. Boris Shekhtman constructed a counterexample to this conjecture for the case of three variables where \(n=3\). It has been an open question as to whether or not this conjecture is true for two variables. I will present a construction showing this does not hold for the case of two variables.

Monday, September 21, 2009

Title: What I Did This Summer, or Periodicity and Tiling Spaces, Part II
Speaker: Greg McColm
Time: 3:05pm‐3:55pm
Place: LIF 263

Monday, September 14, 2009

Title: What I Did This Summer, or Periodicity and Tiling Spaces
Speaker: Greg McColm
Time: 3:05pm‐3:55pm
Place: LIF 263

Abstract

A tiling space is a set of tilings with certain nice closure properties: what sort of closure properties depends on what one's agenda is. One of the most basic kinds of tiling space is the “principal” tiling space, generated by a single tiling. We find that under certain conditions, the difference between a periodic and an aperiodic tiling is the “size” of their respective principal tiling spaces.

Spring 2009

(Leader: Prof. Greg McColm)

Monday, April 13, 2009

Title: Simplicial Complexes of Modular Leonard Triples
Speaker: Jessica Sobkowiak
Time: 3:05pm‐3:55pm
Place: PHY 109

Abstract

Let \(K\) denote a field, and let \(V\) denote a vector space over \(K\) of finite positive dimension. An ordered triple \(A1\), \(A2\), \(A3\) of linear operators on \(V\) is said to be a Leonard triple whenever for each \(B\) in \(\{A1,A2,A3\}\) there exists a basis of \(V\) with respect to which the matrix representing \(B\) is diagonal and the matrices representing the other two operators are irreducible tridiagonal. A Leonard triple \(A1\), \(A2\), \(A3\) is said to be modular whenever for each \(B\) in \(\{A1,A2,A3\}\) there exists an antiautomorphism of \(\operatorname{End}(V)\) which fixes \(B\) and swaps the other two operators. We study simplicial complexes associated with Leonard triples and modular Leonard triples. Our focus is on the case when the simplicial complex is finite.

Monday, April 6, 2009

Title: Characterization of radical ideals, Part II
Speaker: Boris Shekhtman
Time: 3:05pm‐3:55pm
Place: PHY 109

Monday, March 30, 2009

Title: Characterization of radical ideals, Part I
Speaker: Boris Shekhtman
Time: 3:05pm‐3:55pm
Place: PHY 109

Abstract

I will address a couple of conjectures of Tomas Sauer that naturally popped up in approximation theory:

Given a subspace \(G\) and an ideal \(J\) that complements \(G\) in \(C[x,y,\dotsc,w]\) is it true that for every subspace \(H\) of \(G\) there exists an ideal \(K\) containing \(J\) such that \(K\) complements \(H\). Sauer and Xu showed that it is so for some special radical ideals. I will prove that not only it is not true for arbitrary ideals but, in fact, this property characterizes zero-dimensional radical ideals.

I will also discuss some variations on the theme. Among them an open problem:

What subspaces \(G\) can be complemented by ideals?

Monday, March 9, 2009

Title: Recognizing sub-blocks of local picture languages
Speaker: Egor Dolzhenko
Time: 3:05pm‐4:05pm
Place: PHY 109

Abstract

Sets of rectangular arrays of symbols whose \(2\times 2\) sub-blocks belong to a predetermined set are called local picture languages. Recognizable languages are symbol-to-symbol projections of local picture languages. As such, they generalize regular languages to two dimensions. In one dimension, the set of factors of words of a local (regular) language remains local (regular). It was previously known that there are local picture languages whose sub-blocks form a non-local picture language. We will extend this result and show the existence of a local language whose factors form a language which is not recognizable.

Monday, March 2, 2009

Title: Computing the cost of Cellular Automata and Compiling Algorithms
Speaker: Apurva Bhatty
Time: 3:05pm‐4:05pm
Place: PHY 109

Abstract

Previously, I described both FSM and CA (Finite State Machine and Cellular Automaton) models of Hemoglobin function. I will describe the methods used to compose multiple cellular automata machines into a single cellular automaton, either spatially or temporally, and how to decompose a single complex cellular automaton into an equivalent ensemble of multiple simpler and smaller cellular automata. Decomposition of a complex algorithm CA or the functional composition of multiple CAs allows the “cost of computation” to be decreased, where cost is defined as a function of space (memory or number of logic gates), time (number of steps in the algorithm, the number of steps required for a stable output, or the actual “clock time” required to carry out the computations), and communication (number of wire traces between cells or the number of messages routed between processors).

I will describe the extension of this modeling method to allow for the simulation and modeling of arbitrary physical, chemical, and biological processes which are diffusion limited. Time permitting, I will describe a compiler to turn the chemical formulas into Cellular Automata to be run on general purpose Von Neumann architecture CPUs and on various specially fabricated hardware that does not use the Von Neumann architecture.

Monday, February 23, 2009

Title: A hypergraph regularity method for \(k\)-uniform hypergraphs
Speaker: Shoaib Khan
Time: 3:05pm‐4:05pm
Place: PHY 109

Abstract

In this talk we will present a proof of weak hypergraph regularity which is an extension of Szemeredi's original graph regularity lemma. The statement of the theorem follows:

For every \(\epsilon > 0\), every \(k\) and every \(m\ge 1\), there exists an integer \(M\) s.t. every \(k\)-uniform hypergraph of order (order of \(H=|V|\)) at least \(m\) admits an epsilon-regular partition \(\left\{V_0,V_1,\dotsc,V_l\right\}\) with \(m\le l\le M\).

Monday, February 16, 2009

Title: Implementing Complex Algorithms in Multi-Core and Massively Parallel Digital Signal Processors
Speaker: Apurva Bhatty
Time: 3:05pm‐4:05pm
Place: PHY 109

Abstract

Previously in this seminar series, I presented a Finite State Machine model of hemoglobin which I have designed and implemented. I will elaborate upon the algorithms used to instantiate this Finite State Automaton into \(2\)-D and \(3\)-D cellular automata along with other biological molecules. The mathematical underpinnings of Diffusion-Reaction systems modeling in cellular automata will be detailed. These algorithms and their implementation in hardware are based on the works of Toffoli and Margulis (who built the CAM processor) and Hillis (who built the Connection Machine) and electronic digital signal processing hardware for carrying out these computations with massively parallel processors.

In the second part of this talk, I will describe the historical errors made in the implementation of these algorithms and the trade-offs that will be required in re-implementing these designs in new hardware. The specific implementation of the algorithms depends upon the hardware on which they will run: the linear Von Neumann architecture, hyperthreaded cores, multiple core processors, or massively parallel hardware architectures.

The optimal implementation of complex algorithms upon these massively parallel hardware machines will be defined as existing in the trade-space of various descriptors of algorithmic complexity. The trade-offs will be described in terms of computational complexity, algorithmic complexity, space complexity, time complexity, and power consumption. The maximal, average, and optimal requirements for power, memory, and time usage will be described theoretically, along with one approach to dividing an arbitrary algorithm across multiple processing resources.

Monday, February 9, 2009

Title: Gene Rearrangements Through Assembly Graphs
Speaker: Angela Angeleska
Time: 3:05pm‐4:05pm
Place: PHY 109

Abstract

Motivated by DNA rearrangements in certain species of ciliates, we investigate spatial graphs that consist of \(4\)-valent rigid vertices, called assembly graphs. We introduce a notion of polygonal path in an assembly graph to model a single gene. The smoothing of the vertices in an assembly graph can be seen as a DNA homologous recombination. The smoothed assembly graph models the resulting molecules after gene rearrangement.

Monday, February 2, 2009

Title: Net Traversals and Net Generation, Part II
Speaker: Greg McColm
Time: 3:05pm‐4:05pm
Place: PHY 109

Monday, January 26, 2009

Title: Net Traversals and Net Generation, Part I
Speaker: Greg McColm
Time: 3:05pm‐4:05pm
Place: PHY 109

Abstract

One of the primary goals in material science is to design a crystal and then to synthesize that crystal from that design. We are developing a computer program for crystal design, and we are also developing the underlying theory for:

What is it exactly that we are describing?
What is necessary to describe it?
What constitutes a (usable description)?
Oh, yes, how does the algorithm work?

We address these and other issues.

Fall 2008

(Leader: Prof. Greg McColm)

Monday, December 1, 2008

Title: Representation of algebraic groups by simple graphs
Speaker: Joy D'Andrea
Time: 3:05pm‐3:55pm
Place: PHY 013

Abstract

In 1936, the first book on graph theory was published. It was in this book that König proposed a problem of determining all finite groups \(\Gamma\) for which there exists a graph \(G\) such that \(\operatorname{Aut}(G)\equiv\Gamma\).

In 1938, the problem was solved by Frucht. I will state Frucht's theorem and show the proof of this theorem, by using the quaternion group to go throught the proof by construction.

First, we will see the generating set for \(Q_8\) and get a Cayley color graph of this group. I will use this Cayley color graph of \(Q_8\) to got through Frucht's proof to show that the automorphism group of the resulting graph \(G\) will be isomorphic to \(Q_8\).

Monday, November 24, 2008

Title: Hypergraph regularity and quasirandomness
Speaker: Brendan Nagle
Time: 3:05pm‐3:55pm
Place: PHY 013

Abstract

Frankl and Rödl were the first to prove a \(3\)-uniform hypergraph regularity lemma suitable for proving a counting lemma. Using different arguments and different concepts of regularity, these methods were extended to \(k\)-uniform hypergraphs by Rödl, Schacht, Skokan and the speaker, by Gowers and by Tao. In this talk, we return to the \(3\)-uniform case, and consider some hypergraph regularity concepts introduced by Frankl and Rödl (\(\delta\)-regularity), by Gowers (\(\delta\)-quasirandomness) and by Haxell, Rödl and the speaker (\(\delta\)-minimality). We prove that these three concepts are, in fact, equivalent. This result implies that the \(3\)-uniform hypergraph regularity lemmas of Frankl and Rödl and of Gowers admit algorithmic versions (using that Haxell et al. proved an algorithmic regularity lemma based on \(\delta\)-minimality). We also discuss some other applications and related results. Time permitting, we briefly discuss extensions of this work to \(k\)-uniform hypergraphs, currently in progress. Joint work with A. Poerschke, V. Rödl and M. Schacht.

Monday, November 17, 2008

Title: Design and Validation of Finite State Automata Models of Active Agents and “Intelligent Agents”
Speaker: Apurva Bhatty
Time: 3:05pm‐3:55pm
Place: PHY 013

Abstract

Timing issues and information flow in cycles of networks of Deterministic and Nondeterministic Finite State Machines can create oscillations with regular rhythms, regularly irregular rhythms, or irregularly irregular rhythms, i.e., arrhythmias. The proper selection and design of states, transitions, and model environments (e.g., Cellular Automata, Lattice Gas, Lattice Boltzmann) is necessary to create valid models of phenomena in gas, liquid, and solid media (all three of which are integral to models of computational biophysics, and useful in computational behavioural and cognitive models, and computational control systems). Biophysically sound models of rhythm generation can be used to construct novel diagnostic and therapeutic approaches. These models and formal languages can be tested in silico to quantify their ability to recognize and treat arrythmias in the heart, brain, and other excitable biologic tissues. Examples will be provided in Biomedicine, Gas Transport Dynamics in Fluids and Gases, and Computational Biophysics and Chemistry (e.g., Hemoglobin), ending in the philosophical question of what levels of interaction and action are necessary and sufficient to constitute “agency” and “intelligent agents”.

Monday, November 10, 2008

Title: From the Jones Polynomial to Khovanov Homology, Part II
Speaker: Mohamed Elhamdadi
Time: 3:05pm‐3:55pm
Place: PHY 013

Monday, November 3, 2008

Title: From the Jones Polynomial to Khovanov Homology, Part I
Speaker: Mohamed Elhamdadi
Time: 3:05pm‐3:55pm
Place: PHY 013

Abstract

In 1984, V. Jones introduced a polynomial invariant of knots as a result of investigations of Von Neumann algebras. Using state models introduced by Lou Kauffman in 1987 we will define combinatorially the bracket polynomial which has the Jones polynomial as a specialization. We will then move from the bracket polynomial to Khovanov homology (introduced in 1999) which is a stronger invariant of knots than the Jones polynomial. Explicit examples of calculations will be provided.

Monday, October 20, 2008

Title: Beyond Cellular Automata, Part III
Speaker: W. Richard Stark
Time: 3:05pm‐3:55pm
Place: PHY 013

Monday, October 13, 2008

Title: Beyond Cellular Automata, Part II
Speaker: W. Richard Stark
Time: 3:05pm‐3:55pm
Place: PHY 013

Monday, October 6, 2008

Title: Beyond Cellular Automata, Part I
Speaker: W. Richard Stark
Time: 3:05pm‐3:55pm
Place: PHY 013

Abstract

Asynchronous computation occurs naturally in networks. It is seen as being intractable because it leads to computations which branch. If the computations are allowed to continue forever, then a single computation is a sequence of global states analogous to a decimal representing a real number, and a property of computations is a measurable set. This leads to applications of Lebesgue integration over the set of all computations — e.g., an integral can evaluate to the expectation of a property.

I will begin by (1) presenting examples, then (2) presenting an example of a process which solves its problem faster when its components are slowed down, and finally (3) end by describing indefinite integrals over the computation space.

Monday, September 29, 2008

Title: On reporter strands in DNA-based graph structures
Speaker: Nataša Jonoska
Time: 3:05pm‐3:55pm
Place: PHY 013

Abstract

Through self-assembly of branched junction molecules many different DNA structures (graphs) can be assembled. We show that every multigraph can be assembled by DNA such that there is a single strand that traces each edge in the graph at least once. This strand corresponds to a boundary component of a two-dimensional orientable surface that has the given graph as a deformation retract. This boundary component traverses every edge at least once, and it defines a circular path in the graph that “preserves the graph structure” and traverses each edge once or twice, if an edge is visited twice, then this is done in opposite directions.

Monday, September 22, 2008

Title: Crystal Nets III: Edge Transitivity
Speaker: Greg McColm
Time: 3:05pm‐3:55pm
Place: PHY 013

Abstract

This spring, I wrote a computer program that looks for “edge transitive” “binodal” crystal nets. We look at how it works ... and edge transitive binodal crystal nets I found. We will also discuss the “so what?” issue that arose in the recent ICMR Workshop on the Design and Synthesis of New Materials.

Monday, September 15, 2008

Title: Crystal Nets II: Edge Transitivity
Speaker: Greg McColm
Time: 3:05pm‐3:55pm
Place: PHY 013

Abstract

One of the goals of material science is engineering new solids; this means designing such solids in advance of synthesis. In particular, this means generating mathematical descriptions of the novel crystals one desires to manufacture. Here we will look at three of the extant methods for generating crystal nets using geometry; one of these will be a method developed by Edwin Clark and myself.

Monday, September 8, 2008

Title: Crystal Nets I: Edge Transitivity
Speaker: Greg McColm
Time: 3:05pm‐3:55pm
Place: PHY 013

Abstract

As far as I know, Democritus was the first to propose representing solids (like crystals) as graph-like objects, with atoms as vertices and bonds as edges. But ninety years since the first Nobel was handed out for graph theory, almost all mathematical work on the subject goes back only a few decades. This will be a brief introduction to and overview of crystal nets.

Spring 2008

(Leader: Prof. Greg McColm)

Monday, April 14, 2008

Title: Isomorphisms of Subconstituent Algebras
Speaker: Ibtisam Daqqa
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

We compare several notions of isomorphism for subconstituent algebras. We use Latin Squares and their subconstituent algebras as a source of examples and counter examples.

Monday, April 7, 2008

Title: Irreducibility of Commuting Matrices
Speaker: Boris Shekhtman
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

There is an old theorem of Motzkin and Tausski that states that the variety of pairs of \(N\times N\) commuting matrices is irreducible and has dimension \(N\). For three or more commuting matrices it is not so.

There is an open problem: If the dimension of variety of \(k\) \(N\times N\) matrices has dimension \(N\), does it imply that the variety is irreducible? In the talk I will present an elementary proof (joint with Carl de Boor) of the result of Motskin-Tausski, I will present a counterexample to the aforementioned open problem and discuss a number of related open questions.

Monday, March 31, 2008

Title: Certain diagonal equations over finite fields
Speaker: Xiang-dong Hou
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

Let \(p\) be an odd prime, \(q=p^n\), \(F_q\) the finite field of order \(q\) and \(F^*_q\) the multiplicative group of \(F_q\). A function \(f\) from \(F_q\) to \(F_q\) is called planar if for every \(u\) in \(F^*_q\), the function \(f(x+u)-f(x)\) is a permutation of \(F_q\). A construction of planar functions requires the answer to the following question: Assume \(t\) divides \(n\). Can every element of \(F^*_q\) be written as a sum of two \(\left(p^{n/t}-1\right)\)st powers in \(F^*_q\)?

When \(t=1\), the answer is trivially “no”.

When \(t=2\), the answer is no except when \(q=9\). (Simple counting)

When \(t>3\), the answer is “yes”. This follows from a well known estimate of the number of solutions of diagonal equations in terms of Gauss sums.

When \(t=3\), the answer is still “yes”, but the proof requires a new approach.

Monday, March 24, 2008

Title: The volume of the smallest tetrahedron among \(n\) points in the unit cube
Speaker: Niluk John
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

This is a generalization of the Heilbronn problem from two dimensions to three dimensions, which can be defined as follows. For any configuration \(S\) of \(n\) points in the unit cube \([0,1]^3\), let \(T(S)\) be the volume of the smallest tetrahedron. The \(3\)D Heilbronn's problem is about determining $$ \Delta(n)=\max T(S) $$ where the maximum is taken over all possible configuration \(S\) of \(n\) points in \([0,1]^3\). It has been proved that \(n^{-3}\log\,n\ll\Delta(n)\). We shall discuss the lower bounds for \(\Delta(n)\) by using two different methods. One is using an incremental construction which gives a bound \(n^{-3.33}\ll\Delta(n)\), and other is using a probabilistic construction which gives a bound \(n^{-3}\ll\Delta(n)\). The incremental construction methods were used by W. M. Schmidt in 1971, and the probabilistic construction is from N. Alon and J. Spencer's probabilistic methods and later generalized by G. Barequet for higher dimensions.

Monday, March 3, 2008

Title: A Game-Theoretic Model of the Evolution of Random Structures: More Semigroups & Thresholds
Speaker: Greg McColm
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

Several years ago, Dimitris Achlioptas proposed the following model of the evolution of random graphs. Start with a graph \(G_{n,0}\) of \(n\) isolated vertices, and repeat the following:

Given the graph \(G_{n,m}\) of size \(m\), randomly and uniformly select a pair of pairs of vertices \(\{u,v\}\) and \(\{x,y\}\), where neither pair represents an edge in \(G_{n,m}\).
A player then chooses which pair to add an edge to to get a graph \(G_{n,m+1}\).
Go to (1).

Repeat until the graph satisfies a monotone increasing property of graphs.

We generalize this question to the semigroup model of random processes, and to two-player games (between a Radical who wants to satisfy the property as soon as possible, and a Conservative who wants to delay the satisfaction of the property); using Zermelo's Theorem, we can get (somewhat) optimal strategies for the Conservative and the Radical. We then ask: given (ensembles of somewhat) optimal strategies, do monotone increasing properties necessarily admit weak thresholds? We find that even phrasing the question properly is complicated, but phrased in just the right way, the answer is “yes”.

Monday, February 18, 2008

Title: Some Connections Between Classical Computational Complexity and Quantum Computing, Part II
Speaker: Rahul Tripathi, USF Computer Science & Engineering
Time: 3:00pm‐4:00pm
Place: PHY 108

Monday, February 11, 2008

Title: Some Connections Between Classical Computational Complexity and Quantum Computing
Speaker: Rahul Tripathi, USF Computer Science & Engineering
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

I will be giving two talks on computational complexity theory in consecutive weeks. In these talks, I plan to do the following: I will cover some basic concepts in classical complexity theory. I will also introduce few important rules that govern quantum computation and that are relevant for this talk. Next, I will show certain applications of quantum computational techniques in solving classical complexity problems. Some of these applications are from my recent work.

These applications demonstrate that quantum computing not only offers a possibility for an emerging technology but also provides useful mathematical tools to understand classical computation.

I will try to make the talk self-contained and accessible to people with little background in computational complexity theory.

Monday, February 4, 2008

Title: One-Parameter Generalizations of the Fibonacci and Lucas Numbers
Speaker: Mourad Ismail, University of Central Florida
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

The Hilbert matrix \(a_{i,j}=1/(i+j+1)\) plays an important role in numerical analysis. It's inverse has integer entries. We give one-parameter generalizations of the Fibonacci and Lucas numbers denoted by \(\{F_n(\theta)\}\) and \(\{L_n(\theta)\}\), respectively. We evaluate the Hankel determinants with entries \(\{1/F_{j+k+1}(\theta):0\le i,j\le n\}\) and \(\{1/L_{j+k+1}(\theta):0\le i,j\le n\}\). We also find the entries in the inverse of \(\{1/F_{j+k+1}(\theta):0\le i,j\le n\}\) and show that all its entries are integers. Some of the identities satisfied by the Fibonacci and Lucas numbers are extended to more general numbers. All integer solutions to three diophantine equtions related to the Pell equation are also found.

Monday, January 28, 2008

Title: Towards the Hypergraph Regularity Method, Part II
Speaker: Brendan Nagle
Time: 3:00pm‐4:00pm
Place: SOC 256

Abstract

In the last Fall 2007 session of the Discrete Math Seminar, the speaker introduced some of the complexities involved with various notions of hypergraph regularity. In this talk, we attempt to resolve some of these technicalities.

Fall 2007

(Leader: Prof. Greg McColm)

Monday, December 3, 2007

Title: Towards the Hypergraph Regularity Method
Speaker: Brendan Nagle
Time: 3:00pm‐4:00pm
Place: PHY 109

Abstract

In this talk, we begin to present a hypergraph extension of Szemeredi's Regularity Lemma for graphs. In particular, we reveal some of the technicalities that arise in such an extension, namely, in finding a suitable hypergraph regularity lemma that admits a corresponding hypergraph counting lemma. We also discuss some applications.

Monday, November 26, 2007

Title: Entropy of the transducer generated two dimensional languages
Speaker: Egor Dolzhenko
Time: 3:00pm‐4:00pm
Place: PHY 109

Abstract

Transducers are finite state automata with an output. To each transducer \(\tau\) we can associate a two-dimensional language \(L^2(\tau)\), consisting of blocks of symbols in the following way. The first row, \(w\), of each block is in the input language of \(\tau\), the second row is a word that \(\tau\) outputs on input \(w\). Inductively, every subsequent row is a word outputted by the transducer when its preceding row is read as an input. We show a relationship of the entropy values of these two-dimensional languages to the entropy values of the one-dimensional languages which can be the input language of \(\tau\).

Monday, November 19, 2007

Title: Rational Power Series
Speaker: Xiang-dong Hou
Time: 3:00pm‐4:00pm
Place: PHY 109

Abstract

Let \(F\) be a field and \(n>0\). A power series \(f\in F\left[\left[x_1,\dotsc,x_n\right]\right]\) is called rational if \(f=h/g\) for some \(g,h\in F[x_1,\dotsc,x_n]\) with \(g(0,\dotsc,0)\ne 0\), i.e., if there exists \(g\in F[x_1,\dotsc,x_n]\) with \(g(0,\dotsc,0) \ne 0\) such that \(gf\in F[x_1,\dotsc,x_n]\). We prove that in this definition, the condition \(g(0,\dotsc,0) \ne 0\) can be replaced with a weaker condition \(g\ne 0\). This is obvious when \(n=1\). When \(n\ge 2\), however, the problem is more subtle. Our proof uses valuations in fields of algebraic functions of one variable.

Monday, October 29, 2007

Title: A Symmetry Approach to the Three-dimensional Structure of Simple Viruses
Speaker: Reidun Twarock, University of York, Heslington, York, UK
Time: 3:00pm‐4:00pm
Place: PHY 109

Abstract

An important part of a virus is its protein container, called the viral capsid, that encapsulates and hence provides protection for the viral genome. Based on the observation that the capsids of most viruses are organized with icosahedral symmetry, Caspar and Klug introduced a landmark theory in 1962 in which they predicted the locations of the proteins in viral capsids schematically based on triangulations that are compatible with icosahedral symmetry. However, information on the structures of the capsid proteins and on the organization of the genomic material is inaccessible with their approach. We show here that such information can be obtained via an extension of the symmetry principle underlying their theory. Based on various examples we demonstrate that the material boundaries in simple RNA viruses are completely determined at all radial levels from the capsid area down to the innermost RNA by our new symmetry principle, implying that symmetry is more important in virus architecture than previously appreciated. We conclude by an analysis of the RNA cage structures formed by the viral genome in certain classes of viruses and discuss implications on virus assembly.

Monday, October 22, 2007

Title: Threshholds in the Evolution of Random Structures, Part II
Speaker: Greg McColm
Time: 3:00pm‐4:00pm
Place: PHY 109

Abstract

I will continue the talk from last time, when I presented a monoid-based meta-model of (upwards) evolution of random structures organized around the notion of a stopping time, which for any desirable property is the time when the given random graph acquires that property. Last week, I looked at models where the distribution of increments doesn't change; this week, I will recap last week and then look at more complicated models (of evolution of random structures) where the distribution of increments changes.

Monday, October 15, 2007

Title: Threshholds in the Evolution of Random Structures, Part I
Speaker: Greg McColm
Time: 3:00pm‐4:00pm
Place: PHY 109

Abstract

One of the basic notions in random graph theory is the evolution of a random graph; one of the fundamental questions is the question of when the randomly-evolving graph acquires a desired property. There are many extant models of evolution of random structures, and recently there have appeared several meta-models to try to organize them. In these two talks, I present one such meta-model, organized around the notion of a stopping time, which for any desirable property is the time when the given random graph acquires that property.

I will outline the mechanics of estimating stopping times, and the first issue will be how good our estimates are. In random graph theory, the width of the range of probable stopping times is the width of the threshold; in the literature, thresholds are usually weak or coarse (the width is on the same order as the median stopping time itself) or strong or sharp (the width shrinks without bound with respect to the median of the threshhold). I will present a formalism of the widths, which is useful in getting well-defined theorems.

I will then describe the semantics of the situation: the evolving random structure is actually a trajectory through a particularly nice semigroup; I will look at this notion of niceness and some examples. I will then use the above-mentioned formalism of the widths to get an infinite hierarchy of width measurements, from ultra-weak to ultra-strong. I will reintroduce a theorem on models for which all stopping times have (at least) weak thresholds, and then I will describe how to get a width of one threshhold on one process by simulating that process with another process having a threshhold whose width one already knows.

Monday, October 8, 2007

Title: Single Generated \(3\)-Periodic Nets, Part II
Speaker: W. Edwin Clark
Time: 3:00pm‐4:00pm
Place: PHY 109

Abstract

Using just the blackboard and chalk, I will show how to find the angles used to generate the singly-generated \(3\)-periodic nets discussed last week. Strictly speaking, this talk will be self-contained and not depend on the previous talk. The main tool is the so-called “Crystallographic Restriction” which says that if one has an isometry \(\varphi:x\to R(x)+b\) of Euclidean \(3\)-space where \(R\) is a rotation and \(b\) is a fixed vector and \(\varphi\) induces a graph automorphism of a \(3\)-periodic net then the angle of rotation is \(2\pi/n\) where \(n=1,2,3,4\) or \(6\).

Monday, October 1, 2007

Title: Single Generated \(3\)-Periodic Nets
Speaker: W. Edwin Clark
Time: 3:00pm‐4:00pm
Place: PHY 109

Abstract

“\(3\)-periodic net” is an embedding of a graph in \(\mathbb{R}^3\) (Euclidean \(3\)-space) with the following properties:

Vertices are represented by points in \(\mathbb{R}^3\).
Edges are represented by straight line segments.
The set of vertices is a discrete subset of \(\mathbb{R}^3\), that is, there is positive number \(r\) such that the distance between any two vertices is more than \(r\).
There are three independent translations of \(\mathbb{R}^3\) that induce automorphisms of the graph represented by the net.

A \(3\)-periodic net \(N\) is “singly generated” if there is a group \(G\) of isometries of \(\mathbb{R}^3\) generated by \(n\) involutary isometries \(f[1],\dotsc,f[n]\) of \(\mathbb{R}^3\) so that the orbit of the origin: \(G0:=\{g(0):g\text{ in }G\}\) is the set of vertices of \(N\) and the edges of \(N\) are the line segments joining pairs \(\{g(0),gf[i](0)\}\), \(g\) in \(G\) and \(i=1,\dotsc,n\). Hence \(N\) is a homomorphic image of the Cayley graph of \(G\) with generator set \(\{f[1],\dotsc,f[n]\}\). Not all such nets are \(3\)-periodic. The problem is to pick the isometries so that the corresponding net is \(3\)-periodic. I will show how to find some such \(f[i]\)'s using geometric figures including some regular polygons, some Platonic and Archimedean solids, and perhaps a few other methods.

[“Singly generated” comes from the fact that the examples we have so far are each “generated” by a single polygon or polyhedron.]

Historical Comment: Although the idea of singly-generated nets seems to be original, chemists have been studying and classifying \(3\)-periodic nets at least since a series of papers by A. F. Wells [1954 to 1976] and his book “Three-Dimensional Nets and Polyhedra” in 1977. More recently much in this area has been done by various chemists including Mohamed Eddaoudi in the USF Chemistry Department, Michael O'Keeffe, O. M. Yaghi and the German mathematicians Delgado-Friedrichs, Andreas Dress, and Daniel Huson. However almost all papers on the subject have appeared in the chemical or crystallographic literature and the classification problem for \(3\)-periodic nets so far as we can tell is not well-known in mathematical circles.

Monday, September 24, 2007

Title: The Subconstituent Algebra of a Latin Square
Speaker: Ibtisam Daqqa
Time: 3:00pm‐4:00pm
Place: PHY 109

Abstract

We describe the subconstituent algebra \(T(p)\) of the Bose-Mesner algebra of a Latin square with respect to any base point \(p\). We show that \(T(p)\) is isomorphic as an abstract algebra to \(\mathbb{M}_5+\mathbb{M}_6^{n-2}+\mathbb{M}_1^{n^2-6n+7}\), where \(\mathbb{M}_k\) denotes the complex algebra of \(k\times k\) complex matrices and the exponents give the multiplicity of each summand.

Monday, September 17, 2007

Title: A bilinear form for tridiagonal pairs of \(q\)-Serre type
Speaker: Brian Curtin
Time: 3:00pm‐4:00pm
Place: PHY 109

Abstract

Let \(V\) denote a vector space of finite, positive dimension, and let \(V^*\) denote the vector space dual of \(V\). Let \(A_1,A_2\) be a tridiagonal pair on \(V\), and let \(B_1,B_2\) be linear transformations from \(V^*\) to \(V^*\) such that for all \(\nu\) in \(V\) and \(f\) in \(V^*\), $$ B_1 f(\nu)=f\left(A_1\nu\right)\text{ and } B_2 f(\nu)=f\left(A_2\nu\right). $$

We show that \(B_1,B_2\) is a tridiagonal pair on \(V^*\). We then show that if \(A_1,A_2\) is of \(q\)-Serre type, then \(B_1,B_2\) is isomorphic to \(A_1,A_2\). We also show that in this case there exists a unique bilinear form on \(V\) such that for all \(u,\nu\) in \(V\), $$ \left\langle A_1 u,\nu\right\rangle = \left\langle u,A_1\nu\right\rangle \text{ and } \left\langle A_2 u,\nu\right\rangle = \left\langle u,A_2\nu\right\rangle. $$

Monday, September 10, 2007

Title: Leonard Triples
Speaker: Brian Curtin
Time: 3:00pm‐4:00pm
Place: PHY 109

Abstract

Let \(V\) denote a vector space of finite positive dimension. We call a triple of elements from \(\operatorname{End}(V)\) a Leonard triple whenever for each choice of element there is a basis of \(V\) with respect to which the matrix representing the chosen element is diagonal and the matrices representing the other two are irreducible tridiagonal. We discuss the classification of Leonard triples.

Spring 2007

(Leader: Prof. Greg McColm)

Monday, April 23, 2007

Title: The dynamics of icosahedral viruses: what does Viral Tiling Theory teach us?
Speaker: Anna Taormina, Durham University, United Kingdom
Time: 3:00pm‐4:00pm
Place: PHY 120

Abstract

I shall give a brief review of key aspects of Viral Tiling Theory and exploit the symmetry properties of viruses whose protein shell is invariant under the icosahedral group \(H_3\), with a view to provide biologists with predictions on the normal modes of vibration of such viruses and assist them, for instance, in their study of mechanisms of genetic material release during viral replication.

Monday, April 16, 2007

Title: Assembly Graphs
Speaker: Angela Angeleska
Time: 3:00pm‐4:00pm
Place: PHY 120

Abstract

Motivated by problems in gene recombination observed in ciliates, we define assembly graphs as a finite graphs with rigid vertices of degree four and even number of vertices of degree one. We investigate certain properties and applications of assembly graphs, such as: the assembly number, smoothing, Hamiltonian and polygonal paths. Also some results for words associated with assembly graphs are presented.

Monday, April 9, 2007

Title: Graphs With Few Triangles
Speaker: Brendan Nagle
Time: 3:00pm‐4:00pm
Place: PHY 120

Abstract

In 1978, Ruzsa and Szemerédi proved that if a graph \(G\) has few triangles, then it is possible to remove relatively few edges from \(G\) to destroy all of its triangles. This result, dubbed the ‘triangle removal lemma’, quickly implies some deep results from combinatorial number theory and geometry, including Roth's Theorem on arithmetic progressions of length \(3\). In this talk, we shall consider some of these applications and will discuss the proof of the triangle removal lemma. We attempt to motivate recent work of the speaker and others concerning extending the triangle removal lemma to hypergraphs, and hope to introduce some of the technicalities that arise in such an extension.

Monday, April 2, 2007

Title: Kauffman-Harary Conjecture for Virtual Knots
Speaker: Matt Williamson
Time: 3:00pm‐4:00pm
Place: PHY 120

Note: Defense of Master's Thesis

Abstract

In this talk, I will present some basics of virtual knot theory, leading into a conjecture called the Kauffman-Harary Conjecture. This conjecture was proved to be true for many classical knots, and I present a type of virtual knot diagram where it is true as well. Furthermore, I use a move called a \(k\)-swap throughout the talk and I show that it does not change the involutory quandle.

Thursday, March 29, 2007

Title: Skew Hadamard difference sets from commutative semifields and symplectic spreads
Speaker: Qing Xiang, University of Delaware
Time: 2:00pm‐3:00pm
Place: LIF 261

Note: Special Seminar

Abstract

Let \(G\) be a finite group of order \(v\) (written multiplicatively). A \(k\)-element subset \(D\) of \(G\) is called a \((v,k,\lambda)\) difference set if the list of “differences” \(xy^{-1}\), \(x,y\in D\), \(x\ne y\), represents each nonidentity element of \(G\) exactly \(\lambda\) times. Let \(q\) be a prime power congruent to \(3\) modulo \(4\). The set of nonzero squares of \(\mathrm{GF}(q)\) is a \((q,\frac{q–1}{2},\frac{q–3}{4})\) difference set in \((\mathrm{GF}(q),+)\). This construction dates back to 1933, and it is due to Paley. The difference sets coming from this construction are usually called Paley difference sets.

A difference set \(D\) in a finite group \(G\) is called skew Hadamard if \(G\) is the disjoint union of \(D\), \(D^{(-1)}\), and \(\{1\}\), where \(D^{(-1)}=\{d^{-1}:d\in D\}\). The Paley difference sets provide a family of examples of skew Hadamard difference sets. For more than 70 years, these were the only known examples in abelian groups. It was conjectured that no further examples in abelian groups can be found. This conjecture was disproved by Ding and Yuan in 2005. Subsequently, we found another construction using certain permutation polynomials from the Ree-Tits slice symplectic spreads in \(\mathrm{PG}(3,3^{2h+1})\). In this talk, we will discuss these developments and raise several questions about skew Hadamard difference sets.

Monday, March 26, 2007

Title: Area of the smallest triangle among \(n\) points in the unit square
Speaker: Niluk John
Time: 3:00pm‐4:00pm
Place: PHY 120

Abstract

The Heilbronn problem is defined as follows.

Given a configuration \(F\) of \(n\) points in the unit square \([0,1]^2\), let \(T(F)\) be the area of the smallest triangle. And Heilbronn's problem is about determining \(T(n)=\max T(F)\), where the maximum is taken over all possible configuration \(F\) of \(n\) points in \([0,1]^2\). We shall give a review of this problem and the existing upper and lower bounds for \(T(n)\).

We shall also discuss the average case, where the \(n\) points are independent and uniformly distributed on \([0,1]^2\).

Monday, February 28, 2007

Title: The chromatic polynomial of graphs as the Euler characteristic
Speaker: Masahico Saito
Time: 3:00pm‐4:00pm
Place: PHY 120

Abstract

This talk is a brief overview of the work by Helme-Guison and Rong on a categorification of the chromatic polynomial of graphs. The chromatic polynomial counts the number of colorings of vertices such that colors are distinct when two vertices are connected by edges. The categorification, in this case, means that the chromatic polynomial can be regarded as the Euler characteristic, the famous topological formula for polyhedrons: \([(\text{# of vertices})-(\text{# of edges})+\dotsb]\).

My motivation of this review is for possible applications to DNA recombinations and other situations.

Monday, February 12, 2007

Title: An analogue of conjugation of groups for Hopf algebras and representations of braid groups
Speaker: Masahico Saito
Time: 3:00pm‐4:00pm
Place: PHY 120

Abstract

The conjugation \((x,y)\to y^{1}xy\) of groups are related to braid groups by assigning a mapping \((x,y)\to (y,y^{1}xy)\) to a braiding.

In this talk, an analog of conjugation is defined for Hopf algebras that are vector spaces with multiplication and some other structures, which I will explain by pictures. Such an analog of conjugation gives braid group representations on vector spaces, that have been of interest for physicists by the name “Yang-Baxter equation”.

The talk is an exposition of facts known to algebraists and mathematical physicists since the 1990’s, from a topological and combinatorial point-of-view of knots and braids. In particular, linear maps are represented by graphs, and matrix equations are proved by pictures.

Monday, February 5, 2007

Title: Does the Number Seven “Exist”?
Speaker: Greg McColm
Time: 3:00pm‐4:00pm
Place: PHY 120

Abstract

Ever since Pythagoras, the philosophy of mathematics has been a spectrum from Realism — the contention that mathematical objects like The Number Seven actually “exist” — and various anti-realists, who contend that the Number Seven is a social convention. This will be an outline of the debate from Pythagoras to the present, and its implications for the practice of mathematics … and of science in general.

Monday, January 22, 2007

Title: Rigid Structures
Speaker: Greg McColm
Time: 3:00pm‐4:00pm
Place: PHY 120

Abstract

A class of complex structures constructible from simple building blocks can be described as follows. Start with a diagram giving the articulation possibilities of the various types of blocks. This diagram can be used to devise a semigroup of all possible (relative) positions of different blocks in a complex. If we want to embed the complex in a geometric space (such as Euclidean space), we can do this block by block. By imposing restrictions the (use of) the semigroup, we can capture the notion of the complex being rigid, and of the blocks not being able to occupy the same space. This is joint work with Nataša Jonoska.

Monday, January 8, 2007

Title: From Potts to Tutte and Back Again… A Graph Theoretic View of Statistical Mechanics
Speaker: Jo Ellis-Monaghan, St. Michaels Collegem
Time: 3:00pm‐4:00pm
Place: PHY 120

Abstract

This talk will provide basic principles of the Ising and \(q\)-state Potts model partition functions of statistical mechanics. These models play important roles in the theory of phase transitions and critical phenomena in physics and have applications as widely varied as muscle cells, foam behaviors, and social demographics. The Potts model is constructed on various lattices, and when these lattices are viewed as graphs (i.e., networks of nodes and edges) then, remarkably, the Potts model is also equivalent to one of the most renown graph invariants, the Tutte polynomial. Thus, the talk will also give a general introduction to the Tutte polynomial. The Tutte polynomial is the universal object of its type, in that any invariant that obeys a certain deletion/contraction relation (or, equivalently, a particular state-model formulation) must be an evaluation of it. The talk includes a (very brief) history and some interesting properties of the Potts model partition function and Tutte polynomial, but the emphasis will be on how the Potts model and Tutte polynomial are related and how research into one has informed the theory of the other, and vice-versa. The talk includes computational complexity results and a brief excursion into Monte Carlo simulations.

Fall 2006

(Leader: Prof. Greg McColm)

Monday, December 4, 2006

Title: Hurwitz Equivalence in Tuples of Generalized Quaternion Groups and Dihedral Groups
Speaker: Xiang-dong Hou
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

Let \(Q_2m\) be the generalized quaternion group of order \(2^m\) and \(D_N\) the dihedral group of order \(2N\). We classify the orbits in \(\left(Q_2m\right)^n\) and \((D_pm)^n\) \(\left(p'\right)\) under the Hurwitz action.

Monday, November 27, 2006

Title: Questions About Dynamics of Membrane Systems
Speaker: Giuditta Franco
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

Membrane systems were introduced in 1998 as a distributed computational model inspired by the structure and the functioning of the living cell. Their computational power has been extensively investigated, while their feasibility as models of cellular and biochemical processes is lately receiving an increasing interest. In this context, it is still an open problem to find a suitable mathematical setup to describe membrane systems as (discrete) dynamical systems. Two possible approaches will be suggested, one based on linear operators (so called “stoichiometric matrices”) and the other one based on symbolic dynamics.

Monday, November 20, 2006

Title: Subconstituent algebras of Latin square
Speaker: Ibtisam Daqqa
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

In this talk we are going to define a subconstituent algebra \(T(p)\) of a Latin square \(L\) with respect to a base point \(p\). We will introduce the cycle structure of \(L\) with respect to \(p\). And see how one can span a \(T\)-module using a given cycle of order \(k\). This cycle structure will play an important role in determining the isomorphism classes of \(T(p)\).

Monday, November 13, 2006

Title: String Pointer Reduction System: Formalization of gene assembly in ciliates
Speaker: Angela Angeleska
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

In this talk we give a short overview of a combinatorial model for DNA recombination in ciliates which are the unicellular organisms characterized by the presence of two nuclei in a single cell (macronucleus MAC and micronucleus MIC).

The assembly of MIC-gene into MAC-gene in ciliates might be viewed as a composition of three molecular operations that can be formalized through string rewriting rules. The string rewriting rules define a String Pointer Reduction System, which describes every posible gene recombination observed in rearrangements from MIC into MAC genes.

Monday, November 6, 2006

Title: Building Block Approach to Porous Materials
Speaker: Mohamed Eddauodi, Chemistry Department, USF
Time: 3:00pm‐4:00pm
Place: PHY 108

Monday, October 30, 2006

Title: The Spectrum of a Pot With DNA Molecules and Related Problems
Speaker: Ana Staninska
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

A theoretical model of DNA self-assembly will be presented. For this model a problem is encoded in the molecules in the pot and a solution is represented by a complete complex (a complex that does not contain free sticky ends) of appropriate size.

In most experiments, a lot of useless material (non-complete complexes) also appears. To optimize the initial solution so as to minimize the amount of useless material at the end one needs to use proper proportion of molecule types. The set of vectors representing these proper proportions is called the “spectrum” of the pot.

The spectrum reveals much more information about the pot with DNA molecules, than just giving the proper proportion. It helps to classify the pots and to determine the minimal complete complexes.

I will present some already proved facts as well as problems that I am currently working on.

Monday, October 23, 2006

Title: Minimal Generators of Zero-Dimensional Ideals
Speaker: Boris Shekhtman
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

Let \(F[x]\) be the ring of polynomials in \(d\) variables over the real or complex field \(F\). A zero-dimensional ideal is an ideal in \(F[x]\) of finite codimension (colength). I present bounds for the minimal number of generators for such ideals and “extreme cases”, that is the cases where bounds are actually archived. These questions popped up naturally (believe it or not) in Analysis.

Monday, October 16, 2006

Title: Coloring Random Knots
Speaker: Enver Kardayi
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

I will discuss creating a random knot and computing its Determinant by using Maple and the distribution of non-trivial and \(p\)-colorable random knots for different stick numbers.

Monday, September 25, 2006

Title: Isomorphisms and homeomorphisms of graphs
Speaker: Dr. Brian Curtin
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

We show that the isomorphism class of a graph \(G\) is determined by the set \(\{(H,n)\mid H\text{ is a graph, }n\text{ is the number of homomorphic images of }H\text{ in }G\}\). We use partition functions to encode the computation of \(n\) into a polynomial, and then use some elementary invariant theory to study these polynomials.

Monday, September 18, 2006

Title: Blueprints for Very Tiny Structures, Part II
Speaker: Greg McColm
Time: 3:00pm‐4:00pm
Place: PHY 108

Monday, September 11, 2006

Title: Blueprints for Very Tiny Structures
Speaker: Greg McColm
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

With chemists designing crystals, computer scientists carrying out DNA computations, and pharmacists creating new proteins, lots of scientists are now building nanostructures. Presumably, such architectural planning would involve blueprints of the final building. We present an algebraic system for such blueprints, and look at examples.

Spring 2006

(Leader: Prof. Greg McColm)

Monday, April 24, 2006

Title: On the Number of Inequivalent Binary Self-Orthogonal Codes
Speaker: Xiang-dong Hou
Time: 10:00am‐10:50am
Place: PHY 109

Abstract

Let \(\Psi k,n\) denote the number of inequivalent binary self-orthogonal \([n,k]\) codes. We present a method which allows us to compute \(\Psi k,n\) explicitly for a moderate \(k\) and an arbitrary \(n\). Included in this talk are explicit formulas for \(\Psi k,n\) with \(k\le 5\).

Monday, April 17, 2006

Title: Spatial Graphs and Chemistrys
Speaker: Enver Kardayi
Time: 10:00am‐10:50am
Place: PHY 109

Abstract

We will talk about spatial graphs and chromatic polynomials. We will go over Bing's conjecture about complete graphs and Yamada Polynomials. Finaly, we will discuss the chirality of spatial graphs.

Monday, April 10, 2006

Title: Forbidding-enforcing graphs
Speaker: Daniela Genova
Time: 10:00am‐10:50am
Place: PHY 109

Abstract

We propose a new way of defining classes of graphs based on boundary conditions. Forbidding conditions state that certain combinations of subgraphs are forbidden in a graph and enforcing conditions state that certain subgraphs induce larger subgraphs in the graph structure. A “forbidding-enforcing family” of graphs is specified as the set of graphs that satisfy such forbidding and enforcing conditions. The talk will include examples and some properties of these families.

Monday, April 3, 2006

Title: Bose-Mesner algebra from Latin square
Speaker: Ibtisam Daqqa
Time: 10:00am‐10:50am
Place: PHY 109

Abstract

We recall Latin square and a construction of a Bose-Mesner algebra from a Latin square. We show that this Bose-Mesner algebra has the so-called amorphous property.

Monday, March 27, 2006

Title: A graphic representation of a pot with DNA molecules
Speaker: Ana Staninska
Time: 10:00am‐10:50am
Place: PHY 109

Abstract

Junction DNA molecules with flexible branches self-assemble into larger complexes using weak hydrogen bonds. We approach this self-assembly process form a graph theoretical point-of-view. Given a pot of molecules, we assign a starlike graph to every molecule, a labeled multigraph to the complexes that can arise from the pot, and a labeled multigraph to the pot itself. This representation is used to determine what complexes can assemble from the molecules in the given pot.

Monday, March 20, 2006

Title: Breaking Highgrade Ciphers in World War II: Working With Alan Turing
Speaker: Peter Hilton, Distinguished Professor Emeritus, Oxford University
Time: 10:00am‐10:50am
Place: LIF 268

Abstract

I will reminisce about the experience of working on the German Naval Enigma and Geheimschreiber (“Secret Writer”) during World War II. Concentrating on the Patter — the most sophisticated German coding machine — I will describe how the Germans made very serious mistakes which enormously facilitated our work.

I will also talk about the great logician Alan Turing, whose contribution to breaking Enigma was unique and decisive.

Monday, March 6, 2006

Title: Quandle Cocycle Invariants and Tangle Embeddings
Speaker: Kheira Ameur
Time: 10:00am‐10:50am
Place: PHY 109

Abstract

Quandles are sets with self-distributive binary operations that generalize the Fox-\(n\) colorings. A quandle coloring along with a quandle cocycle can be used to define invariants for knots and knotted surfaces.

For some Alexander quandles we contruct polynomial type cocycles, we then use them to compute invariants for certain families of knots and their twist-spins. An interesting application is tangle embedding, where the cocycle invariant can be used as obstructions to embedding tangles in knots. We will define the cocycle invariant for tangles, and then compute the invariant for some tangles. By comparing the invariant values, informations can be obtained in which knots a given tangle can be embedded.

Monday, February 27, 2006

Title: A Generalized Urn Model, Part II
Speaker: Kevin Wagner
Time: 10:00am‐10:50am
Place: PHY 109

Wednesday, February 22, 2006

Title: A Generalized Urn Model
Speaker: Kevin Wagner
Time: 10:00am‐10:50am
Place: PHY 109

Abstract

\(m\) “\(-1\)” balls and \(p\) “\(+t\)” balls are placed in an urn and drawn out randomly without replacement. Before any ball is drawn, a player decides whether to place a bet on the ball, the payoff being the value of the ball that is then drawn. The process continues until all balls are removed from the urn.

In part one, we will find an optimal betting strategy, and determine the expected gain \(G(m,p)\) (or give suitable bounds) as a sum involving binomial coefficients. In the case where an exact formula is present, we will then transform the sum into one involving a binomial distribution.

In part two, we determine what \(G(m,p)\) is asymptotically under various circumstances, via Stirling's formula, normal approximation, and such.

Monday, February 13, 2006

Title: Numerical Calculation of Growth Rates for Some Random Fibonacci Sequences
Speaker: Edgardo Cureg
Time: 10:00am‐10:50am
Place: PHY 109

Abstract

We will consider the numerical determination of the growth rate of some random Fibonacci sequences.

Fall 2005

(Leader: Prof. Greg McColm)

Friday, December 2, 2005

Title: On the Asymptotic Number of Non-Equivalent \(q\)-Ary Linear Codes
Speaker: Xiang-dong Hou
Time: 10:00am‐11:00am
Place: PHY 120

Abstract

Two subspaces (linear codes) of \(F_{q}^{n}\) are called equivalent if one can be obtained form the other through the action of a monomial matrix (a product of a permutation matrix and a diagonal matrix). We confirmed a recent conjecture about the asymptotic number of non-equivalent codes as \(n\) tends to infinity. If time permits, we will also mention some related results.

Friday, November 18, 2005

Title: Graphs and Marriages
Speaker: David Nezelek
Time: 10:00am‐11:00am
Place: PHY 120

Abstract

The marriage game concerns two disjoint sets of players, men and women, along with each player's preferences among the acceptable members of the opposite set. The object is to form stable marriages among the players, such that no two players would prefer to leave their mates for each other. We use the directed-graph approach proposed by Balinski and Ratier to demonstrate the existence of stable marriages, and to explore other items of interest.

Friday, November 4, 2005

Title: Thresholds and the Creation of Random Structures
Speaker: Greg McColm
Time: 10:00am‐11:00am
Place: PHY 120

Abstract

Quite by accident, the models of random structures mathematicians looked at first were models of random assembly. But there is another kind of model: the model in which all the random elements appear at the beginning, and in which all subsequent development is deterministic. We will look at a class of these, the random geometric graphs — which can be problematic with weak thresholds, and surprise us with strong ones.

Friday, October 28, 2005

Title: Weak Thresholds and the Simulation of Random Structures
Speaker: Greg McColm
Time: 10:00am‐11:00am
Place: PHY 120

Abstract

There are many models of random graphs, and the model of random strings presented last week can simulate many of these. We will see some models of random accretion, and see that by using the model of random strings, we can prove that these models have weak thresholds. We will also look at some open questions.

Friday, October 21, 2005

Title: Weak Thresholds and the Evolution of Random Structures
Speaker: Greg McColm
Time: 10:00am‐11:00am
Place: PHY 120

Abstract

There are many extant models of random structures, and it is about time that we start organizing them. Towards this end, we present a general model that subsumes many other models of the random assembly of complex structures. For a theme, we look at the question “at what point of the development does the partially assembled structure satisfy criterion θ?” and we find that in dealing with at least ballpark answers, this model provides some readily accessible results.

Friday, October 14, 2005

Title: Twist Numbers of Links from the Jones Polynomial
Speaker: Matt Williamson
Time: 10:00am‐11:00am
Place: PHY 120

Abstract

In this talk, I will present some basic information about knot theory, which I learned over the summer for a Research Experience for Undergraduate program. My research deals with twist numbers of links, and their relation to the Jones Polynomial. In a paper written by Dasbach and Lin, the twist number of any alternating knot was found to be encoded inside the Jones Polynomial. I extended this theorem to include alternating links, and I also found a way to read two of the Jones Polynomial coefficients from only using the diagram of the alternating link.

Friday, October 7, 2005

Title: The Spectrum of the DNA Self-Assembly Model with Flexible Tiles
Speaker: Ana Staninska
Time: 10:00am‐11:00am
Place: PHY 120

Abstract

I’ll talk about the spectrum of a given pot with DNA junction molecules, which is another aspect of the model described by Dr. Jonoska in the previous two meetings. In the final pot of an experiment, only complete complexes represent the solution to a given problem while incomplete complexes are wasted material. With careful selection of the proportion of each proto-tile added in the pot we can annul the amount of incomplete complexes. The space of all the distribution vectors of the proto-tile proportions is called the Spectrum of the pot type. The properties of the spectrum will be the main topic of the talk.

Friday, September 30, 2005

Title: A Computational Model for Self-Assembling Flexible Tiles, Part II
Speaker: Nataša Jonoska
Time: 10:00am‐11:00am
Place: PHY 120

Friday, September 23, 2005

Title: A Computational Model for Self-Assembling Flexible Tiles
Speaker: Nataša Jonoska
Time: 10:00am‐11:00am
Place: PHY 120

Abstract

A theoretical model for self-assembling tiles with flexible branches will be introduced. An instance of a “problem” is encoded as a pot of such tiles, and a “solution” is encoded as an assembled complete complex without any free sticky ends (called ports), whose number of tiles is within predefined bounds.

We prove that this model of self-assembly precisely captures NP-computability when the number of tiles in the minimal complete complexes is bounded by a polynomial.

Friday, September 16, 2005

Title: Leonard pairs and Leonard triples
Speaker: Brian Curtin
Time: 10:00am‐11:00am
Place: PHY 120

Abstract

We begin by introducing the notion of a Leonard pair. We briefly discuss their connections to the orthogonal polynomials in the Askey-scheme and examples arising in representation theory.

We shall also discuss our work on the extension of Leonard pairs to Leonard triples.

Friday, September 9, 2005

Title: Salient Properties of Scale-free Random Graph Processes
Speaker: Zoran Nikoluski, Charles University, Prague
Time: 10:00am‐11:00am
Place: PHY 120

Abstract

Recent empirical studies of the Internet and the WWW have shown statistical similarities between these and other networks, as diverse as the network of phone-calls, power network, citation, and the network of sexual contacts. The extent to which these, so-called, scale-free (scale-invariant) networks have pervaded, influenced, and conditioned the modern society, have prompted the study of scale-free random graph processes. In this talk, we review results pertinent to the three salient characteristics: scale-free degree distribution, small average path length, and large clustering coefficient. We define a fourth characteristic — degree-degree correlation — and obtain a rigorous result using static description of the scale-free random graph process per Barabasi and Albert. Implications of these salient properties to reliable searching, fast data-communication, and strategies for quarantining a disease, will also be addressed.

Spring 2005

(Leader: Prof. Greg McColm)

Thursday, April 21, 2005

Title: On a vector space analogue of Kneser's theorem, Part II
Speaker: Xiang-dong Hou
Time: 4:00pm‐5:00pm
Place: LIF 269

Thursday, April 14, 2005

Title: On a vector space analogue of Kneser's theorem
Speaker: Xiang-Dong Hou
Time: 4:00pm‐5:00pm
Place: LIF 269

Abstract

The following is a well known theorem in additive number theory:

Theorem 1 (Kneser, 1953) Let \(G\) be an ableian group, written multiplicatively, and let \(A\), \(B\) be nonempty finite subsets of \(G\). Then \(|AB|\ge |A|+|B|-|H(AB)|\), where \(AB=\{ab:a\in A,b\in B\}\) and \(H(AB)=\{g\in G:gAB=AB\}\) is the stabilizer of \(AB\).

Recently, a vector space analogue of Kneser's theorem was found:

Theorem 2 (Hou, Leung, Xiang, 2002 JNT) Let \(E\subset K\) be fields and let \(A\), \(B\) be \(E\)-subspace of \(K\) such that \(0<\dim A<\infty\), \(0<\dim B<\infty\). Assume that the algebraic closure of \(E\) in \(K\) is separable over \(E\). Then \(\dim AB\ge\dim A+\dim B-\dim H(AB)\) where \(AB\) is the \(E\)-space generated by \(\{ab:a\in A,b\in B\}\) and \(H(AB)=\{x\in K:xAB=AB\}\) is the stabilizer of \(AB\) in \(K\).

In part I of this talk, we will review the proof Theorem 2. We conjecture that Theorem 2 remains true without the separability assumption. In part II of this talk, we will prove the conjecture with \(\dim A<5\).

Thursday, April 7, 2005

Title: Transitivity in Two-dimensional Languages
Speaker: Joni Pirnot
Time: 4:00pm‐5:00pm
Place: LIF 269

Abstract

In one-dimensional language theory, a language is said to be transitive if for every pair of words in the language, there exists a sequence of symbols from the alphabet that can ‘paste’ the two words together, forming another (longer) word that appears in the language.

In two dimensions, the definition of transitivity is not so straightforward. Dot systems are used to illustrate the need for an expanded notion of transitivity when discussing two-dimensional languages.

Thursday, March 31, 2005

Title: Generating SAT solution spaces via splicing rules
Speaker: Giuditta Franco
Time: 4:00pm‐5:00pm
Place: LIF 269

Abstract

An ambition of DNA Computing is to solve NP-Complete problems in linear time. The generation of the solution space is the first step of the classical method for solving, in particular, an instance of SAT. For this problem, I will present some combinatorial features of a (string) generation procedure based on null context splicing rules. I will also discuss the generalization to the case of non-boolean variables.

Thursday, March 24, 2005

Title: On Radical Deformations of Zero-dimensional Ideals
Speaker: Boris Shekhtman
Time: 4:00pm‐5:00pm
Place: LIF 269

Abstract

I will give a counterexample to a conjecture of Carl de Boor, showing that in the ring of polynomials in three or more variables there exist zero-dimensional ideals that do not admit radical deformations.

Time permitting, I will also propose an open problem that I think will be of interest to this particular audience.

Thursday, March 10, 2005

Title: Surveillance and Forecasting for Waterborne Infections
Speaker: Ian McNeill, Department of Statistical and Actuarial Sciences, University of Western Ontario
Time: 4:00pm‐5:00pm
Place: LIF 269

Note: This is a special session of the Complex Systems seminar.

Abstract

A system is discussed for monitoring case count data on infections with a view to early detection of outbreaks and to forecasting the extent of detected outbreaks. The system is called INFERNO — a system for INtegrated Forecasts and EaRly eNteric Outbreak detection. Historical data are smoothed using a loess-type smoother. Upon receipt of a new datum, the smoothing is updated and estimates are made of the first two derivatives of the smooth curve and these are used for near-term forecasting. Recent data and the near-term forecasts are used to compute a warning index. The algorithms for computing the warning index and the interpretation of the index have been designed to effect a balance between Type I errors (false prediction of an epidemic) and Type II errors (failure to correctly predict an epidemic). If the warning index signals a sufficiently high probability of an epidemic, then a forecast of the probable size of the outbreak is made. This longer-term forecast is made by fitting a “signature” curve to the available data. The effectiveness of the forecast depends upon the extent to which the signature curve captures the shape of outbreaks of the infection under consideration. Also, since the success of forecasting is partly determined by the timeliness of the data, and since data are not usually available on a next-day basis, a discussion is provided of a methodology of adjusting for reporting-delay.

Thursday, March 3, 2005

Title: A subgroup of the braid group associated with Fox's colorings
Speaker: Shin Satoh
Time: 4:00pm‐5:00pm
Place: LIF 269

Abstract

The set of braids with Fox's colorings, whose top and bottom strings have the same vector of given colors, forms a subgroup of the braid group. We construct a certain \(2\)-complex from the vector, and prove that the subgroup is isomorphic to the fundamental group of the \(2\)-complex. In particular, we demonstrate the case of \(3\)-string braids with \(3\)-colorings.

Thursday, February 24, 2005

Title: Polynomial quandle cocycles and knot applications
Speaker: Kheira Ameur
Time: 4:00pm‐5:00pm
Place: LIF 269

Abstract

We construct new cocycles for Alexander quandles by polynomial expressions, then we use them to compute quandle cocycle invariants for \((2,m)\)-torus knots and their twist spins.

Thursday, February 17, 2005

Title: On a Theorem of Schur
Speaker: Peter Hilton, Distinguished Professor Emeritus, State University of New York, Binghamton
Time: 4:00pm‐5:00pm
Place: LIF 269

Abstract

I. Schur proved that if \(G\) is a group, \(Z\) its center and \(G'\) its commutator subgroup, and if \(G/Z\) is finite, then \(G'\) is finite. Given a certain supplementary condition, the converse also holds.

In this talk we prove the analog of Schur's Theorem and its converse in the context of nilpotent groups. For such groups one can localize the problem at a given family of primes \(P\).

We also show how to relativize the theorem by replacing \(G\) by the pair \((G,N)\), where \(N\) is normal in \(G\), and replacing \(Z\) by \(C_G(N)\), the centralizer of \(N\) in \(G\).

Thursday, February 10, 2005

Title: Divisibility properties of Fibonacci and Lucas numbers
Speaker: Peter Hilton, Distinguished Professor Emeritus, State University of New York, Binghamton
Time: 4:00pm‐5:00pm
Place: LIF 269

Abstract

We establish divisibility relations between Fibonacci and Lucas numbers. One very striking result is the following: If the Fibonacci number \(F_m\) divides some Lucas number \(L_n\), then \(F_m=1\), \(2\) or \(3\). Another surprising result is that if \(L_n\) divides \(F_m\), then \(F_n\) divides \(F_m\) and yet \(L_n\) and \(F_n\) are “almost” coprime.

Thursday, February 3, 2005

Title: Logical Operators III: the Transitive Closure Operator
Speaker: Greg McColm
Time: 4:00pm‐5:00pm
Place: LIF 269

Abstract

This is the third of three talks aimed at describing lattice-valued (e.g., boolean and/or fuzzy) Least Fixed Point logic and the Transitive Closure operator, a logical operator intimately connected with NLOGSPACE.

In this talk, we present the Transitive Closure Operator, and a game-theoretic representation of it.

Thursday, January 27, 2005

Title: Logical Operators II: Game Semantics
Speaker: Greg McColm
Time: 4:00pm‐5:00pm
Place: ENC 1002

Abstract

This is the second of several talks aimed at describing lattice-valued (e.g., boolean and/or fuzzy) Least Fixed Point logic and the Transitive Closure operator, a logical operator intimately connected with NLOGSPACE.

In this talk, we present a game-theoretic logic based on operators on a lattice of game-value functions.

Thursday, January 20, 2005

Title: Logical Operators I: Fixed Points
Speaker: Greg McColm
Time: 4:00pm‐5:00pm
Place: NES 103

Abstract

This is the first of several talks aimed at describing the Transitive Closure operator, a logical operator intimately connected with NLOGSPACE.

In this talk, we start at the beginning, with a description of operators on lattices, the existence and construction of fixed points of operators, and the consequent extension of First Order logic.

Fall 2004

(Leader: Prof. Greg McColm)

Tuesday, November 23, 2004

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

Abstract

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.

Tuesday, November 16, 2004

Title: Two-Dimensional Finite State Automata
Speaker: Joni Pirnot
Time: 2:00pm‐3:00pm
Place: CHE 203

Abstract

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.

Tuesday, November 9, 2004

Title: A Self-Assembling DNA Model and related problems
Speaker: Ana Staninska
Time: 2:00pm‐3:00pm
Place: CHE 203

Abstract

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.

Tuesday, November 2, 2004

Title: Radical Deformations of Polynomial Ideals
Speaker: Boris Shekhtman
Time: 2:00pm‐3:00pm
Place: CHE 203

Abstract

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.

Tuesday, October 26, 2004

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

Abstract

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.

Tuesday, October 19, 2004

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

Abstract

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.

Tuesday, October 12, 2004

Title: Imprimitivity in distance-regular graphs
Speaker: Brian Curtin
Time: 2:00pm‐3:00pm
Place: CHE 203

Abstract

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.

Tuesday, October 5, 2004

Title: Elementary calculations in twisting knots
Speaker: Masahico Saito
Time: 2:00pm‐3:00pm
Place: CHE 203

Abstract

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.

Tuesday, September 28, 2004

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

Abstract

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.

Tuesday, September 21, 2004

Title: Non-ribbon surface braids whose closures are ribbon
Speaker: Isao Hasegawa
Time: 2:00pm‐3:00pm
Place: CHE 203

Abstract

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

Abstract

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.

Tuesday, September 14, 2004

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

Tuesday, August 31, 2004

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

Abstract

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.

Spring 2004

(Leader: Prof. Greg McColm)

Friday, April 30, 2004

Title: Coloring Knots by Maple
Speaker: Masahico Saito and Chad Smudde
Time: 4:00pm‐5:00pm
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: Brian Curtin
Time: 4:00pm‐5:00pm
Place: ENB 108

Friday, April 16, 2004

Title: Duality in Bose-Mesner Algebras
Speaker: Brian Curtin
Time: 4:00pm‐5:00pm
Place: ENB 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 an Alternative Metric on the Space of Configurations, Part II
Speaker: David Kephart
Time: 4:00pm‐5:00pm
Place: ENB 108

Friday, April 2, 2004

Title: Cellular Automata: the Implications an Alternative Metric on the Space of Configurations
Speaker: David Kephart
Time: 4:00pm‐5:00pm
Place: ENB 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)=\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

Title: How far from an affine mapping can a permutation of a vector space be?, Part II
Speaker: Edwin Clark
Time: 4:00pm‐5:00pm
Place: ENB 108

Friday, March 19, 2004

Title: How far from an affine mapping can a permutation of a vector space be?
Speaker: Edwin Clark
Time: 4:00pm‐5:00pm
Place: ENB 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 \(\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

Title: Enumeration of Certain Affine Invariant Extended Cyclic Codes, Part II
Speaker: Xiang-dong Hou
Time: 4:00pm‐5:00pm
Place: ENB 108

Friday February 20, 2004

Title: Enumeration of Certain Affine Invariant Extended Cyclic Codes
Speaker: Xiang-dong Hou
Time: 4:00pm‐5:00pm
Place: ENB 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,\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

Title: Tridiagonal Pairs
Speaker: Hasan Al-Najjar
Time: 4:00pm‐5:00pm
Place: ENB 108

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:

Each of \(A\) and \(A^*\) is diagonalizable over \(\mathcal{F}\);
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\);
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\);
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, January 30, 2004

Title: Algebraic Properties of Involution Codes
Speaker: Kalpana Mahalingam
Time: 4:00pm‐5:00pm
Place: ENB 108

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

Title: Indefinite Sequences of Universal Quantifications: A Case Study in Fixed Point Logic, Part II
Speaker: Greg McColm
Time: 4:00pm‐5:00pm
Place: ENB 108

Friday, January 16, 2004

Title: Indefinite Sequences of Universal Quantifications: A Case Study in Fixed Point Logic
Speaker: Greg McColm
Time: 4:00pm‐5:00pm
Place: ENB 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.

Fall 2003

(Leader: Prof. Greg McColm)

Friday, November 21, 2003

Title: \(3\)-coloring and other elementary invariants of knots
Speaker: Kheira Ameur
Time: 1:00pm‐2:00pm
Place: PHY 120

Abstract

Classical Knot theory studies the position of a circle (knot) or of several circles (link) in \(R^3\) or \(s^3\). The fundamental problem of classical knot theory is the classification of links (including knots) up to natural movement in space which is called an ambient isotopy. To distinguish knots or links we look for invariants of links which are unchanged under ambient isotopy. The tricoloring invariant is the simplest invariant which distinguish between the trefoil knot and the trivial knot. The idea of tricoloring was introduced by R. Fox around 1960 and has been extensively used and popularized by J. Montesinos and L. Kauffman. It turns out that the \(3\)-coloring invariant is nicely related to other invariants like the Alexander polynomial and the Kauffman polynomial.

Friday, November 14, 2003

Title: Evolution and observation: A new way to look at computation
Speaker: Matteo Cavaliere, University of Rovira i Virgili
Tarragona, Spain
Time: 1:00pm‐2:00pm
Place: PHY 120

Abstract

In biology and chemistry a standard proceeding is to conduct an experiment, observe its progress, and then take the result of this observation as the final output. Inspired by this, we have introduced a new framework where computation is obtained by observing the “evolution” of a system. The approach has been applied to classical formal language theory (a derivation of a context-free grammar is observed by a finite automaton) and to membrane computing (a membrane system is observed by a multiset automaton). In both cases (surprising) universality results have been obtained.

Friday, November 7, 2003

Title: Modular Leonard Triples as \(q\)-Analogs of the Pauli Matrices
Speaker: Brian Curtin
Time: 1:00pm‐2:00pm
Place: PHY 120

Friday, October 24, 2003

Title: Kambi Kolam and Circular DNA Splicing
Speaker: Rani Siromoney, Madras Christian College/Chennai Mathematical Institute, India
Time: 1:00pm‐2:00pm
Place: PHY 120

Abstract

Kolam patterns have motivated the Madras group to define formal grammars for picture languages. Of special interest are the patterns which have rotational symmetry. Kambi Kolam (literally meaning wire decoration) provide us with interesting classes of cycle languages. Gift Siromoney had conducted several experiments to find out how the women folk memorise, store and retrieve from their memory, the rules for complicated Kolam patterns. His findings were that this memorisation process was similar to the turtle moves. Yet another study involved the complexity of the patterns by the number of threads (cycles) in it — whether a kambi kolam with more number of cycles is easier to remember than a single kambi (cycle) kolam. He had introduced operations which turned out to be closely related to the splicing rules in Circular DNA Splicing.

Friday, October 17, 2003

Title: Solution to a Problem of S. Payne, Part II
Speaker: Xiang-dong Hou
Time: 1:00pm‐2:00pm
Place: PHY 120

Friday, October 10, 2003

Title: Solution to a Problem of S. Payne
Speaker: Xiang-dong Hou
Time: 1:00pm‐2:00pm
Place: PHY 120

Abstract

A problem posed by S. Payne calls for determination of all linearized polynomials \(f(x)\in\mathbb{F}_{2^n}[x]\) such that \(f(x)\) and \(f(x)/x\) are permutations of \(\mathbb{F}_{2^n}\) and \(\mathbb{F}_{2^n}^*\), respectively. We show that such polynomials are exactly of the form \(f(x)=ax^{2^k}\) with \(a\in\mathbb{F}_{2^n}^*\) and \((k,n)=1\). In fact, we solve a \(q\)-ary version of Payne's problem.

Friday, October 3, 2003

Title: Characteristic Vectors of Unimodular Lattices, Part II
Speaker: Mark Gaulter
Time: 1:00pm‐2:00pm
Place: PHY 120

Friday, September 26, 2003

Title: Characteristic Vectors of Unimodular Lattices
Speaker: Mark Gaulter
Time: 1:00pm‐2:00pm
Place: PHY 120

Abstract

In this talk, we define and give examples of positive definite unimodular \(Z\)-lattices. We describe applications to crystallography, and to codes. We discuss tools that can be used to construct new unimodular lattices from old ones, including the neighbo[u]r lattice process and glue vectors. We also introduce the theta series of a lattice. To conclude the lecture, we introduce the notion of a characteristic vector in a lattice, and prove a theorem of Elkies; that the only unimodular lattice in \(R^n\) whose shortest characteristic vectors have norm \(\ge n\) is \(Z^n\).

Friday, September 19, 2003

Title: Minimal Combinatorial Models for Maps of an Interval With a Given Set of Periods, Part II
Speaker: David Kephart
Time: 1:00pm‐2:00pm
Place: PHY 120

Friday, September 12, 2003

Title: Minimal Combinatorial Models for Maps of an Interval With a Given Set of Periods
Speaker: David Kephart
Time: 1:00pm‐2:00pm
Place: PHY 120

Abstract

Continuous self-maps of the interval reveal more subtle properties than can be anticipated, even — and especially the simplest such functions, i.e., piecewise weakly monotonic functions. In Presentation I we give the background and outline of one proof of the Sharkovskii Theorem. This theorem is the starting point for the combinatorial examination of the dynamics of iterations of such functions. In Presentation II we will show how, in recently published work, (“Minimal combinatorial models for maps of an interval with a given set of periods” by Block, Coven, Geller, and Hubner, published this year in Ergodic Theory and Dynamical Systems, this approach is applied to the problem of establishing minimal combinatorial models for certain families of continuous self-maps.

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

Spring 2003

(Leader: Prof. Greg McColm)

Monday, April 28, 2003

Title: Morphisms and Continuous Maps on the Space of Formal Languages
Speaker: Daniela Genova
Time: 2:00pm‐3:00pm
Place: 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: An Introduction to Back-Circulant Graphs
Speaker: Nathan Chau
Time: 4:00pm‐5:00pm
Place: 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: Languages From and for DNA Sequences
Speaker: Kalpana Mahalingam
Time: 4:00pm‐5:00pm
Place: 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: Modular Leonard Triples
Speaker: Brian Curtin
Time: 4:00pm‐5:00pm
Place: 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: Leonard Pairs, Part II
Speaker: Hassan Al-Najjar
Time: 4:00pm‐5:00pm
Place: PHY 108

Monday, March 24, 2003

Title: Leonard Pairs
Speaker: Hassan Al-Najjar
Time: 4:00pm‐5:00pm
Place: 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:

there exists a basis for \(V\) with respect to which the matrix representing \(A\) is diagonal, and the matrix representing \(B\) is irreducible tridiagonal.
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: Cographic Excluded Minors for the Classes of Gain-Graphic Matroids
Speaker: Hongxun Qin, Ohio State University
Time: 4:00pm‐5:00pm
Place: PHY 108

Sponsor: 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: Negation and Failure, Part III
Speaker: Greg McColm
Time: 4:00pm‐5:00pm
Place: 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: Negation and Failure, Part II
Speaker: Greg McColm
Time: 4:00pm‐5:00pm
Place: PHY 108

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

Friday, January 17, 2003

Title: Negation and Failure
Speaker: Greg McColm
Time: 4:00pm‐5:00pm
Place: 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: Orbits of Acyclic Group and the \(q\)-binomial Coefficient
Speaker: Dennis Stanton, University of Minnesota
Time: 3:00pm‐4:00pm
Place: CHE 203

Fall 2002

(Leader: Prof. Greg McColm)

Monday, November 18, 2002

Title: Counting Blocks in Dimension 2, Part II
Speaker: Nataša Jonoska
Time: 4:00pm‐5:00pm
Place: PHY 118

Monday, November 4, 2002

Title: Counting Blocks in Dimension 2
Speaker: Nataša Jonoska
Time: 4:00pm‐5:00pm
Place: PHY 118

Abstract

We consider subsets of the set of all actions of \(Z\times Z\) onto a finite alphabet. These subsets (called shifts) are closed under the multiplication with the generators \((0,1)\) and \((1,0)\) and topologically closed (alphabet has discrete topology and the actions are equipped with the product topology).

We introduce the notion of “uniform transitivity” which is stronger than topologicaltransitivity, but, it implies topological entropy-minimal systems.

Monday, October 28, 2002

Title: Forbidding and Enforcing Systems, Part II
Speaker: Daniela Genova
Time: 4:00pm‐5:00pm
Place: PHY 118

Monday, October 21, 2002

Title: Forbidding and Enforcing Systems
Speaker: Daniela Genova
Time: 4:00pm‐5:00pm
Place: PHY 118

Abstract

We present a new way of defining classes of formal languages through a set of forbidden subwords and a set of enforced words. Forbidding and enforcing systems were inspired by chemical properties of DNA and actions of restriction enzymes. These systems will be presented through description of several graph theoretical problems and some topological observations will be discussed.

Monday, October 14, 2002

Title: Algebraic Characterizations of Graph Regularity Conditions
Speaker: Brian Curtin
Time: 4:00pm‐5:00pm
Place: PHY 118

Abstract

A theorem of algebraic graph theory can be stated as follows: A finite simple connected graph is regular if and only if the all-ones matrix spans an ideal of the adjacency algebra. We show that several other graph regularity conditions have ideal theoretic characterizations in appropriate algebras.

Monday, October 7, 2002

Title: Complexity Measures and Least Fixed Point Logic
Speaker: Greg McColm
Time: 4:00pm‐5:00pm
Place: PHY 118

Abstract

We will look at a time complexity measure and a space complexity measure on Least Fixed Point logic. We will use the algebraic approach of Moschovakis (~1980) and Hodges that the audience seems to prefer.

Monday, September 30, 2002

Title: The Foundations of Least Fixed Point Logic
Speaker: Greg McColm
Time: 4:00pm‐5:00pm
Place: PHY 118

Abstract

This will be a basic introduction of least fixed point logic, from Tarski to Moschovakis. We will conclude with a look at two complexity measures.

Monday, September 23, 2002

Title: The Number of Recursion Variables
Speaker: Greg McColm
Time: 1:00pm‐2:00pm
Place: PHY 109

Abstract

The Number of Recursion Variables (also called “dimension” or “arity” is a space-complexity measure introduced two decades ago. We review its prehistory and its history, mostly in the logic of First Order Logic \(+\) Least Fixed Points, and then look at a conjecture I'm launching.

Monday, September 16, 2002

Title: Combinatorial and Inverse Relations, Part II
Speaker: Mourad Ismail
Time: 1:00pm‐2:00pm
Place: PHY 109

Thursday, September 12, 2002

Title: Combinatorial and Inverse Relations
Speaker: Mourad Ismail
Time: 1:00pm‐2:00pm
Place: PHY 109

Abstract

We show how generalized Taylor series lead to combinatorial identities and inverse relations. One example is a two parameter family of matrices \(A(a,b)\) with the property \(A(a,b)A(b,c)=A(a,c)\). Also \(A^{-1}(a,b)=A(b,a)\). No differential equations will be used.

Spring 2002

(Leader: Prof. Greg McColm)

Monday, April 15, 2002

Title: Monotonicity of Eigenvalues of Hermitian Matrices
Speaker: Mourad Ismail
Time: 9:00am‐10:00am
Place: PHY 120

Abstract

We discuss various discrete techniques to describe how the eigenvalues of a parameter-dependent Hermitian matrix change as a function of the parameter.

Monday, April 8, 2002

Title: Cocycle Knot Invariants, Alexander and Burau Matrices, Part II
Speaker: Marina Appiou-Nikiforou
Time: 9:00am‐10:00am
Place: PHY 120

Monday, April 1, 2002

Title: Cocycle Knot Invariants, Alexander and Burau Matrices
Speaker: Marina Appiou-Nikiforou
Time: 9:00am‐10:00am
Place: PHY 120

Abstract

We will talk about extensions of quandles by \(2\)-cocycles in relation to knot colorings. We will also demonstrate relations between cocycle invariants and Alexander and Burau matrices. Examples of the Whitehead link and Borromean rings will be given.

Monday, March 25, 2002

Title: Using Circulant Matrices to Solve Low-Level Polynomials
Speaker: Karol McIntosh
Time: 9:00am‐10:00am
Place: PHY 120

Abstract

The idea is to construct a circulant matrix with a specified characteristic polynomial. Roots of the polynomial become eigenvalues which are trivially found for circulant matrices. This approach provides a beautiful unity to the solutions of quadratic, cubic, and quartic polynomials. This is a talk on a paper by D. Kalman & J. E. White.

Monday, March 18, 2002

Title: Distance-Regular Graphs, Part II
Speaker: Brian Curtin
Time: 9:00am‐10:00am
Place: PHY 120

Abstract

We continue with a gentle introduction to distance-regular graphs. This second part will focus on the Bose-Mesner algebra of a distance-regular graph and its representations. We shall also discuss the “\(Q\)-polynomial” property (which is defined algebraically) and some its characterizations.

The script of the first part is available on my web page at http://www.math.usf.edu/~bcurtin/DRG1.pdf.

Monday, March 4, 2002

Title: Distance-Regular Graphs
Speaker: Brian Curtin
Time: 9:00am‐10:00am
Place: PHY 120

Abstract

I will discuss some basic combinatorial and algebraic features of distance-regular graphs, objects central to my research. This talk is intended to be a gentle introduction to the subject. I will give some examples and briefly discuss some connections to other topics as well as presenting some basic facts.

Monday, February 25, 2002

Title: Software to Generate Codes for DNA Computations
Speaker: David Kephart
Time: 9:00am‐10:00am
Place: PHY 120

Abstract

In DNA nontechnology 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 \(\{A,G,C,T\}\). This alphabet is associated with a natural involution mapping \(h\), \(h(A)=T\) and \(h(G)=C\). In order to avoid undesirable Watson-Crick bonds between the words (undesirable hybridization), the language has to satisfy certain variations of coding properties such as: being a prefix (suffix) code, comma-free code, and more particular for DNA, no involution of a word is a subword of another word, or no ivolution of a word is a subword of a composition of two words.

We will demonstrate the alpha-test version of software that can either (1) test whether a given set of code words satisfy any of these properties or (2) design a set of code words that satisfy certain coding properties defined by the user. Though the default alphabet for the program is the DNA alphabet of \(\{A,G,C,T\}\) it is designed to accept (or generate) words over arbitrary alphabet and as such it can be used for a variety of applications.

Note: This work is joint with K. Mahalingam and N. Jonoska.

Monday, February 18, 2002

Title: Coloring Knots With a \(4\)-Color Palette
Speaker: Unknown
Time: 9:00am‐10:00am
Place: PHY 120

Abstract

First I review a coloring scheme of knots and links. For a given \(4\)-colored link, I give a rule of changing the (underlying) colors by a yellow marker. Whether or not you can consistently change colors this way depends on a given link, and can be used to distinguish links.

Then I will discuss how to come up with such marker rules, and mention a relation to the quandle cocycle knot invariants.

Monday, February 11, 2002

Title: Games, Logics, and Complexity, Part III
Speaker: Greg McColm
Time: 9:00am‐10:00am
Place: PHY 120

Abstract

We will conclude with a look at second order logic, the polynomial hierarchy, and other hallucinatory nonsense.

Monday, February 4, 2002

Title: Games, Logics, and Complexity, Part II
Speaker: Greg McColm
Time: 9:00am‐10:00am
Place: PHY 120

Abstract

We continue with the game for PTIME, and move on to NLOGSPACE.

Monday, January 28, 2002

Title: Games, Logics, and Complexity
Speaker: Greg McColm
Time: 9:00am‐10:00am
Place: PHY 120

Abstract

There are a number of logics that are associated with famous complexity classes. And there are a number of games that are associated with famous logics. This gives us an opportunity for some representation theorems that may enable to understand the complexity classes better.

We will start with our old friend PTIME …

Fall 2001

(Leader: Prof. Greg McColm)

Thursday, September 6, 2001

Title: An Anti-Ramsey Theorem on Posets
Speaker: Greg McColm
Time: 2:00pm‐3:00pm
Place: LIF 267

Abstract

One of the generalizations of Ramsey Theory has been to posets. It is known that for any finite poset \(P\), there is a finite poset \(Q\) such that any 2-coloring of the nodes of \(Q\) yields a monochromatic copy of \(P\). We will explore some of the results surrounding this fact, including the fact that for any trees \(S\), \(T\), and any 2-coloring of the Cartesian product \(S\times T\) into red nodes and blue nodes, there is either a red copy of \(S\) or a blue copy of \(T\). Then we will find a pair of finite posets \(P\), \(Q\), and a 2-coloring of \(P\times Q\) admitting no red copy of \(P\) nor a blue copy of \(Q\).

Thursday, September 13, 2001

Title: An Anti-Ramsey Theorem on Posets, Part II
Speaker: Greg McColm
Time: 2:00pm‐3:00pm
Place: LIF 267

Thursday, September 20, 2001

Title: Solutions of Bethe Ansatz Equations in Some Physics Models
Speaker: Mourad Ismail
Time: 2:00pm‐3:00pm
Place: LIF 267

Abstract

The Bethe Asatz equations are nonlinear algebraic equations satisfied by the eigenvalues of a physical system. Stieltjes solved these equations for the Coulomb gas model. This work is also connected to earlier work of Heine who counted the number of polynomial solutions to second order differential equations with polynomial coefficients. \(Q\)-analogues of these results will be described and I will show the connection with Bethe Ansatz equations for the XXX and XXZ models. In doing so one needs to develop a new theory of singuarities of second order equations in the Askey-Wilson operators.

Thursday, September 27, 2001

Title: Difference Equations, Orthogonal Polynomails, and Rogers-Ramanujan Identities
Speaker: Mourad Ismail
Time: 2:00pm‐3:00pm
Place: LIF 267

Abstract

We show how the Rogers-Ramanujan identities follow from studying difference equations motivated by orthogonal polynomials. In particular this explains and gives infinite families of generalizations of a list of Rogers-Ramanujan identities developed in the 1960's by L. J. Slater, who claimed it was a complete list.

Thursday, October 4, 2001

Title: A Non-Monotonic Propositional Logic
Speaker: Richard Stark
Time: 2:00pm‐3:00pm
Place: LIF 267

Thursday, October 11, 2001

Title: A Non-Monotonic Propositional Logic, Part II
Speaker: Richard Stark
Time: 2:00pm‐3:00pm
Place: LIF 267

Thursday, October 18, 2001

Title: A Non-Monotonic Propositional Logic, Part III
Speaker: Richard Stark
Time: 2:00pm‐3:00pm
Place: LIF 267

Thursday, October 25, 2001

Title: Graph Homomorphisms and Graph Automorphisms
Speaker: Brian Curtin
Time: 2:00pm‐3:00pm
Place: LIF 267

Abstract

Let \(G\) and \(H\) denote finite simple graphs. An automorphism of \(H\) is a permutation of its vertices which maps adjacent vertices to adjacent vertices (and nonadjacent vertices to nonadjacent vertices). Let \(\operatorname{Aut}(H)\) denote the full group of automorphisms of \(H\). A homomorphism of \(G\) into \(H\) is a map from the vertex set of \(G\) to that of \(H\) which maps the endpoints of edges of \(G\) to the endpoints of edges of \(H\). We discuss the use of graph homomorphisms in determining the automorphisms of a graph.

More precisely, we do the following. Fix a natural number \(n\), and let \(p\) and \(q\) denote \(n\)-tuple of vertices of \(H\). We show that if \(p\) and \(q\) belong to distinct orbits under the action of \(\operatorname{Aut}(H)\) then there is a graph \(G\) and an \(n\)-tuple \(r\) of vertices of \(G\) such that the number of homomorphisms from \(G\) into \(H\) maping \(r\) to \(p\) element-wise differs from the number of homomorphisms from \(G\) into \(H\) mapping \(r\) to \(q\) element-wise. To prove this result we shall use some classical results on polynomial invariants of finite groups.

Thursday, November 1, 2001

Title: Ph.D. Program Review Planning Session
Time: 2:00pm‐3:00pm
Place: LIF 267

Abstract

We will discuss what we will say to the Ph.D. committee next week.

Thursday, November 14, 2001

Title: Graph Homomorphisms and Graph Automorphisms, Part II
Speaker: Brian Curtin
Time: 2:00pm‐3:00pm
Place: LIF 267

Spring 2001

(Leader: Prof. Greg McColm)

Monday, April 23, 2001

Title: Domination Numbers of Circulant Graphs
Speaker: Vicky Wood
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

I will define and discuss circulant graphs and some of their characteristics. Primarily, the meaning of domination number and how I used Maple to find these numbers for most graphs through \(n=2\) will be explained. Secondarily, I will touch upon connectivity, isomorphism and one technique used to eliminate isomorphic graphs from the data for better computational efficiency. In addition, I will briefly mention 2-packing numbers and explore possible application ideas for domination numbers of circulant graphs. Finally, I will wrap up the session with a challenge to others to look for patterns in the data I generated that might lead to theorems about domination number in circulant graphs.

Monday, April 16, 2001

Title: Generating Caley Graphs
Speaker: Daniela (Genova) Filipov
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

Cayley graphs appear in problems related to edge-coloring, planarity, and symmetries in a graph. I will define Cayley graphs, superposition of graphs, Möbius Ladder, and twisted prismatic identification. I will discuss the structure of Cayley graphs using these concepts. This material is taken from a recent paper by Abreu and Guidici. The main goal of the paper is to give graph-theoretic descriptions of the Cayley graphs for all groups of small order.

Monday, April 9, 2001

Title: More on Linear Cellular Automata
Speaker: Edwin Clark
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

This talk will be more or less independent of the talk last week. I will discuss several definitions of linear cellular automata and give a few basic results. In particular I will give a few examples and discuss implications of Fitting's Lemma for the transition diagram of global states.

Monday, April 2, 2001

Title: Linear Cellular Automata and Garden-of-Eden Configurations
Speaker: Edwin Clark
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

I will discuss the definition of linear cellular automata (on graphs) and prove a few general facts concerning such automata. I will also present Sutner's proof of Sutner's Theorem: The all-ones problem has a solution in any finite graph.

The proof requires some basic facts from linear algebra over a finite field which will be reviewed prior to the presentation of the proof.

Monday, March 26, 2001

Title: Cyclic Homology of Algebras, Part IV
Speaker: Mohamed Elhamdadi
Time: 3:00pm‐4:00pm
Place: PHY 108

Monday, March 5, 2001

Title: Cyclic Homology of Algebras, Part III
Speaker: Mohamed Elhamdadi
Time: 3:00pm‐4:00pm
Place: PHY 108

Monday, February 19, 2001

Title: Cyclic Homology of Algebras, Part II
Speaker: Mohamed Elhamdadi
Time: 3:00pm‐4:00pm
Place: PHY 108

Monday, February 12, 2001

Title: Cyclic Homology of Algebras
Speaker: Mohamed Elhamdadi
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

We will define Hochschild and Cyclic Homologies of associative Algebras, give some examples and the relationship between the two.

Monday, February 5, 2001

Title: Making Bigger Quandles, Part II
Speaker: Masahico Saito
Time: 3:00pm‐4:00pm
Place: PHY 108

I will show how the 3rd cohomology groups of quandles are related to making even bigger quandles. I will also discuss relations to knots.

Monday, January 29, 2001

Title: Making Bigger Quandles
Speaker: Masahico Saito
Time: 3:00pm‐4:00pm
Place: PHY 108

Abstract

A quandle is a set with a self-distributive binary operation with a few other properties. I will review some basics of quandles, and discuss a construction of bigger quandles from given smaller quandles.

Monday, January 22, 2001

Title: Organizational Meeting
Time: 3:00pm‐4:00pm
Place: PHY 108

Summary

This meeting will also be a special session. Natasha Jonoska has asked for volunteers to go to nearby colleges and make presentations on “How to Choose and Apply to a Math Graduate School”. She has even prepared a collection of overhead slides of volunteers to use. Masahico Saito will go over the slides. Anyone, discrete or otherwise, who is interested in volunteering is invited.

Fall 2000

(Leader: Prof. Greg McColm)

Thursday, September 14, 2000

Title: Turing's Famous Leopards' Spots Problem
Speaker: W. Richard Stark
Time: 12:00pm‐1:00pm
Place: PHY 108

Thursday, September 28, 2000

Title: Turing's Famous Leopards' Spots Problem, Part II
Speaker: W. Richard Stark
Time: 12:00pm‐1:00pm
Place: PHY 108

Thursday, October 6, 2000

Title: Turing's Famous Leopards' Spots Problem, Part III
Speaker: W. Richard Stark
Time: 12:00pm‐1:00pm
Place: PHY 108

Thursday, October 19, 2000

Title: Topological Entropy of Shift Spaces
Speaker: Jamie Oberste-Vorth
Time: 12:00pm‐1:00pm
Place: PHY 108

Abstract

In this talk I'll present the definition of entropy for compact metrizable spaces then prove a theorem which enables the entropy to be more easily computed for shift spaces over the integers. Then I'll expand the theorem to include shift spaces over \(Z\times Z\). Finally, I'll include some information about the entropy of shift spaces over some other groups.

Thursday, October 26, 2000

Title: Topological Entropy of Shift Spaces, Part II
Speaker: Jamie Oberste-Vorth
Time: 12:00pm‐1:00pm
Place: PHY 108

Thursday, November 2, 2000

Title: The Rigidity Question for Coxeter Groups
Speaker: Anton Kaul
Time: 12:00pm‐1:00pm
Place: PHY 108

Abstract

Coxeter groups are often defined as those having a presentation in which generators have order 2 and all other relations involve only pairs of generators. From a geometric standpoint it is preferable to define Coxeter groups as those that act “by reflections” on some topological space. It turns out that these two definitions are equivalent.

We will discuss the basic definitions and results on Coxeter groups, focusing on the geometric aspects. In particular we will see that any Coxeter group acts by isometries on a complete \(\mathrm{CAT}(0)\) space (i.e., a metric space of non-positive curvature in the sense of Gromov) called the Davis complex.

The geometry of the Davis complex facilitates a topological approach to the “rigidity question” for Coxeter groups (a Coxeter group \(W\) is rigid if, given any two generating sets \(S\) and \(S'\) for \(W\), there is an automorphism of \(W\) which carries \(S\) to \(S'\)).

Thursday, November 9, 2000

Title: The Rigidity Question for Coxeter Groups, Part II
Speaker: Anton Kaul
Time: 12:00pm‐1:00pm
Place: PHY 108

Thursday, November 16, 2000

Title: The Rigidity Question for Coxeter Groups, Part III
Speaker: Anton Kaul
Time: 12:00pm‐1:00pm
Place: PHY 108

Thursday, November 30, 2000

Title: Discrete Mathematics Program Development
Time: 12:00pm‐1:00pm
Place: First Watch Restaurant

Thursday, December 7, 2000

Title: Discrete Mathematics Program Development, Part II
Time: 12:00pm‐1:00pm
Place: PHY 108

Spring 1999

(Leader: Prof. Greg McColm)

Thursday, February 25, 1999

Title: Quandle Colorings in Knot Theory
Speaker: Daniel Jelsovsky
Time: 1:00pm‐2:00pm
Place: PHY 120

Thursday, February 18, 1999

Title: O’Brien’s Results on The Road Coloring Problem (continued)
Speaker: Edwin Clark
Time: 1:00pm‐2:00pm
Place: PHY 120

Jump to: 98-99 * 00-01 * 01-02 * 02-03 * 03-04 * 04-05 * 05-06 * 06-07 * 07-08 * 08-09 * 09-10 * F10