A-Z index - Search
OASIS - myUSF

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

Mathematics and Statistics Website College of Arts and Sciences Home

Discrete Mathematics
(Leader: Prof. Greg McColm)

Monday, April 20, 2009

No seminar this week.

Monday, April 13, 2009

Title Simplicial Complexes of Modular Leonard Triples
Speaker Jessica Sobkowiak
Time 3:05-4:05 p.m.
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 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 II
Speaker Boris Shekhtman
Time 3:05-4:05 p.m.
Place PHY 109
Abstract Please see below.

Monday, March 30, 2009

Title Characterization of radical ideals
Speaker Boris Shekhtman
Time 3:05-4:05 p.m.
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,…,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 23, 2009

No seminar this week.

Monday, March 9, 2009

Title Recognizing sub-blocks of local picture languages
Speaker Egor Dolzhenko
Time 3:05-4:05 p.m.
Place PHY 109
Abstract Sets of rectangular arrays of symbols whose 2×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:05-4:05 p.m.
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:05-4:05 p.m.
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 ε > 0, every k and every m ≥ 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 {V0, V1, …, Vl} with m ≤ l ≤ M.

Monday, February 16, 2009

Title Implementing Complex Algorithms in Multi-Core and Massively Parallel Digital Signal Processors
Speaker Apurva Bhatty
Time 3:05-4:05 p.m.
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:05-4:05 p.m.
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 II
Speaker Greg McColm
Time 3:05-4:05 p.m.
Place PHY 109
Abstract

See below.

Monday, January 26, 2009

Title Net Traversals and Net Generation
Speaker Greg McColm
Time 3:05-4:05 p.m.
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.