University of South Florida

College of Arts and Sciences

Search

Menu

Give Now

Title: Graph Transversals and Transversals of Faces Speaker: Joy D'Andrea Time: 3:05pm‐3:55pm Place: PHY 108

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.

Title: Factorial-local Cellular Automata Speaker: Egor Dolzhenko Time: 3:05pm‐3:55pm Place: PHY 108

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.

Title: Involution codes applied to DNA Coding Speaker: Andrew Burruss Time: 3:05pm‐3:55pm Place: PHY 108

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.

No seminar this week.

Title: The Acceptance Urn Model Speaker: Kevin Wagner Time: 3:05pm‐3:55pm Place: PHY 108

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.

Title: Anonymous ID Assignment for Data Mining Speaker: Larry Dunning Time: 3:05pm‐3:55pm Place: PHY 108

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.

Title: Forbidding-Enforcing Classes of Graphs Speaker: Daniela Genova, University of North Florida Time: 3:05pm‐3:55pm Place: PHY 108

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.

Title: Coherence in Random Number Generators used in Parallel Distributed Systems Speaker: Apurva Bhatty Time: 3:05pm‐3:55pm Place: PHY 108

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.

Title: A Matrix form of the Jacobi-Trudi Identity Speaker: Neranga Fernando Time: 3:05pm‐3:55pm Place: PHY 108

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.

Title: Combinatorial Dynamics, Part II Speaker: Erik Lundberg Time: 3:05pm‐3:55pm Place: PHY 108

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.

Title: Combinatorial Dynamics Speaker: Erik Lundberg Time: 3:05pm‐3:55pm Place: PHY 108

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”.