# Research

## Discrete Mathematics

### Monday, November 28, 2011

Title: A re-visitation of Frucht's theorem for the digraph factorial
Speaker: Joy D'Andrea
Time: 3:05pm‐4:05pm
Place: PHY 120

#### Abstract

In 1936, the first book on Graph Theory was published. The author Dénes König proposed the problem of determining all finite groups $$G$$ for which there exists a graph $$Gr$$ such that $$\mathrm{Aut}(Gr)$$ is isomorphic to $$G$$.

In 1938 Roberto Frucht solved this problem with the following theorem, “Let $$G$$ be a finite group. Then there is a graph $$Gr$$ such that $$\mathrm{Aut}(Gr)$$ is isomorphic to $$G$$.” In 2008 we showed Frucht's theorem and an example in the discrete mathematics seminar. Recently, an analogue of Frucht's theorem has been developed by Dr. Richard Hammock.

This development is known as Frucht's theorem for the digraph factorial. Given a digraph $$A$$, then its factorial $$A!$$ is a certain digraph whose vertex set is the permutations of $$V(A)$$. The arc set of $$A!$$, denoted as $$E(A!)$$, forms a group, where the operation is the pairwise multiplication of the endpoints. Hammock's analogue of Frucht's theorem is stated as follows: ‘For any finite group $$G$$, there is a graph $$A$$ for which $$E(A!)$$ is isomorphic to $$G$$.’

In this talk we will briefly review Frucht's theorem, and show an outline of the proof of Hammock's analogue.

### Monday, November 21, 2011

Title: Sets of Real Numbers Defined by Finite Automata
Speaker: Tony Long
Time: 3:05pm‐4:05pm
Place: PHY 120

#### Abstract

We will investigate the topological properties of sets of real numbers defined by finite automata. The concept of an automaton “defining” a number is obtained through a natural extension of the concept of an automaton accepting a finite sequence. Under this definition, we will see that a finite automaton defines a closed set of numbers. We will characterize those automata whose defined sets contain nontrivial intervals and show that the end points of these intervals are rational numbers. Additionally, we will see that the measure of a set defined by an automaton is always rational. This is based on work by Professor Juris Hartmanis and Dr. Richard Stearns.

### Monday, November 14, 2011

Title: Strongly Irresolvable Spaces
Speaker: Kari Sizemore
Time: 3:05pm‐4:05pm
Place: PHY 120

#### Abstract

Several characteristics of strongly irresolvable topological spaces are noted and the precise relationship between strong irresolvability, heritary irresolvability, and submaximality are given. It is also noted that strong irresolvability is a faint topological property, while neither heriditary irresolvability nor submaximality are semitopological.

### Monday, November 7, 2011

Title: Graph products and integer domination
Speaker: Niluk John
Time: 3:05pm‐4:05pm
Place: PHY 120

#### Abstract

For integer $$k\ge1$$, we consider the $$\{k\}$$-domination number $$\gamma_{\{k\}}(G)$$ of a graph $$G$$ and the Cartesian product $$G\square H$$ and the strong direct product $$G\boxtimes H$$ of graphs $$G$$ and $$H$$. We improved the bounds of $$\gamma_{\{k\}}(G\boxtimes H)$$, from which earlier results by Fisher on $$\gamma(G\boxtimes H)$$ and Fisher et al. on the fractional domination number $$\gamma_f(G\boxtimes H)$$ were derived. We also give sufficient conditions for graphs to satisfy the generalized form of Vizing's conjecture posed by Hou and Lu.

### Monday, October 31, 2011

Title: Manufacturing Quandles for Knot Coloring
Speaker: W. Edwin Clark
Time: 3:05pm‐4:05pm
Place: PHY 120

#### Abstract

I will discuss how we constructed quandles that will distinguish by number of colorings all prime knots on at most 12 crossings. [Collaborators: Mohamed Elhamdadi, Masahico Saito and Timothy Yeatman]

### Monday, October 24, 2011

