banner USF Home College of Arts & Sciences OASIS myUSF USF A-Z Index

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

Mathematics & Statistics

Discrete Mathematics
(Leader: Prof. Greg McColm)

Monday, November 30, 2009

Title
Speaker
Time
Place

Biased Random Walks on Hypercubes, on \(K_{2^n}\), and on derived digraphs
Apurva Bhatty
3:05pm-3:55pm
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:

  1. 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
  2. a representational scheme for these automata
  3. a technique to generate approximate Stochastic matrices which take up polynomial space of size \(\left(n^2\times n^2\right)\)
  4. a conjecture on the scaling of the dynamics of these automata, and describe future simulations to test the conjecture.

Monday, November 23, 2009

Title
Speaker
Time
Place

On monotone and hereditary properties of graphs and hypergraphs
Brendan Nagle
3:05pm-3:55pm
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
Speaker

Time
Place

Witten multiple zeta functions associated with Lie algebras, Part II
Jianqiang Zhao
Eckerd College
3:05pm-3:55pm
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
Speaker

Time
Place

Witten multiple zeta functions associated with Lie algebras, Part I
Jianqiang Zhao
Eckerd College
3:05pm-3:55pm
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, November 2, 2009

No seminar this week.

Monday, October 26, 2009

Title
Speaker
Time
Place

Some properties of assembly graphs associated with DNA recombination in ciliates
Tilahun Muche
3:05pm-3:55pm
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
Speaker
Time
Place

Leonard pairs of classical type constructed from Lie algebra \(\operatorname{sl}(2)\)
Brian Curtin
3:05pm-3:55pm
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
Speaker
Time
Place

CA-generated Two-dimensional Languages
Egor Dolzhenko
3:05pm-3:55pm
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
Speaker
Time
Place

Nested ideals and the Tomas Sauer conjecture
Tom McKinley
3:05pm-3:55pm
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 28, 2009

The seminar is cancelled this week.

Monday, September 21, 2009

Title
Speaker
Time
Place

What I Did This Summer, or Periodicity and Tiling Spaces, Part II
Greg McColm
3:05pm-3:55pm
LIF 263

Monday, September 14, 2009

Title
Speaker
Time
Place

What I Did This Summer, or Periodicity and Tiling Spaces
Greg McColm
3:05pm-3:55pm
CPR 203

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.