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

Title
Speaker
Time
Place

Building Categories of Multisets
Scott Grizzard
2:00pm-3:00pm
CMC 108

Abstract

A category is a kind of formal representation of a mathematical object, which can be used to “quickly” build application-specific mathematics. We state the basic facts of category theory, and we present the standard category of multisets. We then build an alternative category of multisets appropriate for a specific problem in economics. We will compare and contrast these two models of multisets.

## Monday, April 18, 2016

Title
Speaker
Time
Place

Lattices, ideals, and cryptography
Jean-François Biasse
2:00pm-3:00pm
CMC 108

Abstract

Many proposals for the next generation of public-key cryptographic protocols are based on the hardness of finding short vectors in high dimensional lattices. This area of research is known as “lattice-based cryptography”.

Lattice-based schemes with a proof of security usually require to be instantiated with parameters that worsen their performances. On the other hand, some schemes take advantage of the special structure of restricted classes of lattices. In particular, lattices arising from ideals in a number field of large degree are very popular. The rule of thumb seems to be that we need to sacrifice provable security for the sake of performance.

We will study the problem of finding short vectors in lattices arising from ideals in a number field and we will discuss its consequences for lattice-based cryptography. In particular, we will report on recent work allowing to find a short generator of a principal ideal in a high degree number field and its consequences on the security of an entire family of cryptosystems.

## Monday, April 11, 2016

Title
Speaker
Time
Place

Ludwig Bieberbach and Hilbert's 18th, the Second Theorem
Greg McColm
2:00pm-3:00pm
CMC 108

Abstract

David Hilbert's Eighteenth problem begins with the following question. Call a group of isometries on a Euclidean space crystallographic if the orbit of the origin is discrete and if there is an upper bound on the distance from any point in the space to the orbit. Hilbert asked if, for any Euclidean space, are there only finitely many isomorphism classes of such groups? The question had arisen from crystallography, and Arthur Shoenflies and Evgraf Federov had already answered this question affirmatively for dimensions two and three.

A decade later, Ludwig Bieberbach answered Hilbert's question affirmatively for all Euclidean spaces with a sequence of three theorems that connected the crystallographic groups to geometric lattices. We outlined a variant of Joseph Wolfe's proof of the first theorem (that any crystallographic group admits a translation subgroup of finite index) in the Analysis Seminar. In this presentation, we outline a traditional (i.e., cohomology-free) proof of the second theorem (that any pair of isomorphic crystallographic groups are in fact affine conjugates). The third theorem and conclusion will be presented in the fall.

## Monday, April 4, 2016

Title
Speaker
Time
Place

Tile Assembly Models and the Use of Signals
Daniel Cruz
2:00pm-3:00pm
CMC 108

Abstract

We review the abstract Tile Assembly Model (aTAM) and its relationship with DNA motifs and DNA origami. After the discussing results related to this model and its extensions, we focus on the introduction of signal transmission to tile-based self-assembly and its DNA counterpart. We explore whether signal transmission can be simulated by tile sets which do not have signals and present associated results. We conclude with conjectures involving three-dimensional tile models.

## Monday, March 28, 2016

Title
Speaker
Time
Place

A Simple Proof that Asynchronous Computing Beats Synchronous
Richard Stark
2:00pm-3:00pm
CMC 108

Abstract

The idea that programs can be made faster and more likely to succeed is we randomize a key step (a choice in who does what) is surprising. Why not just program the best choice?

## Monday, March 21, 2016

Title
Speaker
Time
Place

Applications of Planar Graphs in Knot Theory
David Kotchessa
2:00pm-3:00pm
CMC 108

Abstract

From a link diagram, we can obtain a signed planar graph. We will examine the relationships between knot diagrams and planar graphs, and how we might detect whether a given planar graph corresponds to a knot. We will discuss “almost planar” Seifert surfaces and show that a knot $$K$$ has an almost planar Seifert surface if and only if the corresponding signed planar graph is bipartite. A result concerning prime alternating amphicheiral knots will be discussed briefly.

## Monday, March 7, 2016

Title
Speaker
Time
Place

Different types of maximal caps in $$\mathbb{Z}_3^n$$
Apurva Bhatty
2:00pm-3:00pm
CMC 108

Abstract

Given a deck of cards corresponding to the lattice points in $$\mathbb{Z}_3^n$$, there are many games that can be played with a subset of dealt cards. One such game is quickly finding an “affine line” in the subset. One question that arises from such games is the number of cards which must be dealt to ensure finding such an “affine line”. Another question is the distribution and sizes of maximal caps, sets which do not contain such a line.

A cap, in this particular instance, is a subset of $\mathbb{Z}_3^n$, such that it contains no “affine line” subset within it. A maximal cap, $$C$$, is one such that the addition of any nonempty card $$c\in\{ \mathbb{Z}_3^n-C\}$$ to $$C$$ yields a new set which is no longer a cap. For $$n=1$$ and $$n=2$$, all maximal caps are of the same size. For $$n\ge 3$$, maximal caps can be of different sizes. I will review some of the distributions of these caps of different sizes, along with some novel integer sequences (which are not currently in the OEIS) that describe the trees associated with these caps. I will also describe the slightly varying definitions of “maximal cap” that are used in different publications.

