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 26, 2018

Title
Speaker
Time
Place

On Post algebras
Daviel Leyva
2:00pm-2:50pm
CMC 108

Abstract

In 1921, Emil L. Post published systems of many-valued logic, for which Paul C. Rosenbloom, in 1942, gave a definition of their associated algebras; the algebras were appropriately termed Post algebras. In this talk, we shall examine the definition and some facts related to Post algebras and, hopefully, prove that the systems put forth by Post are, in fact, Post algebras.

## Monday, November 19, 2018

Title
Speaker
Time
Place

On the security of a recent isogeny-based cryptosystem
Annamaria Iezzi
2:00pm-2:50pm
CMC 108

Abstract

Because of their arithmetic properties, since the 1980s elliptic curves have played a crucial role in several public-key cryptosystems. Among these, the most recent ones, called isogeny-based cryptosystems, use the notion of isogeny, a particular kind of map, between elliptic curves, and have been introduced in order to face the cryptanalytic powers of quantum computers. The security of these cryptosystems is based on the difficulty of computing an isogeny between two given isogenous elliptic curves.

In this seminar, after reviewing the fundamental mathematics of isogeny-based cryptography, I will discuss the security of the recent isogeny-based cryptosystem CSIDH proposed by Castryck et al. This will be also an opportunity to do some algebraic number theory and graph theory.

This is a joint work with Jean-François Biasse and Michael J. Jacobson.

## November 12, 2018

Veteran's Day Holiday -- no seminar this week.

## Monday, November 5, 2018

Title
Speaker
Time
Place

Maximal assemblies in confluent tile self-assembly systems
Nataša Jonoska
2:00pm-2:50pm
CMC 108

Abstract

We consider a model of DNA self-assembly that is similar to placing copies of a finite set of Wang tiles on the 2-dimensional integer lattice. The assemblies are built one tile at a time, and we consider the case when the system is confluent, meaning, the system produces a unique maximal assembly. We show that the bonding graph of the maximal assembly (the subgraph of the lattice indicating the bonding of the tiles) in a confluent system is a semi-linear set, and therefore such systems do not have a computational power of a Turing machine.

## Monday, October 29, 2018

Title
Speaker
Time
Place

Site-Directed Deletion
Hwee Kim
2:00pm-2:50pm
CMC 108

Abstract

We introduce a new bio-inspired operation called a site-directed deletion motivated from site-directed mutagenesis performed by enzymatic activity of DNA polymerase: Given two strings $$x$$ and $$y$$, a site-directed deletion partially deletes a substring of $$x$$ guided by the string $$y$$ that specifies which part of a substring can be deleted. We study a few decision problems with respect to the new operation and examine the closure properties of the (iterated) site-directed deletion operations.

We then define a site-directed deletion-closed (and -free) language $$L$$ and investigate its decidability property when $$L$$ is regular or context-free.

## Monday, October 22, 2018

Title
Speaker
Time
Place

More on Spaces of Geometric Graphs
Greg McColm
2:00pm-2:50pm
CMC 108

Abstract

A geometric graph is a graph embedded in some (nice) geometric space; usually a Euclidean space. Previous presentations concerned how to construct a function $$\Gamma$$ from a real vector space to a space of geometric graphs. In this (hopefully relatively self-contained) presentation, we take such functions as given and look at their properties as well as relationships between the vectors $$v$$ and the corresponding graphs $$\Gamma(v)$$. As always, our primary interest will be in periodic graphs.

## Monday, October 15, 2018

Title
Speaker
Time
Place

Spaces of Geometric Graphs
Greg McColm
2:00pm-2:50pm
CMC 108

Abstract

A geometric graph is a graph embedded in some (nice) geometric space; usually a Euclidean space. A geometric graph may be generated from a putative quotient graph with some matrix groups assigned to the quotient graph's vertices and vectors (and perhaps matrices) assigned to the edges. If we treat the matrices as constants and the vectors as variables, we obtain an ensemble of geometric graphs parametrized by a vector space of input values.

