USF Home > College of Arts and Sciences > Department of Mathematics & Statistics

Mathematics & Statistics

# Discrete Mathematics (Leader: Prof. Greg McColm)

## Monday, April 26, 2010

Title
Speaker
Time
Place

Graph Transversals and Transversals of Faces
Joy D'Andrea
3:05pm-3:55pm
PHY 108

Abstract

In graph theory, a transversal, given a partition of vertices and edges, will consist of one vertex and one edge from each orbit of a group of automorphisms. We are expanding this concept to finding “transversals” of the faces on CW-Complexes of Polyhedra. We are looking for a transversal of faces that will be connected. In this talk we will provide a construction of a proof and show some examples.

## Monday, April 19, 2010

Title
Speaker
Time
Place

Factorial-local Cellular Automata
Egor Dolzhenko
3:05pm-3:55pm
PHY 108

Abstract

The time evolution of a bi-infinite configuration of a one-dimensional cellular automaton (CA) can be visualized as a half-plane array of symbols. The set of rectangular blocks extracted from such arrays forms a two-dimensional (picture) language. If this picture language is factorial-local, we call the cellular automaton factorial-local. We show that the class of factorial-local CA is properly included in the class of regular cellular automata and that it contains nilpotent cellular automata. We give a characterization of factorial-local CA and show that it is decidable whether a given set of blocks defines a factorial-local CA with a given radius, but the general membership problem for this class of cellular automata is undecidable.

## Monday, April 12, 2010

Title
Speaker
Time
Place

Involution codes applied to DNA Coding
Andrew Burruss
3:05pm-3:55pm
PHY 108

Abstract

DNA and RNA molecules are composed of sequences of nucleotides. DNA sequences form a language with a four element alphabet. Hybridization errors can interfere with DNA coding by creating unwanted structures. These errors can be reduced by utilizing particular involution codes.

## Monday, April 5, 2010

No seminar this week.

## Monday, March 29, 2010

Title
Speaker
Time
Place

The Acceptance Urn Model
Kevin Wagner
3:05pm-3:55pm
PHY 108

Abstract

An urn contains $$p$$ balls of value $$t$$, and $$m$$ balls of value $$-s$$, where $$s$$ and $$t$$ are positive real numbers. The balls are drawn from the urn uniformly at random, without replacement, until the urn is empty. Before each draw, a player is asked whether he would like to accept the next ball drawn from the urn. If the player accepts, his payout will be the value of the next ball drawn. If the player does not accept, the next ball is drawn, but otherwise nothing happens. In this talk, we examine the acceptance urns for which $$s=t=1$$, giving the distribution of the gain using an optimal strategy that maximizes the expected gain, via the reflection method. We then examine the broader collection of acceptance urns for which $$s=1$$ and $$t$$ is a positive integer, calculating the expected gain and finding the distribution of the gain using a different geometric approach, rotation.

## Monday, March 22, 2010

Title
Speaker
Time
Place

Anonymous ID Assignment for Data Mining
Larry Dunning
3:05pm-3:55pm
PHY 108

Abstract

Each node $$n$$ of a computer network $$\mathbf{N}$$ holds an integer quantity $$Q_n$$. The secure sum operation computes $$\operatorname{Sum}\{Q_n,n\in\mathbf{N}\}$$ making the sum available to all nodes without revealing any individual contributions. Methods for computing secure sum include the use of network Edge-Disjoint Hamiltonian Cycles. The secure sum operation will be used as the basis of an iterative method for assigning each node in the network a unique number ID$$n$$ in $$\{1,\dotsc,\mathbf{N}\}$$.

The IDs are anonymous in that each node will have knowledge of only its own ID. The number of iterations required by the Anonymous ID Assignment algorithm (AIDA) can be assessed by use of a Markov Chain model. A second version of the AIDA protocol which transmits significantly shorter messages will be based on use of the Newton-Girard formulae. Implementation of the protocol can be facilitated by using a distributed algorithm for solving a resulting polynomial $$p(x)$$ over $$\mathrm{GF}(P)$$, where $$p(x)$$ is expressed in terms of the Newton basis polynomials.

## Monday, March 15, 2010

Title
Speaker

Time
Place

