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, April 20, 2015

Title
Speaker
Time
Place

An Erdös-type problem in plane geometry
Jeremy Kerr
2:00pm-3:00pm
CMC 108

Abstract

TBA

## Monday, April 13, 2015

Title
Speaker
Time
Place

The Frankl-Wilson Theorem, Its Modular Counterpart, and Applications
Greg Churchill
2:00pm-3:00pm
CMC 108

Abstract

Last Monday in the Discrete Math Seminar, John Theado provided a constructive lower bound on the diagonal Ramsey numbers $$R(t,t)$$ where $$t$$ is large. To prove his construction was adequate, he relied on the famous Frankl-Wilson theorem for $$L$$-intersecting families, and also made use of its modular counterpart (due to Deza, Frankl, Singhi).

For this talk, the speaker will prove the Frankl-Wilson theorem and its modular counterpart, and state some other attractive applications of these theorems.

## Monday, April 6, 2015

Title
Speaker
Time
Place

Constructive Lower Bounds on Ramsey Numbers
2:00pm-3:00pm
CMC 108

Abstract

The Ramsey number $$R(s,t)$$ is the smallest integer n such that a complete graph on $$n$$ vertices whose edges have been arbitrarily colored with red and blue must contain either a complete subgraph on $$s$$ vertices with all red edges or a complete subgraph on $$t$$ vertices with all blue edges. For the interesting cases where $$s$$ and $$t$$ are at least 3, very few Ramsey numbers are known precisely. This talk will be focused primarily on lower bounds for diagonal Ramsey numbers $$R(t,t)$$. We will see a nonconstructive proof due to Paul Erdös that verifies an exponential lower bound that is nearly the best known. As for constructive lower bounds, however, the best known are only sub-exponential and we will explore some of these including one which gives a superpolynomial bound. When finished, we will be left with the following question: Is it possible to give a constructive exponential bound?

## Monday, March 30, 2015

Title
Speaker
Time
Place

A connected 3-state reversible Mealy automaton cannot generate an infinite periodic group
Dmytro Savchuk
2:00pm-3:00pm
CMC 108

Abstract

The class of automaton groups is a rich source of the simplest examples of infinite Burnside groups. However, there are some classes of automata that do not contain such examples. For instance, all infinite Burnside automaton groups in the literature are generated by non-reversible Mealy automata and it was recently shown that 2-state invertible-reversible Mealy automata cannot generate infinite Burnside groups. Here we extend this result to connected 3-state invertible-reversible Mealy automata, using new original techniques. The results provide the first uniform method to construct elements of infinite order in each infinite group in this class. This is a joint work with Ines Klimann and Matthieu Picantin.

## Monday, March 23, 2015

Topic
Time
Place

Organizational Meeting
2:00pm-3:00pm
CMC 108

Abstract

The Discrete Mathematics Seminar is one of several sections of the graduate seminar class. This class is partly experimental, providing students with a chance to practice presenting talks and listening to talks presented by faculty.

So how well is it working? For the discrete mathematics seminar, how well is it working? That will be subject of this discrete mathematics seminar meeting. All discrete mathematics faculty are especially encouraged to come, and all faculty are invited. This is not a regular meeting of seminar, so attendance by enrolled students is not required.

We will return to our regularly scheduled programming at the next meeting on March 30.

## Monday, March 16, 2015

Title
Speaker

Time
Place

A geometric approach to understanding neural codes in recurrent networks
Carina Curto
Pennsylvania State University
2:00pm-3:00pm
CMC 108

Abstract

Synapses in many cortical areas of the brain are dominated by local, recurrent connections. It has long been suggested, therefore, that cortical networks may serve to restore a noisy or incomplete signal by evolving it towards a stored pattern of activity. These “preferred” activity patterns are constrained by the network's connections, and are typically modeled as stable fixed points of the dynamics. In this talk I will briefly review the permitted and forbidden sets model for cortical networks, first introduced by Hahnloser et al. (Nature, 2000), and then present some recent results that provide a geometric handle on permitted sets. Specifically, I will show how questions about fixed points can be translated to questions in classical distance geometry. Finally, I will use the geometric description of fixed points to show that these networks can perform error correction and pattern completion for a wide range of connectivities.

## Monday, March 9, 2015

The seminar is cancelled this week.

Spring Break

## Monday, February 23, 2015

Title
Speaker
Time
Place

