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

Mathematics & Statistics

# Discrete Mathematics (Leader: Prof. Greg McColm)

## Monday, December 1, 2008

Title
Speaker
Time
Place

Representation of algebraic groups by simple graphs
Joy D'Andrea
3:05pm-3:55pm
PHY 013

Abstract

In 1936, the first book on graph theory was published. It was in this book that König proposed a problem of determining all finite groups $$\Gamma$$ for which there exists a graph $$G$$ such that $$\operatorname{Aut}(G)\equiv\Gamma$$.

In 1938, the problem was solved by Frucht. I will state Frucht's theorem and show the proof of this theorem, by using the quaternion group to go throught the proof by construction.

First, we will see the generating set for $$Q_8$$ and get a Cayley color graph of this group. I will use this Cayley color graph of $$Q_8$$ to got through Frucht's proof to show that the automorphism group of the resulting graph $$G$$ will be isomorphic to $$Q_8$$.

## Monday, November 24, 2008

Title
Speaker
Time
Place

Hypergraph regularity and quasirandomness
Brendan Nagle
3:05pm-3:55pm
PHY 013

Abstract

Frankl and Rödl were the first to prove a $$3$$-uniform hypergraph regularity lemma suitable for proving a counting lemma. Using different arguments and different concepts of regularity, these methods were extended to $$k$$-uniform hypergraphs by Rödl, Schacht, Skokan and the speaker, by Gowers and by Tao. In this talk, we return to the $$3$$-uniform case, and consider some hypergraph regularity concepts introduced by Frankl and Rödl ($$\delta$$-regularity), by Gowers ($$\delta$$-quasirandomness) and by Haxell, Rödl and the speaker ($$\delta$$-minimality). We prove that these three concepts are, in fact, equivalent. This result implies that the $$3$$-uniform hypergraph regularity lemmas of Frankl and Rödl and of Gowers admit algorithmic versions (using that Haxell et al. proved an algorithmic regularity lemma based on $$\delta$$-minimality). We also discuss some other applications and related results. Time permitting, we briefly discuss extensions of this work to $$k$$-uniform hypergraphs, currently in progress. Joint work with A. Poerschke, V. Rödl and M. Schacht.

## Monday, November 17, 2008

Title
Speaker
Time
Place

Design and Validation of Finite State Automata Models of Active Agents and “Intelligent Agents”
Apurva Bhatty
3:05pm-3:55pm
PHY 013

Abstract

Timing issues and information flow in cycles of networks of Deterministic and Nondeterministic Finite State Machines can create oscillations with regular rhythms, regularly irregular rhythms, or irregularly irregular rhythms, i.e., arrhythmias. The proper selection and design of states, transitions, and model environments (e.g., Cellular Automata, Lattice Gas, Lattice Boltzmann) is necessary to create valid models of phenomena in gas, liquid, and solid media (all three of which are integral to models of computational biophysics, and useful in computational behavioural and cognitive models, and computational control systems). Biophysically sound models of rhythm generation can be used to construct novel diagnostic and therapeutic approaches. These models and formal languages can be tested in silico to quantify their ability to recognize and treat arrythmias in the heart, brain, and other excitable biologic tissues. Examples will be provided in Biomedicine, Gas Transport Dynamics in Fluids and Gases, and Computational Biophysics and Chemistry (e.g., Hemoglobin), ending in the philosophical question of what levels of interaction and action are necessary and sufficient to constitute “agency” and “intelligent agents”.

## Monday, November 10, 2008

Title
Speaker
Time
Place

From the Jones Polynomial to Khovanov Homology, Part II
3:05pm-3:55pm
PHY 013

## Monday, November 3, 2008

Title
Speaker
Time
Place

From the Jones Polynomial to Khovanov Homology, Part I
3:05pm-3:55pm
PHY 013

Abstract

In 1984, V. Jones introduced a polynomial invariant of knots as a result of investigations of Von Neumann algebras. Using state models introduced by Lou Kauffman in 1987 we will define combinatorially the bracket polynomial which has the Jones polynomial as a specialization. We will then move from the bracket polynomial to Khovanov homology (introduced in 1999) which is a stronger invariant of knots than the Jones polynomial. Explicit examples of calculations will be provided.

## Monday, October 27, 2008

No seminar currently scheduled.

## Monday, October 20, 2008

Title
Speaker
Time
Place

Beyond Cellular Automata, Part III
W. Richard Stark
3:05pm-3:55pm
PHY 013

## Monday, October 13, 2008

Title
Speaker
Time
Place

Beyond Cellular Automata, Part II
W. Richard Stark
3:05pm-3:55pm
PHY 013

## Monday, October 6, 2008

Title
Speaker
Time
Place

Beyond Cellular Automata, Part I
W. Richard Stark
3:05pm-3:55pm
PHY 013

Abstract

Asynchronous computation occurs naturally in networks. It is seen as being intractable because it leads to computations which branch. If the computations are allowed to continue forever, then a single computation is a sequence of global states analogous to a decimal representing a real number, and a property of computations is a measurable set. This leads to applications of Lebesgue integration over the set of all computations — e.g., an integral can evaluate to the expectation of a property.

I will begin by (1) presenting examples, then (2) presenting an example of a process which solves its problem faster when its components are slowed down, and finally (3) end by describing indefinite integrals over the computation space.

## Monday, September 29, 2008

Title
Speaker
Time
Place

On reporter strands in DNA-based graph structures
Nataša Jonoska
3:05pm-3:55pm
PHY 013

Abstract

Through self-assembly of branched junction molecules many different DNA structures (graphs) can be assembled. We show that every multigraph can be assembled by DNA such that there is a single strand that traces each edge in the graph at least once. This strand corresponds to a boundary component of a two-dimensional orientable surface that has the given graph as a deformation retract. This boundary component traverses every edge at least once, and it defines a circular path in the graph that “preserves the graph structure” and traverses each edge once or twice, if an edge is visited twice, then this is done in opposite directions.

## Monday, September 22, 2008

Title
Speaker
Time
Place

Crystal Nets III: Edge Transitivity
Greg McColm
3:05pm-3:55pm
PHY 013

Abstract

This spring, I wrote a computer program that looks for “edge transitive” “binodal” crystal nets. We look at how it works ... and edge transitive binodal crystal nets I found. We will also discuss the “so what?” issue that arose in the recent ICMR Workshop on the Design and Synthesis of New Materials.

## Monday, September 15, 2008

Title
Speaker
Time
Place

Crystal Nets II: Generating Crystal Nets
Greg McColm
3:05pm-3:55pm
PHY 013

Abstract

One of the goals of material science is engineering new solids; this means designing such solids in advance of synthesis. In particular, this means generating mathematical descriptions of the novel crystals one desires to manufacture. Here we will look at three of the extant methods for generating crystal nets using geometry; one of these will be a method developed by Edwin Clark and myself.

## Monday, September 8, 2008

Title
Speaker
Time
Place

Crystal Nets I: Background
Greg McColm
3:05pm-3:55pm
PHY 013

Abstract

As far as I know, Democritus was the first to propose representing solids (like crystals) as graph-like objects, with atoms as vertices and bonds as edges. But ninety years since the first Nobel was handed out for graph theory, almost all mathematical work on the subject goes back only a few decades. This will be a brief introduction to and overview of crystal nets.