Research

Discrete Mathematics

(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:

  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: 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, November 2, 2009

No seminar this week.

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 28, 2009

The seminar is cancelled this week.

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.