I will also quickly review some results from Terence Tao about the bounds for these caps, and from Elizabeth McMahon about the structure of the caps for $$n=4$$, in $$AG(4,3)$$.

## Monday, February 29, 2016

Title
Speaker

Time
Place

Periodic graphs, spanning trees and Mahler measure
Susan Williams
University of South Alabama
2:00pm-3:00pm
CMC 108

Abstract

Infinite periodic graphs, graphs that are invariant under translation in one or more independent directions, are of interest in crystallography and statistical mechanics. One measure of complexity for such a graph is the spanning tree entropy, the exponential growth rate of the number of spanning trees in a sequence of finite subgraphs approximating the whole graph. This entropy has been calculated using mainly combinatoric and analytic arguments.

Using ideas of algebraic dynamics, we give a simplified approach to showing that the spanning tree entropy is the Mahler measure of a Laplacian polynomial that is easily obtained from graph data. Our work has applications to knot theory. This is joint work with Dan Silver.

## Monday, February 22, 2016

Title
Speaker
Time
Place

Asynchronous Computing in Modern Mathematical Computation Theory, Part II
W. Richard Stark
2:00pm-3:00pm
CMC 108

Abstract

I will present the promised proof that asynchronous computing is more powerful and efficient than the usual approaches (serial or synchronous) to computing. Finally, in response to questions by Natasha and others, I will work in a calculation using Lebesgue integration to determine the expected halting time of an NP-complete amorphous process. Approaches to asynchronous programming will have to wait.

## Monday, February 15, 2016

Title
Speaker
Time
Place

Asynchronous Computing in Modern Mathematical Computation Theory
W. Richard Stark
2:00pm-3:00pm
CMC 108

Abstract

The failure of cellular automata to represent biological computing eventually led to success in amorphous nets of automata. Asynchronous computing, dominant in multicellular living systems, is represented clearly in amorphous nets. Using this representation, I will present a simple and surprising proof that asynchronous computing is more powerful and efficient than the usual approaches (serial or synchronous) to computing. Finally, time permitting, I will describe an approach to asynchronous programming.

## Monday, February 8, 2016

Title
Speaker
Time
Place

From Quandle Modules to Sheaves on Topological Quandles
2:00pm-3:00pm
CMC 108

Abstract

We will explain how to generalize the notion of Quandle Modules to the context of Topological Quandles. If time allows, we will discuss some other open problems related to topological quandles.

## Monday, February 1, 2016

Title
Speaker

Time
Place

Delta-matroids and their polynomials
Hendrik Jan Hoogeboom
University of Leiden
The Netherlands
2:00pm-3:00pm
CMC 108

Abstract

Delta-matroids were introduced by Bouchet in 1987 as a natural generalization of matroids, changing the basis exchange axiom into a symmetric version.

Delta-matroids may be viewed as a generalization of graphs. Moreover, as pointed out by Geelen, the graph operations of local and edge complementation (used in the mathematics for modelling Euler tours) have particularly simple interpretations in terms of Delta-matroids. We have added a suitable generalization of the notion of loop complementation (“toggling” loops).

Using these operations and an equivalent of the notion of nullity for graphs we then extend the interlace polynomial (and related polynomials motivated by counting cycles in 4-regular graphs) to Delta-matroids (or even general set systems). All interrelationships and evaluations stay valid.

## Monday, January 25, 2016

Title
Speaker

Time
Place

Cotranscriptional folding: A novel topic in theory and applications of molecular self-assembly
Sukuse Abe
University of Electro-Communications
Tokyo, Japan
2:00pm-3:00pm
CMC 108

Abstract

Cotranscriptional folding refers to a phenomenon in which an RNA transcript folds upon itself while it is still being transcribed. This phenomenon has received a great deal of attention especially because of its application in manufacturing nanoscale structures reported recently [Geary, Rothemund, Andersen, Science 345:799-804, 2014]. As a model of computation by cotranscriptional folding, we propose the oritatami system. In this talk, we first present this novel computational model, introduce an oritatami system that counts in binary as an example, and finally provide an overview of the proof of its efficient Turing completeness.

## Monday, January 11, 2016

Title
Speaker

Time
Place

On finite type invariants of knots and 3-manifolds
Sukuse Abe
Saitama University
Japan
2:00pm-3:00pm
CMC 108

Abstract

We review Vassiliev invariants (finite type invariants) of knots. It is very interesting to find the relation between quantum invariants and invariants using quandles. In this lecture, we define quasi finite type invariants which are more generalized than finite type invariants and obtain the quasi finite type invariants from quandle shadow cocycle invariants of 2-bridge links and torus links calculated concretely with dihedral quandles. Besides, in the same way, we define finite type invariants of lens space and Brieskorn manifolds (which are different from Ohtsuki type invariants).

Note: This presentation will be followed by a sequel at 3 pm in CMC 116 (Conference Room) and then on Jan. 13 from 1 pm to 4 pm in CMC 116.