## Monday, October 8, 2018

Title
Speaker
Time
Place

Covering and Navigating Geometric Graphs
Greg McColm
2:00pm-2:50pm
CMC 108

Abstract

A geometric graph is a graph embedded in some (nice) geometric space; usually a Euclidean space. Given a group acting on that Euclidean space, the symmetry group $$S$$ of a graph $$\Gamma$$ embedded in that space is the group of automorphisms of $$\Gamma$$ induced by the group acting on the underlying space. This symmetry group does not necessarily act freely on $$\Gamma$$, and yet we would like to “lift&rdqup; $$\Gamma$$ from $$\Gamma/S$$. We describe a method for doing so, and en route, we obtain a method for parametrizing classes of periodic (and other very regular) geometric graphs.

## Monday, October 1, 2018

Title
Speaker
Time
Place

Graph Covers, Quotients, Lifts, and Immersion
Greg McColm
2:00pm-2:50pm
CMC 108

Abstract

Given a graph $$\Delta$$, a covering graph of $$\Delta$$ is a graph $$\Gamma$$ such that there is a homomorphism $$\phi$$ from $$\Gamma$$ to $$\Delta$$ that is bijective from neighborhood to neighborhood. Connected covering graphs of connected graphs can be determined up to isomorphism by “lifting” walks on the covered walk up to vertices of the covering graph. We adapt this theory to the problem of generating a graph from its quotient graph and generators of its group.

## Monday, September 24, 2018

Title
Speaker
Time
Place

Greg McColm
2:00pm-2:50pm
CMC 108

Abstract

Metric spaces of finite and infinite geometric graphs of high symmetry can be described using linear forms. Given an abstract graph composed of forms, we obtain an ensemble of homomorphic images of that graph embedded in Euclidean space. We look at some fundamentals concerning these abstract graphs and the spaces of graphs that they characterize.

## Monda, September 17, 2018

Title
Speaker

Time
Place

Gromov-Monge Quasimetrics and Distance Distributions
Tom Needham
Ohio State University
2:00pm-2:50pm
CMC 108

Abstract

In applications in computer graphics and computational anatomy, one seeks measure-preserving maps between shapes which preserve geometry as much as possible. Inspired by this, we define a distance between arbitrary compact metric measure spaces by blending the Monge formulation of optimal transport with the Gromov-Hausdorff construction. We show that the resulting distance is an extended quasi-metric on the space of compact mm-spaces, which has convenient lower bounds defined in terms of distance distributions. We provide rigorous results on the effectiveness of these lower bounds when restricted to simple classes of $$mm$$-spaces such as metric graphs or plane curves. This is joint work with Facundo Mémoli.

## Monday, September 10, 2018

Topic
Speaker

Time
Place

Quasigroups and their application in several applied areas
Danilo Gligoroski
Norwegian University of Science and Technology
Trondheim, Norway
2:00pm-2:50pm
CMC 108

Abstract

In the talk, I will briefly define the algebraic structure quasigroup and quasigroup string transformations and their related combinatorial structures Latin Squares. Then I will show several applications of quasigroups in Cryptography, Coding Theory, Computer Science and 5G. In cryptography quasigroups have been used in primitives such as block ciphers, stream ciphers, hash functions and authenticated ciphers. Popular modes of operations of block ciphers such as CBC, OFB and CTR are actually quasigroup string transformations. I will show how can we use Latin rectangles to define balanced matrices that can be used in coding theory to define efficient erasure codes. Orthogonal matrices over finite fields are very useful mathematical objects in different areas of computer science since by their use we do not need to spend expensive time to compute their inverses, nor to spend space to store their inverses. I will show how can we use Latin rectangles to efficiently define orthogonal matrices over finite fields. Finally I will show how can we use Latin squares and partial Latin squares for one emerging scientific area: Network slicing in the upcoming 5G networks.