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, December 1, 2014

Title
Speaker
Time
Place

Knot theory and DNA: unknotting numbers and topoisomerases
Rasika Hamudra
2:00pm-2:50pm
CMC 109

Abstract

Many biological processes affect topological properties of DNA. The DNA of most bacteria and viruses is circular although human DNA is linear, extremely long and tacked down to a protein scaffold at various points on the DNA. This periodic attachment endows human DNA with topological constraints similar to those for circular DNA. The topological constraints can interfere with vital metabolic cellular processes such as replication and transcription. Most mathematicians have, at some point, taken a strip of paper, put an even number of twists in it before taping the ends together, and cut the strip down the middle. The result is two linked strips of paper. This is what occurs when DNA replicates if one thinks of the the two edges of the strip as being the sugar phosphate backbones of the two strands of DNA.

We’ll talk about some biological preliminary properties of DNA, enzymes and their relation to unknotting number in knot theory.

## Monday, November 24, 2014

Title
Speaker
Time
Place
Note

The Odd-Town, and Her Drastically Different Sister City
Gregory Churchill
2:00pm-2:50pm
CMC 109
This week's seminar is cancelled.

Abstract

Consider a family of subsets on n points where each member is of odd order but where each pair of distinct members share evenly many vertices. The Odd-Town Theorem, which is wonderfully proven via the linear algebra method, states that such a family can contain at most $$n$$ sets.

We will prove this surprising result, and consider slight changes in the hypothesis.

## Monday, November 17, 2014

Title
Speaker
Time
Place

Optical Computing using Discrete SLM Filters in Digital Image Processing
Susan Highnote
2:00pm-2:50pm
CMC 109

Abstract

Early optical correlator devices required digitization of photographic images and were cumbersome because of the limited resolution and bulkiness of the technology. Digital images record a scene's discretely sampled intensity over three limited spectral ranges as a vector value $$(R_{xy}, G_{xy}, B_{xy})$$ at each pixel over varying spatial angles. Monochrome, or intensity-sampled images, are readily available and can be processed with discrete SLM (Spatial Light Modulating) filters to (1) identify objects, (2) specify object location within a frame, or (3) to encode data using optical computing approaches. Optical computing methods are capable of generating image correlation or convolution using Fourier and Fresnel transforms on discretized images with discrete filters. Binary Phase-only filters consist of binary (positive and negative phase) patterns which act as light-modulators by changing the phase of the light's wave-vector.

I will describe such an optical computing technique and hardware platform which successfully demonstrated this method. I will also review how optical computing can carry out the logic operations of AND, OR, and two-input XOR (exclusive ‘OR’) using discrete filters and coherent laser light.

## Monday, November 10, 2014

Title
Speaker
Time
Place

Self-Assembly of Three-Dimensional DNA-based Structures
Daniel Cruz
2:00pm-2:50pm
CMC 109

Abstract

We study the three-dimensional assembly of DNA-based structures. We present a design for the recursive growth of an aperiodic, self-similar, three-dimensional structure. A set of “cubic tiles”, each comprised of a skewed triangular DNA motif, provides controllable building blocks for the continued self-assembly of the structure.

## Monday, November 3, 2014

Title
Speaker
Time
Place

Knots, Unknotting, and Arc-Presentation
Jeremy Kerr
2:00pm-2:50pm
CMC 109

Abstract

In this talk, I will discuss the problem of unknotting knots; especially, how unknotting applies to “hard” unknots. This is a difficult problem, where there are quite a few algorithms, but no efficient method in place. I will also show how Dynnikov's work in arc-presentations can be used to find an upper bound for the number of unkotting moves required in an unknotting sequence. This talk will be adapted from the publication “Unknotting Unknots” by Allison Henrich and Louis H. Kauffman.

## Monday, October 27, 2014

Title
Speaker
Time
Place

The Linear Algebra of Search
David Kotschessa
2:00pm-2:50pm
CMC 109

Abstract

The success of Google as a company is owed to their powerful search tool, which arises from an application of linear algebra known as PageRank. In this talk, we will survey the mathematics of search engines, and how the Pagerank algorithm essentially turns the ranking of web pages into a simple (but profitable) eigenvector problem. We will discuss these eigenvectors and how they are calculated. We will also learn who the “random surfer” is, and discuss a few theorems about column stochastic matrices.

## Monday, October 20, 2014

Title
Speaker
Time
Place

Efficient polynomial-time approximations for #P-complete problems
Razvan Teodorescu
2:00pm-2:50pm
CMC 109

Abstract