Medical Image Generation, Segmentation, and Analysis Algorithms
Apurva Bhatty
2:00pm-3:00pm
CMC 108

Abstract

2-dimensional and 3-dimensional imagery can be generated from hierarchical medical models, and 2-d and 3-d imagery derived from human subjects (such as 3-d computerized tomography) can be analyzed with various digital image processing techniques to decompose and segment the image into subcomponents and to analyze the underlying structure into a hierarchical arrangement. Examples in non-medical imaging are the segmentation of an image into “foreground” and “background” components, image classification, and feature extraction. The models can be presented as diagrams using the PostScript language, or as interactive dynamic 3-d visualizations using the OpenGL language for clinical assessment, diagnosis, and treatment.

Once the image components have been identified and labeled, the image can be transformed and distorted by “morphing” into a canonical form for further analysis and understanding (conversely, the inverse transform yielding the changes from the canonical form to the individual subject's morphology can be derived). The algorithms that accomplish these transforms need to be speeded up to yield real-time processing capabilities on very large medical images ($$2048^3$$ voxels) or video streams ($$1024^2$$ at 120 Hz), thus it is important to understand the computational complexity of these algorithms along with their effect on information within the image: iterative vs. noniterating, local neighborhood calculations vs. global calculations, lossy vs. lossless. I will review the basics of these image processing techniques and algorithms, along with a little about how the human retina and brain also performs some of these functions.

## Monday, February 16, 2015

The seminar is cancelled this week.

## Monday, February 9, 2015

The seminar is cancelled this week.

## Monday, February 2, 2015

Title
Speaker

Time
Place

Ideal lattices and tomorrow's challenges in cryptology
Jean-François Biasse
University of Waterloo
Waterloo, ON
2:00pm-3:00pm
CMC 108

Abstract

Euclidean lattices are elementary structures that occur in many areas of algebra. More recently, it has been the focus of tremendous attention from the cryptographic community. Indeed, lattice-based cryptography allows solutions for two of the main challenges for the future of cryptology: homomorphic encryption and quantum resistance.

Homomorphic encryption consists of allowing a third party to modify an encrypted message without knowing the secret key. It has applications to situations where data is stored on an untrusted remote device. This allows us to secure computations on the cloud, which is a major industrial stake. A proof of concept exists, but new ideas are required to make homomorphic encryption practical.

Quantum-resistant cryptography is the design of cryptosystems which will resist to the attacks from quantum computers. The existing public-key cryptosystems are not quantum-safe, which is why it there is a growing need for the analysis of the security of their alternatives.

During the talk, I will introduce these notions, and discuss the use of lattices arising as ideals in number fields (ideal lattices) in lattice-based cryptography.

## Monday, January 26, 2015

Title
Speaker
Time
Place

A solution to Greg Churchill's problem and related ideas
Edwin Clark
2:00pm-3:00pm
CMC 108

Abstract

Recently Greg Churchill asked for an example of a collection $$A_1,A_2,\dotsc,A_k$$ of subsets of $$[n]=\{1,2,\dotsc,n\}$$ where

1. $$(n)$$ is odd.
2. The sets $$A_i$$ are odd and $$\mathrm{card}\left(A_i\right)>n/2$$.
3. The intersections of $$A_i$$ and $$A_j$$ have even cardinality.
4. $$k$$ is approximately $$n$$.
5. Each $$i$$ in $$[n]$$ is contained in at least $$n/2$$ of the $$A_j$$.

I will present a solution for all odd $$n>8$$ divisible by $$3$$ where $$k=n$$ and the $$n/2$$ in the above list are replaced by $$(2/3)\,n-1$$.

I will discuss graph theoretic and group theoretic connections to the question and how Maple did most of the work in finding my solution.

## Monday, January 19, 2015

MLK Holiday — no seminar this week.

## Monday, January 12, 2015

Title
Speaker
Time
Place

The Odd Town, and Her Drastically Different Sister City
Greg Churchill
2:00pm-3:00pm
CMC 108

Abstract

Consider a family of sets on $$n$$ points in which each member is of odd order but where any pair of distinct members intersects in evenly many points. The odd-town theorem states that such a family can only have at most $$n$$ sets.

For this talk we will prove the odd town theorem, and consider a slight change in its hypothesis that yields a remarkably different conclusion.

Time permitting, a word will be said on bad conjectures.

## Monday, January 5, 2015

Topic
Speaker
Time
Place

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

Abstract

TBA