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 27, 2017

This week's seminar is cancelled.

## Monday, November 20, 2017

Title
Speaker
Time
Place

Developing a Predictive Model for Compulsivity with Individuals with Obsessive Compulsive Disorder
Lindsay Fields
2:00pm-2:50pm
CMC 108

Abstract

Obsessive-Compulsive Disorder (OCD) is a fairly common disorder in which a patient repeats rituals (compulsions) in order to reduce anxiety. The most common method of diagnosing OCD is the Yale-Brown Obsessive Compulsive scale, which measures the severity of symptoms but not the compulsions. And this scale only considers the quantifiable time and energy lost, while also relying on potentially incorrect self-reporting. Furthermore, current systems of brain imaging arrest mobility and thus make it virtually impossible to empirically correlate physical compulsions and brain function. We take an alternative approach and develop a model of compulsivity based upon Minsky’s The Society of Mind. The objective is a model which would predict, given a set of environmental parameters, the probability of an individual with OCD performing compulsive behavior and the prevalence of such behavior. Each neurological agent is represented by a stochastic automaton and has a certain probability of reacting to a stimulus and moving into one of two excited states. Based on the final state of the automaton, the agent will send excitatory or inhibitory signals to surrounding agents, which also have a certain probability of changing states. If the final agent within the cycle shifts into an excited state, the subject will perform a compulsion.

## Wednesday, November 15, 2017

Title
Speaker

Time
Place

Gene Assembly in Ciliates
Ian McQuillan
2:00pm-2:50pm
CMC 108

Abstract

Ciliates are single-celled eukaryotes that, unlike most organisms, can keep two different types of their genome encoded differently within the same cell. While one type of genome (contained in the macronucleus) is used for creating RNA and proteins in the usual fashion, the other type (contained in the micronucleus) is instead used as an exchange during conjugation. Genes in the micronucleus are interrupted by additional non-coding segments not present in the macronuclear genes. Furthermore, various segments of these micronuclear genes can be permuted. This is important, as after conjugation, ciliates create a new macronucleus from the genomic material within the micronucleus in a process called gene assembly. Biologists, mathematicians, and computer scientists have tried to undercover exactly how gene assembly takes place, through various hypotheses and models.

One major problem involves predicting the order in which segments of the scrambled genome get rearranged. Similar to predictions used in phylogenetic analysis, the principle of parsimony can be used, whereby the smallest sequence of “operations” needed to transform one sequence to another is likely close to the actual number. However, in this case, what classifies as an operation is not particularly well understood. By analyzing the orders of scrambled segments in the ciliate genome, and by using information regarding the structure of the descrambling chromosomes, a mathematical model is developed involving the shuffle operation from the theory of formal languages. This operation can describe multiple parallel recombination operations that can occur during descrambling with alignment of interleaving segments. This system, as well as other models, will be described in this talk.

## Monday, November 13, 2017

Title
Speaker
Time
Place

Amplitudes of Sensations and Composition of Different Sensation types in a Discrete Information Network
Apurva Bhatty
2:00pm-2:50pm
CMC 108

Abstract

Most sensory perceptions come from arrays of sensors with a specific geometric embedding on the body. These sensory nerves map onto a manifold on the cortical surface of the brain that captures/embodies the topology of that geometric embedding. Each type of sensor is usually associated with one particular type of sensation, each of which may be mapped to words such as “heat”, “pressure”, “pain”, “bright”, “loud”, etc. Most of these sensations also have an amplitude associated with them.

How does and/or how could the discrete neural net in the human sensorineural system perform the tasks of transmitting and representing these amplitudes? What limits does a discrete information processing system place on the representation of the sensed stimuli?

How could multiple sensors be combined into composite sensations? I will describe two models, and the upper bounds associated with those models, for the number of discrete categories of composite sensations created in systems containing $$n$$ types of sensors.

Model A allows for up to $$2^n$$ composite sensations, all of the possible subsets of $$n$$ activated sensor types. Model B allows for the comparison of sensation amplitudes between types and has an upper bound of the ordered Bell numbers, sequence A000670 in the OEIS, which is equivalent to the number of weak orderings on a set of $$n$$ elements. I will go over the details of these models and present a few examples in different sensory domains that could allow for the testing of these models.

