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

Title
Speaker
Time
Place

Simulating Substitution Tiling via Self-Assembly
Daniel Cruz
2:00pm-2:50pm
CMC 108

Abstract

Chaim Goodman-Strauss showed that every known substitution tiling of the Euclidean plane can be enforced with a finite set of matching rules. We study which substitution tilings can be simulated via self-assembly. We introduce a notion of hierarchical assembly within an existent tile assembly model to describe substitution tilings and generalize to non-square tiles. We develop a method for simulating substitution tilings via hierarchical assembly and give sufficient conditions for such simulation.

## Monday, April 16, 2018

Title
Speaker
Time
Place

Ehrenfeucht-Fraïssé Games: Examples and Applications
Daviel Leyva
2:00pm-2:50pm
CMC 108

Abstract

In this talk we shall use Ehrenfeucht-Fraïssé Games to examine through examples to what extent two structures are indistinguishable from one another in first-order logic, as well as show Connectivity is not expressible in first-order logic. We shall also connect Ehrenfeucht-Fraïssé Games with the notion of satisfaction via Hintikka sentences.

## Wednesday, April 11, 2018

Title
Speaker

Time
Place

Group of intermediate growth, aperiodic order, and Schröedinger operators
Rostislav Grigorchuk
Texas A&M University
2:00pm-2:50pm
CMC 108

Abstract

I will explain how seemingly unrelated objects: the group $$G$$ of intermediate growth constructed by the speaker in 1980, the aperioidc order, and the theory of (random) Schröedinger operators can meet together. The main result, to be discussed, is based on a joint work with D. Lenz and T. Nagnibeda. It shows that a random Markov operator on a family of Schreier graphs of $$G$$ associated with the action on the boundary of a binary rooted tree has a Cantor spectrum of the Lebesgue measure zero. This will be used to gain some information about the spectrum of the Cayley graph. The main tool of investigation is given by a substitution, that, on the one hand, gives a presentation of $$G$$ in terms of generators and relations, and, on the other hand, defines a minimal substitutional dynamical system which leads to the use of the theory of random Shröedinger operators.

No special knowledge is assumed, and the talk is supposed to be easily accessible for the audience.

Note: This is a joint Discrete Mathematics Seminar/Colloquium talk.

## Monday, April 9, 2018

Title
Speaker

Time
Place

Closed groups of rooted tree automorphisms, symbolic dynamics, and Rabin automata
Zoran Šunić
Hofstra University
2:00pm-2:50pm
CMC 108

Abstract

The set of automorphisms of a rooted tree can be considered in several settings: group theoretic, topological, or symbolic dynamics. We consider topologically closed, self-similar groups of tree automorphisms (thus, sets of tree automorphisms closed in each of the three settings). Prompted by a question by Nataša Jonoska, we provide a weak analog of a theorem of Kitchens on one-sided group shifts, which leads to interesting conclusions about the tree languages representing the closures of some well known self-similar groups. For instance, while the closures of many “unusual” self-similar groups (Grigorchuk group, Hanoi Towers group, ...) are finitely constrained groups (tree shifts of finite type) and, therefore, can be recognized by rather simple Rabin automata, the closure of the infinite cyclic group $$\mathbb{Z}$$ acting as odometer on the tree is not even Rabin recognizable (the same conclusion is valid for many other level transitive, self-similar groups that satisfy an algebraic law). Joint work with Andrew Penland.

## Monday, April 2, 2018

Title
Speaker

Time
Place

Self-assembly of shapes by cotranscriptional folding
Shinnosuke Seki
University of Electro-Communications
Tokyo, Japan
2:00pm-2:50pm
CMC 108

Abstract

Transcription is a process in which an RNA sequence (of A, C, G, U) is synthesized out of its template DNA sequence (of A, C, G, T). The molecular Xerox called RNA polymerase attaches to the template DNA sequence, scans it through, and produces its RNA copy letter by letter according to the rule A $$\to$$ U, C $$\to$$ G, G $$\to$$ C, and T $$\to$$ A (e.g., from the DNA sequence AACGT, the polymerase produces the RNA sequence UUGCA). Much earlier than being fully transcribed, the elongating RNA sequence (transcript) starts folding upon itself into a complex conformation by forming hydrogen bonds in order to get stabilized. This phenomenon is called cotranscriptional folding. In nature, various information processing is done by cotranscriptional folding, in particular, of shapes. For instance, fluoride riboswitches in Bacillus cereus bacteria cotranscriptionally fold into a terminator stem hairpin or not, in order to regulate gene expression. In 2014, Geary, Rothemund, and Andersen proposed an architecture of a DNA sequence whose transcript highly probably folds into a unique rectangle cotranscriptionally.

Using a theoretical model called oritatami system, the study of self-assembly of shapes by cotranscriptional folding was initiated recently. In this talk, I will first formalize the problem of folding a shape cotranscriptionally by an oritatami system. I will then lead audiences through the design process of an OS that cotranscriptionally folds into an arbitrary finite portion of Heighway dragon fractal as well as its verification. Related results and open problems will be also discussed.

## Monday, March 26, 2018

Title
Speaker
Time
Place

Attack-Resilient Monitoring of Cloud Services in Cyber-Physical Infrastructures
Kaiqi Xiong
2:00pm-2:50pm
CMC 108

Abstract

