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, 2016

Title
Speaker
Time
Place

A Note on Isomorphism of Directed Graphs
Nataša Jonoska
2:00pm-2:50pm
CMC 109

Abstract

We associate one-out graphs, called skeletons, with directed graphs (with loops, without parallel edges). We give necessary and sufficient conditions for two one-out graphs to be skeletons of isomorphic graphs. This observation is applied to a formal model of reaction systems to characterize reaction systems with isomorphic dynamics.

## Monday, November 21, 2016

Title
Speaker
Time
Place

A Topological Version of the State Sum Knot Invariant
W. Edwin Clark
2:00pm-2:50pm
CMC 109

Abstract

This is joint work with Masahico Saito growing out of work with Larry Dunning on the computation of the state sum invariant for knots. The state sum invariant (also known as the 2-cocycle invariant) was defined 17 years ago in a paper by Scott Carter, Dan Jelsovsky, Seiichi Kamada, Laurel Langford and Masahico Saito, https://arxiv.org/abs/math/9903135, for finite quandles using “2-cocycles” with values in a finite abelian group. Recently with Dunning and Saito we showed how to compute many state sum invariants of knots without explicitly finding the corresponding 2-cocycles. Using this idea we are able to generalize the state sum invariant from finite quandles with 2-cocycle values in a finite abelian group to topological quandles with 2-cocycle values in a topological group. I will discuss examples based on a family of quandles $${Q(θ):θ2(0,2π]}$$ based on conjugacy classes of $$\mathrm{SO}(3)$$ and $$\mathrm{SU}(2)$$.

## Monday, November 14, 2016

Title
Speaker
Time
Place

Probabilistic algorithms for intractable deterministic problems
Razvan Teodorescu
2:00pm-2:50pm
CMC 109

Abstract

Starting from a typical example of intractable problem, I will introduce and discuss a class of probabilistic algorithms which can provide surrogate solutions in polynomial time, and with error bounds decreasing with the input size. For certain problems, it is proven that the surrogate solutions converge to the actual solution, as the input size goes to infinity. The main result is a criterion for selecting the right class of algorithms for a specific problem.

## Monday, November 7, 2016

Title

Speaker
Time
Place

Lamplighter groups and (bi)reversible automata from affine transformations of the ring of formal power series
Dmytro Savchuk
2:00pm-2:50pm
CMC 109

Abstract

The ring $$\mathbb{Z}_p[[t]]$$ of formal power series over $$\mathbb{Z}_p$$ can be naturally identified with the boundary of $$p$$-ary rooted tree $$T_p$$. For each $$a(t), b(t)\in\mathbb{Z}_p[[t]]$$ with $$b(t)$$ being a unit, we consider the affine transformations of $$\mathbb{Z}_p[[t]]$$ defined by $$f(t)\mapsto a(t)+f(t)\cdot b(t)$$. This transformation defines automorphisms of $$T_p$$ that can be explicitly described by an automaton that is finite if and only if both $$a(t)$$ and $$b(t)$$ are rational power series.

We prove that the multiplication by a power series corresponding to a rational function $$p(t)/q(t)\in\mathbb{Z}_p[[t]]$$ is defined by a finite automaton that is reversible if and only if $$\deg p\le\deg q$$ and $$q$$ divides $$x^{n-1}$$ for some $$n$$. In particular, we obtain a family of bireversible automata in this way, which covers several examples that were studied earlier. We also describe algebraic structure of corresponding self-similar groups generated by such automata and show that they are isomorphic to lamplighter groups of various ranks.

This is a joint result with Ievgen Bondarenko.

## Monday, October 31, 2016

Title
Speaker
Time
Place

Cellular Automaton Simulations Using a 2D DNA Origami Array
Daniel Cruz
2:00pm-2:50pm
CMC 109

Abstract

We discuss and build upon the results presented in Molecular Ping-Pong Game of Life on a 2D DNA Origami Array by Jonoska and Seeman. In particular, we present the theoretical model discussed in this publication and its algorithmic possibilities. We also present the example of a Game of Like-like system and discuss the simulation of 1D elementary cellular automata.

## Monday, October 24, 2016

Title
Speaker
Time
Place

A pants decomposition algorithm on triangulated meshes
Mustafa Hajij
2:00pm-2:50pm
CMC 109

Abstract

A pair of pants is a genus zero orientable surface with three boundary components. A pants decomposition of a surface is a finite collection of unordered pairwise disjoint simple closed curves embedded in the surface that decompose the surface into pants. In this talk I will present a Morse theory based algorithm for pants decomposition of a triangulated surface mesh.

## Monday, October 17, 2016

Title
Speaker
Time
Place

Brian Curtin
2:00pm-2:50pm
CMC 109

Abstract

That means algebra, combinatorics, number theory, logic, theoretical computer science, and topology. All interested people are invited.

## Monday, October 10, 2016

No seminar this week.

## Monday, October 3, 2016

No seminar this week.

## Monday, September 26, 2016

Title
Speaker

Time
Place

How to color knots quickly while staying within the rules
Larry Dunning
Professor Emeritus
Bowling Green State University
2:00pm-2:50pm
CMC 109

Abstract

There have been several generations of knot coloring programs at USF (predating the recent resurgence of adult coloring books).

The tools available in systems such as Maple, GAP, and Prover9/Mace4 have advantages; however, beginning with Tim Yeatman's programs, the C programming language has been used to provide faster computation. These programs have produced colorings based on the braid representation of knots using quandles of increasing sizes.

We will look at the considerations based on data representation, algorithm refinements, and on knot theory that have been used to significantly increase the speed of these C computations.

If time permits, the recent use of these programs to color 1-tangles will be covered.

## Monday, September 19, 2016

Title
Speaker
Time
Place

Bieberbach's Third, Second Movement
Greg McColm
2:00pm-2:50pm
CMC 109

Abstract

Part of Hilbert's 18th problem was (in modern terms) whether it was true that for every dimension $$d$$, there were only finitely many isomorphism classes of $$d$$-dimensional crystallographic groups. Over a decade later, Felix Klein's student Ludwig Bieberbach proved that the answer was yes.

In this, the final installment of the proof of Bieberbach's theorem(s), we first review the previous three parts (for people who missed the previous three episodes) and then present what appears to be the most popular proof of the last part — sans the usual cohomology.

## Monday, September 12, 2016

Title
Speaker
Time
Place

Bieberbach's Third, First Movement
Greg McColm
2:00pm-2:50pm
CMC 109

Abstract

Part of Hilbert's 18th problem was (in modern terms) whether it was true that for every dimension $$d$$, there were only finitely many isomorphism classes of $$d$$-dimensional crystallographic groups. Over a decade later, Felix Klein's student Ludwig Bieberbach proved that the answer was yes.

The affirmative answer came in three theorems, and the first two theorems — that every $$d$$-dimensional crystallographic group has a $$d$$-dimensional lattice subgroup of finite index, and that any two isomorphism crystallographic groups are affine conjugates — were covered last spring. This week and next week we cover the third theorem (that Hilbert was right) in two parts:

• On Monday, September 12, we will cover the primary lemma, that there are finitely many linear conjugate classes of crystallographic point groups. The usual approach is to go through the Unimodular Group (i.e., the subgroup of the General Linear Group with integer entries), but we will take a geometric approach.
• On Monday, September 19, we will complete the theorem, that there are finitely many affine conjugate classes of crystallographic space groups. The usual approach is to use cohomology, but again we will take a more geometric approach.

## Monday, August 22, 2016

Topic
Speaker
Time
Place

Organizational Meeting
Greg McColm
2:00pm-2:50pm
CMC 109