## Monday, November 6, 2017

Title
Speaker
Time
Place

Triangle factors in regular tournaments
Theodore Molla
2:00pm-2:50pm
CMC 108

Abstract

A tournament is a directed graph in which there is exactly one directed edge between every pair of vertices. We say that a tournament on n vertices is regular if the indegree and outdegree of every vertex is $$(n-1)/2$$, and we say that it has a triangle factor if there exists a collection of $$n/3$$ vertex-disjoint cyclic triangles. We prove that when $$n$$ is sufficiently large and an odd multiple of $$3$$, every regular tournament on n vertices has a triangle factor. For large tournaments, this resolves a conjecture made independently by Cuckler and Yuster. This result is best possible, because for every positive number $$n$$ congruent to $$3 \bmod 18$$, there exists a tournament on $$n$$ vertices in which the indegree and outdegree of every vertex is at least $$(n-3)/2$$ that does not have a triangle factor. We will discuss the proof of this theorem and related work and conjectures.

This is joint work with Lina Li.

## Monday, October 30, 2017

Title
Speaker
Time
Place

Level Transitivity of Polynomials Acting on Binary Trees
Elsayed Ahmed
2:00pm-2:50pm
CMC 108

Abstract

Rivest in 2001 derived conditions under which a polynomial $$f\in\mathbb{Z}[x]$$ induces a permutation on $$Z/\left(2^n\mathbb{Z}\right)$$ for every $$n\ge 1$$. Such polynomials are called permutational polynomials (in the sense of Rivest). Each permutational polynomial induces a bijection on the ring $$\mathbb{Z}_2$$ of dyadic integers, and, as we show, an automorphism of the rooted binary tree whose boundary is identified with $$\mathbb{Z}_2$$. We start from considering a general case and describing explicitly these automorphisms via their sections (or states) at all vertices of the tree.

An important question about the permutational polynomials is whether the induced dynamical system is minimal (or, equivalently, ergodic). One of the motivations comes from the constructions of pseudorandom generators with long periods and goes back to Knuth. For the binary tree the conditions necessary and sufficient for a polynomial to produce a minimal dynamical system were developed by Larin (2002) and Anashin (2006) using quite involved arguments from $$p$$-adic analysis. We obtain these conditions in a different and simpler way, namely, by analyzing the structure of an automorphism of the tree induced by permutational polynomial.

## Monday, October 23, 2017

Title
Speaker

Time
Place

The combinatorics and root system of a positional voting method
Catholic University of America
2:00pm-2:50pm
CMC 108

Abstract

Some recent developments in the mathematical foundations of voting theory are built upon a vector space framework — the profile space — to describe and illuminate certain features and properties of voting methods. In this talk, we will focus on positional voting methods, which correspond to linear maps on the profile space which are equivariant with respect to the action of a symmetric group. We will describe a connection between these positional voting methods, and type-A root systems inside of the profile space.

As an application, we will discuss the criterion of reversal symmetry, which demands that a full reversal of all ballots in an election must produce the same effect on the outcome. The combinatorics and root system of a positional voting method will allow us to understand and describe this criterion, as well as its natural generalizations.

## Monday, October 16, 2017

Title
Speaker
Time
Place

The Cartography of Spaces of Periodic Graphs
Greg McColm
2:00pm-2:50pm
CMC 108

Abstract

Call a graph $$d$$-periodic if it can be mapped into Euclidean $$d$$-space so that the vertices are mapped injectively onto a discrete set of points and the symmetry group of the graph is $$d$$-crystallographic. Such graphs can model covalent crystals. We propose some organizational principles for an exhaustive catalog of these graphs. For a fixed number of orbits of vertices and edges, we obtain a very large but finite ensemble of spaces of (equivalence classes of) such graphs, where parametrization of these spaces should produce vital statistics like the angles between adjacent edges, the ratios of lengths of different edges, etc. Each of these spaces can be naturally partitioned into subspaces of isomorphic graphs.

## Monday, October 9, 2017

Title
Speaker

Time
Place

Convergence Between Categorical Representations of Reeb Space and Mapper
Bei Wang
University of Utah
2:00pm-2:50pm
CMC 108

Abstract

