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 \(\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:00-4:00 p.m.
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, 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 \(\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	Professor Edwin Clark
Time	3:00-4:00 p.m.
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: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 \(\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	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 \(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	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 \(\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.