http://www.usf.edu

| Prospective Students | Our Students | Visitors | Faculty & Staff | Alumni & Parents | Business & Community | Campuses |

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, December 3, 2007

Title Towards the Hypergraph Regularity Method
Speaker Brendan Nagle
Time 3:00-4:00 p.m.
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:00-4:00 p.m.
Place PHY 109
Abstract Transducers are finite state automata with an output. To each transducer τ we can associate a two-dimensional language L2 (τ), consisting of blocks of symbols in the following way. The first row, w, of each block is in the input language of τ, the second row is a word that τ 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 τ.

Monday, November 19, 2007

Title Rational Power Series
Speaker Xiang-Dong Hou
Time 3:00-4:00 p.m.
Place PHY 109
Abstract Let F be a field and n > 0. A power series f $\in$ F[[x1,…, xn]] is called rational if f = h/g for some g, h $\in$ F[x1,…,x n] with g(0,…,0) ≠ 0, i.e., if there exists g $\in$ F[x1,…, xn] with g(0,…,0) ≠ 0 such that gf $\in$ F[x1,…, xn]. We prove that in this definition, the condition g(0,…,0) ≠ 0 can be replaced with a weaker condition g ≠ 0. This is obvious when n = 1. When n ≥ 2, however, the problem is more subtle. Our proof uses valuations in fields of algebraic functions of one variable.

Monday, November 12, 2007

Title TBA
Speaker TBA
Time 3:00-4:00 p.m.
Place PHY 109

Monday, November 5, 2007

Note There will be no seminar this week, but it will resume on November 12th.

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:00-4:00 p.m.
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 Dr. Greg McColm
Time 3:00-4:00 p.m.
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 Dr. Greg McColm
Time 3:00-4:00 p.m.
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 Professor Edwin Clark
Time 3:00-4:00 p.m.
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 φ: x → R(x) + b of Euclidean 3-space where R is a rotation and b is a fixed vector and φ induces a graph automorphism of a 3-periodic net then the angle of rotation is 2π/n where n = 1, 2, 3, 4 or 6.

Monday, October 1, 2007

Title Single Generated 3-Periodic Nets
Speaker Professor Edwin Clark
Time 3:00-4:00 p.m.
Place PHY 109
Abstract “3-periodic net” is an embedding of a graph in R3 (Euclidean 3-space) with the following properties:
  1. Vertices are represented by points in R3.
  2. Edges are represented by straight line segments.
  3. The set of vertices is a discrete subset of R3, that is, there is positive number r such that the distance between any two vertices is more than r.
  4. There are three independent translations of R3 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 R3 generated by n involutary isometries f[1], …, f[n] of R3 so that the orbit of the origin: G0 := {g(0): g 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, …, n. Hence N is a homomorphic image of the Cayley graph of G with generator set {f[1],&hellip,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:00-4:00 p.m.
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 M5 + M6 n-2 + M1n2 -6n+7, where Mk denotes the complex algebra of k × 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 Dr. Brian Curtin
Time 3:00-4:00 p.m.
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 A1, A2 be a tridiagonal pair on V, and let B1, B2 be linear transformations from V* to V* such that for all ν in V and f in V*,

B1 f(ν) = f(A1 ν) and B2 f(&nu) = f(A2 ν).


We show that B1, B2 is a tridiagonal pair on V*. We then show that if A1, A2 is of q-Serre type, then B1, B2 is isomorphic to A1, A2. We also show that in this case there exists a unique bilinear form on V such that for all u, ν in V,

〈 A1 u, ν 〉 = 〈 u, A1 ν 〉 and 〈 A2 u, ν 〉 = 〈 u, A2 ν 〉.

Monday, September 10, 2007

Title Leonard Triples
Speaker Dr. Brian Curtin
Time 3:00-4:00 p.m.
Place PHY 109
Abstract Let V denote a vector space of finite positive dimension. We call a triple of elements from 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.