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

Mathematics & Statistics

# Discrete Mathematics (Leader: Prof. Greg McColm)

## Thursday, April 28, 2005

 Title TBA Speaker David Kephart Time 4:00-5:00 p.m. Place LIF 269

## Thursday, April 21, 2005

 Title On a vector space analogue of Kneser's theorem, Part II Speaker Xiang-Dong Hou Time 4:00-5:00 p.m. Place LIF 269

## Thursday, April 14, 2005

 Title On a vector space analogue of Kneser's theorem Speaker Xiang-Dong Hou Time 4:00-5:00 p.m. Place LIF 269

Abstract

The following is a well known theorem in additive number theory:

Theorem 1 (Kneser, 1953) Let $$G$$ be an ableian group, written multiplicatively, and let $$A$$, $$B$$ be nonempty finite subsets of $$G$$. Then $$|AB|\ge |A|+|B|-|H(AB)|$$, where $$AB=\{ab:a\in A,b\in B\}$$ and $$H(AB)=\{g\in G:gAB=AB\}$$ is the stabilizer of $$AB$$.

Recently, a vector space analogue of Kneser's theorem was found:

Theorem 2 (Hou, Leung, Xiang, 2002 JNT) Let $$E\subset K$$ be fields and let $$A$$, $$B$$ be $$E$$-subspace of $$K$$ such that $$0<\dim A<\infty$$, $$0<\dim B<\infty$$. Assume that the algebraic closure of $$E$$ in $$K$$ is separable over $$E$$. Then $$\dim AB\ge\dim A+\dim B-\dim H(AB)$$ where $$AB$$ is the $$E$$-space generated by $$\{ab:a\in A,b\in B\}$$ and $$H(AB)=\{x\in K:xAB=AB\}$$ is the stabilizer of $$AB$$ in $$K$$.

In part I of this talk, we will review the proof Theorem 2. We conjecture that Theorem 2 remains true without the separability assumption. In part II of this talk, we will prove the conjecture with $$\dim A<5$$.

## Thursday, April 7, 2005

 Title Transitivity in Two-dimensional Languages Speaker Joni Pirnot Time 4:00-5:00 p.m. Place LIF 269

Abstract

In one-dimensional language theory, a language is said to be transitive if for every pair of words in the language, there exists a sequence of symbols from the alphabet that can ‘paste’ the two words together, forming another (longer) word that appears in the language.

In two dimensions, the definition of transitivity is not so straightforward. Dot systems are used to illustrate the need for an expanded notion of transitivity when discussing two-dimensional languages.

## Thursday, March 31, 2005

 Title Generating SAT solution spaces via splicing rules Speaker Giuditta Franco Time 4:00-5:00 p.m. Place LIF 269

Abstract

An ambition of DNA Computing is to solve NP-Complete problems in linear time. The generation of the solution space is the first step of the classical method for solving, in particular, an instance of SAT. For this problem, I will present some combinatorial features of a (string) generation procedure based on null context splicing rules. I will also discuss the generalization to the case of non-boolean variables.

## Thursday, March 24, 2005

 Title On Radical Deformations of Zero-dimensional Ideals Speaker Boris Shekhtman Time 4:00-5:00 p.m. Place LIF 269

Abstract

I will give a counterexample to a conjecture of Carl de Boor, showing that in the ring of polynomials in three or more variables there exist zero-dimensional ideals that do not admit radical deformations.

Time permitting, I will also propose an open problem that I think will be of interest to this particular audience.

## Thursday, March 10, 2005

 Title Surveillance and Forecasting for Waterborne Infections Speaker Ian McNeill Department of Statistical and Actuarial Sciences University of Western Ontario Time 4:00-5:00 p.m. Place LIF 269 Note This is a special session of the Complex Systems seminar.

Abstract

A system is discussed for monitoring case count data on infections with a view to early detection of outbreaks and to forecasting the extent of detected outbreaks. The system is called INFERNO — a system for INtegrated Forecasts and EaRly eNteric Outbreak detection. Historical data are smoothed using a loess-type smoother. Upon receipt of a new datum, the smoothing is updated and estimates are made of the first two derivatives of the smooth curve and these are used for near-term forecasting. Recent data and the near-term forecasts are used to compute a warning index. The algorithms for computing the warning index and the interpretation of the index have been designed to effect a balance between Type I errors (false prediction of an epidemic) and Type II errors (failure to correctly predict an epidemic). If the warning index signals a sufficiently high probability of an epidemic, then a forecast of the probable size of the outbreak is made. This longer-term forecast is made by fitting a “signature” curve to the available data. The effectiveness of the forecast depends upon the extent to which the signature curve captures the shape of outbreaks of the infection under consideration. Also, since the success of forecasting is partly determined by the timeliness of the data, and since data are not usually available on a next-day basis, a discussion is provided of a methodology of adjusting for reporting-delay.