The Reeb space, which generalizes the notion of a Reeb graph, is one of the few tools in topological data analysis and visualization suitable for the study of multivariate scientific datasets. First introduced by Edelsbrunner, et al., it compresses the components of the level sets of a multivariate mapping and obtains a summary representation of their relationships. A related construction called mapper, and a special case of the mapper construction called the Joint Contour Net have been shown to be effective in visual analytics. Mapper and JCN are intuitively regarded as discrete approximations of the Reeb space, however without formal proofs or approximation guarantees. An open question has been proposed by Dey et al. as to whether the mapper construction converges to the Reeb space in the limit.

In this work, we are interested in developing the theoretical understanding of the relationship between the Reeb space and its discrete approximations to support its use in practical data analysis. Using tools from category theory, we formally prove the convergence between the Reeb space and mapper in terms of an interleaving distance between their categorical representations. Given a sequence of refined discretizations, we prove that these approximations converge to the Reeb space in the interleaving distance; this also helps to quantify the approximation quality of the discretization at a fixed resolution.

This is a joint work with Elizabeth Munch.

## Monday, October 2, 2017

Title
Speaker

Time
Place

TBA
Abdulmelik Mohammed
Department of Computer Science
Aalto University School of Science & Technology
2:00pm-2:50pm
CMC 108

Abstract

Over the past few decades, DNA has been employed as nanoscale construction material for assembling a variety of shapes, patterns and devices. While earlier work in DNA nanotechnology mostly relied on hand-crafted expert design of individual shapes, the introduction of the ground-breaking and experimentally robust DNA origami method has enabled the synthesis of almost arbitrary 2D and 3D shapes with a variety of design strategies. In DNA origami, a long, circular, viral DNA strand called a scaffold is folded into a target shape using hundreds of short synthetic strands called staples.

Based on DNA origami, we have recently contributed a highly automated and efficient design strategy for 2D and 3D shapes through a graph-theoretic formulation. In our setting, the surface of the target shape is first represented through a triangulation and then edge-skeleton of the triangulation is rendered to a complex of DNA double helices half composed of the scaffold strand. This entails the topological routing of the long circular scaffold strand along the edge skeleton. We have formulated the topological scaffold strand routing problem as topologically constrained variations of the Chinese-postman-tour problem. In this talk, I will present some of the algorithms we have developed for topologically constrained Chinese-postman-tour problems on spherical and higher-genus surface triangulations.

## Monday, September 25, 2017

Title
Speaker

Time
Place

Link invariants derived from multiplexing of crossings
Waseda University
Japan
2:00pm-2:50pm
CMC 108

Abstract

We introduce the multiplexing of a crossing, replacing a classical crossing of a virtual link diagram with multiple crossings which is a mixture of classical and virtual. For integers $$m_{i}$$ ($$i=1,\dotsc,n$$) and an ordered $$n$$-component virtual link diagram $$D$$, a new virtual link diagram $$D(m_{1},\dotsc,m_{n})$$ is obtained from $$D$$ by the multiplexing of all crossings. For welded isotopic virtual link diagrams $$D$$ and $$D'$$, $$D(m_{1},\dotsc,m_{n})$$ and $$D'(m_{1},\dotsc,m_{n})$$ are welded isotopic. From the point of view of classical link theory, it seems very interesting that $$D(m_{1},\dotsc,m_{n})$$ could not be welded isotopic to a classical link diagram even if $$D$$ is a classical one, and new classical link invariants are expected from known welded link invariants via the multiplexing of crossings.

## Monday, September 18, 2017

Title
Speaker
Time
Place

Objects in Maple (and How to Test Them)
Scott Grizzard
2:00pm-2:50pm
CMC 108

Abstract

Maple supports object oriented programming, allowing you to create your own encapsulated, reusuable objects. This talk will introduce object oriented programming, specifically in Maple, using affine transformations as an example. We will also cover the basics of writing scripts to automatically test your objects and procedures to simplify debugging. The final example script is available on github at https://github.com/scottgrizzard/MapleAffineTransformation. Please bring your laptop if you wish to follow and experiment with the code.

## Monday, September 11, 2017

This week's seminar is cancelled due to a university closure.

## Monday, August 21, 2017

Topic
Speaker
Time
Place

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