# Research

## Discrete Mathematics

### Monday, December 1, 2008

Title: Representation of algebraic groups by simple graphs
Speaker: Joy D'Andrea
Time: 3:05pm‐3:55pm
Place: 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: Hypergraph regularity and quasirandomness
Speaker: Brendan Nagle
Time: 3:05pm‐3:55pm
Place: 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: Design and Validation of Finite State Automata Models of Active Agents and “Intelligent Agents”
Speaker: Apurva Bhatty
Time: 3:05pm‐3:55pm
Place: 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: From the Jones Polynomial to Khovanov Homology, Part II
Time: 3:05pm‐3:55pm
Place: PHY 013

### Monday, November 3, 2008

Title: From the Jones Polynomial to Khovanov Homology, Part I
Time: 3:05pm‐3:55pm
Place: 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: Beyond Cellular Automata, Part III
Speaker: W. Richard Stark
Time: 3:05pm‐3:55pm
Place: PHY 013

### Monday, October 13, 2008

Title: Beyond Cellular Automata, Part II
Speaker: W. Richard Stark
Time: 3:05pm‐3:55pm
Place: PHY 013

### Monday, October 6, 2008

Title: Beyond Cellular Automata, Part I
Speaker: W. Richard Stark
Time: 3:05pm‐3:55pm
Place: 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: On reporter strands in DNA-based graph structures
Speaker: Nataša Jonoska
Time: 3:05pm‐3:55pm
Place: 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: Crystal Nets III: Edge Transitivity
Speaker: Greg McColm
Time: 3:05pm‐3:55pm
Place: 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: Crystal Nets II: Edge Transitivity
Speaker: Greg McColm
Time: 3:05pm‐3:55pm
Place: 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: Crystal Nets I: Edge Transitivity
Speaker: Greg McColm
Time: 3:05pm‐3:55pm
Place: 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.