Attack-resilient scalable monitoring of cloud services becomes critical in the steady-state operation of a cyber-physical infrastructure. In this talk, I will first introduce cloud services and then present the cloud status problem for the monitoring of cloud services. I will further discuss a series of my attack-resilient algorithms for solving the cloud status problem, give some properties of these algorithms through theoretical analysis, and evaluate these algorithms through experiments. Moreover, the control center of a cloud is highly vulnerable to Distributed Denial of Service (DDoS) attacks. I will briefly discuss my Software Defined Networking (SDN)-based approaches for DDoS attack mitigation and detection.

## Monday, March 19, 2018

Title
Speaker
Time
Place

Developing a Model to Predict Prevalence of Compulsive Behavior in Individuals with OCD
Lindsay Fields
2:00pm-2:50pm
CMC 108

Abstract

Obsessive-Compulsive Disorder (OCD) is a mental disorder which affects approximately 2.3% of people worldwide at some point in their lives. Although it is commonly accepted by mental health experts that obsessions and compulsions are self-perpetuating, there is little research to support this theory. As such, this research proposes that continued ritualistic behavior, as opposed to calming the OCD sufferer, actually serves to amplify anxiety, which in turn incites further rituals.

We have designed a model which simulates OCD behavior consistent with this theory for individuals with moderate to severe OCD. The model predicts, given a set of environmental parameters, the probability of an individual with OCD performing compulsive behavior and the prevalence of such behavior. By applying a simple signaling game to the neural system known as the worry circuit, a program was composed and simulations run which suggest that the likelihood of compulsive behavior can be predicted using a function of the number of compulsions performed previously. These results may be considered preliminary, given the sample size of the case study and the primitive nature of the model.

## Monday, March 12, 2018

Spring Break — no seminar this week.

## Monday, March 5, 2018

Title
Speaker
Time
Place

A singular trip through the world of algebraic curves over finite fields
Annamaria Iezzi
2:00pm-2:50pm
CMC 108

Abstract

For an algebraic curve defined over a finite field Fq, the number of rational points, i.e., of points of the curve with coordinates in Fq, is always finite. Due to this discrete aspect, algebraic curves over finite fields have found, in the last 40 years, several applications in cryptography and coding theory.

In this talk, we will explore this problem of counting points, by showing the fundamental tools and results that appear in this theory. In particular, we will see how the case of smooth curves generalizes to the case of singular ones and we will present a construction of singular curves with many rational points.

## Monday, February 26, 2018

Title
Speaker
Time
Place

Design strategies for DNA tile assembly
Margherita Maria Ferrari
2:00pm-2:50pm
CMC 108

Abstract

New laboratory techniques have been developed using the Watson-Crick complementarity properties of DNA strands to achieve the self-assembly of nanostructures, particularly polyhedra. For all of these methods, an essential step is designing the component molecular building blocks. We present a mathematical model that captures the geometric constraints of rigid tiles, that are star-shaped molecules used as building blocks for tile-based DNA self-assembly. We illustrate the functionality of the model by providing DNA self-assembly strategies to effciently construct Platonic and Archimedean 3-regular polyhedral skeletons.

## Monday, February 19, 2018

No seminar this week.

## Monday, February 12, 2018

Title
Speaker
Time
Place

Platform Color Designs for Interactive Molecular Arrangements
Jasper Braun
2:00pm-2:50pm
CMC 108

Abstract

It has been shown that alternating attachments of two types (species) of floating molecular (DNA based) tiles on a predesigned array that consists of communicating neighboring DNA tiles complementary to the floating tiles can dynamically simulate some types of cellular automata (CA). We address the question of which design of the platform array provides communication across the whole plane. We show that for square tiles only the checkerboard arrangement of the two species can provide communication between any two tiles of the plane. On the other hand, there are an uncountable number of arrangements of two colors of hexagonal tiles on the plane which provide communication between any two tiles.

## Monday, February 5, 2018

No seminar this week.

## Monday, January 29, 2018

Title
Speaker
Time
Place

Too Many Periodic Graphs
Greg McColm
2:00pm-2:50pm
CMC 108

Abstract

A periodic graph is a graph embedded in Euclidean space, whose vertex set is discrete, and whose symmetry group has a free abelian subgroup of translations spanning the space. Our project is to catalog — or otherwise make accessible — all periodic graphs. We classify periodic graphs using syntactic graphs of linear forms, and for each graph of forms, we obtain a parametrization of the Euclidean graphs that are realizations of that graph of forms. The two primary cataloguing problems are: (1) even restricting our attention to very simple periodic graphs — say, edge transitive periodic graphs — there are a lot of graphs of linear forms, and worse, (2) some graphs of linear forms have infinitely many isomorphism classes of realizations. We describe one approach for finessing the latter nuisance.

## Monday, January 22, 2018

Title
Speaker
Time
Place

On Logic Definition and Comparison Games and First-Order Logic
Daviel Leyva
2:00pm-2:50pm
CMC 108

Abstract

During the Twentieth century, Leon Henkin, Jaakko Hintikka, and others connected game theory and logic. In this talk, we shall introduce the basic ideas connecting these two branches of mathematics as well as a method to obtain semantics from syntax via games developed by Hintikka. We shall also see how we can tell if two structures are “indistinguishable” (in a given logic) from one another as prescribed by Roland Fraïssé and Andrzej Ehrenfeucht.