## Thursday, March 3, 2005

 Title A subgroup of the braid group associated with Fox's colorings Speaker Shin Satoh Time 4:00-5:00 p.m. Place LIF 269

Abstract

The set of braids with Fox's colorings, whose top and bottom strings have the same vector of given colors, forms a subgroup of the braid group. We construct a certain $$2$$-complex from the vector, and prove that the subgroup is isomorphic to the fundamental group of the $$2$$-complex. In particular, we demonstrate the case of $$3$$-string braids with $$3$$-colorings.

## Thursday, February 24, 2005

 Title Polynomial quandle cocycles and knot applications Speaker Kheira Ameur Time 4:00-5:00 p.m. Place LIF 269

Abstract

We construct new cocycles for Alexander quandles by polynomial expressions, then we use them to compute quandle cocycle invariants for $$(2,m)$$-torus knots and their twist spins.

## Thursday, February 17, 2005

 Title On a Theorem of Schur Speaker Peter Hilton Distinguished Professor Emeritus State University of New York, Binghamton Time 4:00-5:00 p.m. Place LIF 269

Abstract

I. Schur proved that if $$G$$ is a group, $$Z$$ its center and $$G'$$ its commutator subgroup, and if $$G/Z$$ is finite, then $$G'$$ is finite. Given a certain supplementary condition, the converse also holds.

In this talk we prove the analog of Schur's Theorem and its converse in the context of nilpotent groups. For such groups one can localize the problem at a given family of primes $$P$$.

We also show how to relativize the theorem by replacing $$G$$ by the pair $$(G,N)$$, where $$N$$ is normal in $$G$$, and replacing $$Z$$ by $$C_G(N)$$, the centralizer of $$N$$ in $$G$$.

## Thursday, February 10, 2005

 Title Divisibility properties of Fibonacci and Lucas numbers Speaker Peter Hilton Distinguished Professor Emeritus State University of New York, Binghamton Time 4:00-5:00 p.m. Place LIF 269

Abstract

We establish divisibility relations between Fibonacci and Lucas numbers. One very striking result is the following: If the Fibonacci number $$F_m$$ divides some Lucas number $$L_n$$, then $$F_m=1$$, $$2$$ or $$3$$. Another surprising result is that if $$L_n$$ divides $$F_m$$, then $$F_n$$ divides $$F_m$$ and yet $$L_n$$ and $$F_n$$ are “almost” coprime.

## Thursday, February 3, 2005

 Title Logical Operators III: the Transitive Closure Operator Speaker Professor Greg McColm Time 4:00-5:00 p.m. Place LIF 269

Abstract

This is the third of three talks aimed at describing lattice-valued (e.g., boolean and/or fuzzy) Least Fixed Point logic and the Transitive Closure operator, a logical operator intimately connected with NLOGSPACE.

In this talk, we present the Transitive Closure Operator, and a game-theoretic representation of it.

## Thursday, January 27, 2005

 Title Logical Operators II: Game Semantics Speaker Professor Greg McColm Time 4:00-5:00 p.m. Place ENC 1002

Abstract

This is the second of several talks aimed at describing lattice-valued (e.g., boolean and/or fuzzy) Least Fixed Point logic and the Transitive Closure operator, a logical operator intimately connected with NLOGSPACE.

In this talk, we present a game-theoretic logic based on operators on a lattice of game-value functions.

## Thursday, January 20, 2005

 Title Logical Operators I: Fixed Points Speaker Professor Greg McColm Time 4:00-5:00 p.m. Place NES 103

Abstract

This is the first of several talks aimed at describing the Transitive Closure operator, a logical operator intimately connected with NLOGSPACE.

In this talk, we start at the beginning, with a description of operators on lattices, the existence and construction of fixed points of operators, and the consequent extension of First Order logic.