Forbidding-Enforcing Classes of Graphs
Daniela Genova
University of North Florida
3:05pm-3:55pm
PHY 108

Abstract

A forbidding-enforcing system (fe-system) defines a class of graphs using two sets of boundary conditions. To comply with the restrictions imposed by a forbidding set, a graph should not contain certain combinations of subgraphs specified by this set. An enforcing set on the other hand, requires that certain subgraphs induce larger subgraphs in the graph structure. Thus, an fe-system defines a class of graphs consisting of the graphs that satisfy both the forbidding restrictions and the enforcing restrictions imposed by the system. The talk will include some properties of fe-systems, as well as, characterizations of some well-known classes of graphs by fe-systems.

## Monday, March 1, 2010

Title
Speaker
Time
Place

Coherence in Random Number Generators used in Parallel Distributed Systems
Apurva Bhatty
3:05pm-3:55pm
PHY 108

Abstract

Simulation of probabilistic automata, synchronous and asynchronous, in serial and parallel computational architectures requires the use of pseudo-random number generation algorithms. PRNG and QRNG (quasi-random) algorithms are deterministic and cyclic with very long periods, and can also show coherence over various multiple phases. I will describe various issues with parallel random number generation for multiple threads, multiple processors, and multiple architectures (including GPU's) and a possible improvement which I will test with simulation.

As a continuation of a previous talk, I will also show how the stochastic matrix of a probabilistic automaton computed asynchronously on a graph can be simplified with two specific examples of metrics and equivalence classes. I will show how the $$16\times 16$$ stochastic matrix of a specific automaton on $$\mathrm{C}_4$$ can be reduced to a $$3\times 3$$ stochastic matrix by using a stability metric as an equivalence class; and I will show how the $$2^{n+1}\times 2^{n+1}$$ stochastic matrix of this automaton on a star-graph $$S_n=K_{1,n}$$ can be reduced to matrix of size $$(2n+2)\times (2n+2)$$ by using Hamming distance from a particular state as an equivalence class.

## Monday, February 22, 2010

No seminar this week.

## Monday, February 15, 2010

No seminar this week.

## Monday, February 8, 2010

Title
Speaker
Time
Place

A Matrix form of the Jacobi-Trudi Identity
Neranga Fernando
3:05pm-3:55pm
PHY 108

Abstract

The Jacobi-Trudi Identity is a well known formula which expresses the Schur functions as a determinant of the complete homogeneous symmetric functions. We found a matrix form of the Jacobi-Trudi Identity.

## Monday, February 1, 2010

Title
Speaker
Time
Place

Combinatorial Dynamics, Part II
Erik Lundberg
3:05pm-3:55pm
PHY 108

Abstract

We will continue to consider iteration of a continuous function as a dynamical system. After finishing a sketch of the proof of Sharkovsky's Theorem, we will raise a related question which turns out to reduce to a problem purely in combinatorics. Namely, how often do cyclic permutations $$p$$ have the property that for some $$i < j$$, $$p(i) < i < j < p(j)$$? We give an asymptotic answer, which appends a statistical “however” to Sharkovsky's Theorem.

## Monday, January 25, 2010

Title
Speaker
Time
Place

Combinatorial Dynamics
Erik Lundberg
3:05pm-3:55pm
PHY 108

Abstract

We will consider iteration of continuous functions as a simple example of a deterministic dynamical system where space is one-dimensional and time is discrete. An initial state that returns to itself after $$n$$ iterations is called a period-$$n$$ point, and its trajectory induces a cyclic permutation of size $$n$$.

The occurrence of a period-$$n$$ point can guarantee the occurrence of a period-$$m$$ point for values of $$m$$ depending on $$n$$. Surprisingly, a period-$$3$$ point guarantees periodic points of every period. Sharkovsky's Theorem gives an exhaustive description of the coexistence of periodic points. To glimpse the proof and to ask questions not answered by Sharkovsky's Theorem requires attention to the combinatorial structure of periodic trajectories. This will be our main focus. We will see that in spite of the strict ordering given by Sharkovsky's Theorem, there is a statistical “however” when all orbit types (induced cyclic permutations) are taken into account. Time permitting, we will briefly discuss knot types of periodic trajectories in three-dimensional flows as another instance of “combinatorial dynamics”.