# Research

## Discrete Mathematics

### Thursday, April 28, 2005

Title: TBA
Speaker: David Kephart
Time: 4:00pm‐5:00pm
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:00pm‐5:00pm
Place: LIF 269

### Thursday, April 14, 2005

Title: On a vector space analogue of Kneser's theorem
Speaker: Xiang-Dong Hou
Time: 4:00pm‐5:00pm
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:00pm‐5:00pm
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:00pm‐5:00pm
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:00pm‐5:00pm
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:00pm‐5:00pm
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:00pm‐5:00pm
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:00pm‐5:00pm
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:00pm‐5:00pm
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:00pm‐5:00pm
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:00pm‐5:00pm
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:00pm‐5:00pm
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:00pm‐5:00pm
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.