The complexity class #P-complete is often considered in relation to the P vs. NP problem, while representative examples from this class are used to illustrate computational intractability. A rather intriguing feature of this class is the existence of polynomial-time algorithms for reduced counting problems, such as the Fisher-Kasteleyn-Temperley algorithm for perfect matchings on a planar graph. A unified mathematical formulation of both tractable and intractable counting problems is given by functional integration of quadratic forms, used to compute quantities such as as Pfaffians and permanents of adjacency matrices. The talk will review this method and its recent generalizations.

## Monday, October 13, 2014

Title
Speaker
Time
Place

Orbit automata as a new tool to attack finiteness problem for automaton groups
Dmytro Savchuk
2:00pm-2:50pm
CMC 109

Abstract

We introduce a new tool, called the orbit automaton, that describes the action of an automaton group $$G$$ on the subtrees corresponding to the orbits of $$G$$ on levels of the tree. In particular, we provide the connection between $$G$$ and the group generated by the orbit automaton and use it to deduce infiniteness of some automaton groups for which other methods failed to work. Further, we show that for each automaton group there is only finite number of different orbit automata up to equivalence.

## Monday, October 6, 2014

Title
Speaker
Time
Place

Square Density in Words
Nataša Jonoska
2:00pm-2:50pm
CMC 109

Abstract

If $$u$$ is a word, then $$uu$$ is said to be a square of $$u$$. It has been conjectured by Fraenkel and Simpson in 1998 that a word of length $$n$$ cannot have more than $$n$$ distinct squares as subwords. We suggest a stronger conjecture for the number of distinct squares in a word over alphabet $$\{a,b\}$$. Let $$k$$ be the least of the number of $$a$$’s and the number of $$b$$’s in the word. In this case, we propose that the number of distinct squares in a word of length $$n$$ is bounded by $$\frac{2k-1}{2k+2}n$$. We observe that this new bound holds for several classes of binary words and we provide examples of words that achieve the proposed bound, thereby proving that the bound is tight. We also observe that maximal number of squares in a word of length $$n$$ is achieved over a binary alphabet.

## Monday, September 29, 2014

Title
Speaker
Time
Place

Feedback Circuits and Feedforward Circuits in the Brain
Apurva Bhatty
2:00pm-2:50pm
CMC 109

Abstract

The brain processes information with fixed circuits and also with adaptable circuits. Feedback circuits allow for changing the focus of attention, for the generation of “Bayesian comparators” where expectation of particular inputs affects the output result, and for tracking and pursuit algorithms.

I will review some of these types of circuits and the types of computations performed by these circuits on static and dynamic inputs. These inputs need to be represented and stored as data objects. Some of the current theories about data structures and information representation in the brain will be discussed: e.g., directed graphs, dictionaries, “labelled lines” and edge labels in graphs, and triple stores (labels for the parent vertex, child vertex, and for the edge).

## Monday, September 22, 2014

Title
Speaker
Time
Place

Graph Isomorphism and Classifying Crystal Structures
Greg McColm
2:00pm-2:50pm
CMC 109

Abstract

Some databases of crystal structures — observed and predicted — have gotten quite large. Both TOPOS and the Cambridge Structure Database have over half a million each. This makes classification a major issue.

One popular approach is to partition known structures into graph isomorphism equivalence classes. We outline some of the complications arising from this practice and focus on one issue: the computational complexity of determing whether two crystal structures are isomorphic.

## Monday, September 15, 2014

No seminar this week.

## Monday, September 8, 2014

Topic
Speaker
Time
Place

Quantitative Analysis and Qualitative Description of Discrete Digital Imagery
Apurva Bhatty
2:00pm-2:50pm
CMC 109

Abstract

Many medical diagnostic procedures involve the review and analysis (qualitative and quantitative) of digital imagery such as MRI or CT. I will review basic concepts in digital image processing and image analysis. Comparing a series of images involves first finding the points of similarity (if any exist) so that the comparisons made are valid and accurate.

Image descriptions require segmenting the data into distinct regions and identifying and defining the differences in the various tissue types (brain, skull, tumor) or components of the objects in the image (head, arm, leg, etc.). Image segmentation using clustering techniques will be reviewed, e.g. $$k$$-means and $$k$$-mediods, along with the question of what value of $$k$$ should be used. The concepts of photogrammetry (extracting validated measurements from visual imagery), quantitative metrics and calibration, and texture analysis will be reviewed with examples from brain scans of patients with tumors and TBI (traumatic brain injury), mammography, and from my participation in the DARPA Shredder Challenge. GPU-centric (and not bio-mimetic) algorithms that measure image similarity will be reviewed. Template-matching and atlas-matching are approaches which may perform as well as the “gestalt” of human vision and image comprehension.

## Monday, August 25, 2014

Topic
Speaker
Time
Place

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