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

Mathematics & Statistics

# Discrete Mathematics (Leader: Prof. Greg McColm <mccolm (at) usf.edu>document.write('<a href="mai' + 'lto:' + 'mccolm' + '&#64;' + 'usf.edu' + '">Prof. Greg McColm</a>');)

## Monday, November 28, 2011

Title
Speaker
Time
Place

A re-visitation of Frucht's theorem for the digraph factorial
Joy D'Andrea
3:05pm-4:05pm
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
Speaker
Time
Place

Sets of Real Numbers Defined by Finite Automata
Tony Long
3:05pm-4:05pm
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
Speaker
Time
Place

Strongly Irresolvable Spaces
Kari Sizemore
3:05pm-4:05pm
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
Speaker
Time
Place

Graph products and integer domination
Niluk John
3:05pm-4:05pm
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
Speaker
Time
Place

Manufacturing Quandles for Knot Coloring
W. Edwin Clark
3:05pm-4:05pm
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
Speaker
Time
Place

CT-Scan Reconstruction, Segmentation, and Classification Iterative Algorithms
Apurva Bhatty
3:05pm-4:05pm
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
Speaker
Time
Place

Characterizing Double Occurrence Words Used in DNA Assembly
Jonathan Burns
3:05pm-4:05pm
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
Speaker
Time
Place

Boolean Partition Algebras and an Application to Ultrapowers
Joseph Van Name
3:05pm-4:05pm
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
Speaker
Time
Place

Terwilliger algebras of Bol loops
Brian Curtin
3:05pm-4:05pm
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
Speaker
Time
Place

Automated Descriptions of Nanostructures and Other Polyhedral Objects, Part II
Greg McColm
3:05pm-4:05pm
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
Speaker
Time
Place

Automated Descriptions of Nanostructures and Other Polyhedral Objects
Greg McColm
3:05pm-4:05pm
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).