Title: CT-Scan Reconstruction, Segmentation, and Classification Iterative Algorithms
Speaker: Apurva Bhatty
Time: 3:05pm‐4:05pm
Place: PHY 120

#### Abstract

Algorithms for the $$3$$-D reconstruction, classification, and feature extraction of scans can be either single-pass or iterated. These algorithms can be distributed and performed in parallel to provide speed-up on certain architectures. The image quality of the reconstructions can be quantitated as a measure (of the physics-based model and noise artifacts) and affects the classification and calibration of the images and allows for improvements in the reconstruction algorithms, including being able to resolve below the single-pixel limit and characterizing the error at each point (SNR, signal-to-noise ratio).

I will review how different approaches to parallelize the algorithms lead to different trade-offs in time, space, and communication resource usage. The same multispectral machine learning approaches (supervised or unsupervised pattern recognition) can also be used in EKG-wave arrhythmia classification and in speech or birdsong identification.

### Monday, October 17, 2011

Title: Characterizing Double Occurrence Words Used in DNA Assembly
Speaker: Jonathan Burns
Time: 3:05pm‐4:05pm
Place: PHY 120

#### Abstract

A double occurrence word contains exactly two copies of each alphabet letter belonging to the word. Such words arise naturally in the study of linked diagrams, chord diagrams, and assembly graphs. Recently, double occurrence words have been used to model the behavior of genetic recombination in Ciliates. I will characterize several elementary classes of double occurrence words such as symmetric, weakly-irreducible, and strongly-irreducible words and enumerate them constructively.

### Monday, October 10, 2011

No seminar this week.

### Monday, October 3, 2011

Title: Boolean Partition Algebras and an Application to Ultrapowers
Speaker: Joseph Van Name
Time: 3:05pm‐4:05pm
Place: PHY 120

#### Abstract

A Boolean partition algebra is a pair $$(B,F)$$ where $$B$$ is a Boolean algebra and $$F$$ is a filter on the meet-semilattice of partitions of $$B$$ that contains all finite partitions. There is a well known one-to-one correspondence between Boolean algebras and totally disconnected compact spaces. This one-to-one correspondence generalizes to a one-to-one correspondence between certain complete uniform spaces and certain Boolean partition algebras. Boolean partition algebras may also be used to generalize the ultrapower construction. Alternatively, one may use complete uniform spaces to generalize the ultrapower construction.

### Monday, September 26, 2011

Title: Terwilliger algebras of Bol loops
Speaker: Brian Curtin
Time: 3:05pm‐4:05pm
Place: PHY 120

#### Abstract

We discuss Terwilliger algebras constructed from finite Bol loops. Bol loops are a special type of quasigroup, and Cayley tables of finite quasigroups are Latin squares. There is a well-known construction of a $$4$$-class association scheme from a Latin square, and from any association scheme one may construct Terwilliger (subconstituent) algebras. We describe the Terwilliger algebras arising from Bol loops in this manner.

### Monday, September 19, 2011

Title: Automated Descriptions of Nanostructures and Other Polyhedral Objects, Part II
Speaker: Greg McColm
Time: 3:05pm‐4:05pm
Place: PHY 120

Abstract

Many nanostructures can be modeled by polyhedral complexes, and formally described using the machinery of (semi-)group theory. Some of the description may be constructed using formal languages, in particular regular languages (describing walks on the structure) and context-free languages (describing cyclic walks on the structure). This is joint work with Nataša Jonoska & Milé Krajčevski.

### Monday, September 12, 2011

Title: Automated Descriptions of Nanostructures and Other Polyhedral Objects
Speaker: Greg McColm
Time: 3:05pm‐4:05pm
Place: PHY 120

#### Abstract

Many nanostructures can be modeled by polyhedral complexes, and formally described using the machinery of (semi-)group theory. Some of the description may be constructed using formal languages, in particular regular languages (describing walks on the structure) and context-free languages (describing cyclic walks on the structure).