Friday Math Seminar Spring 2007 Schedule

 

Date	Location	Speaker	Topic
April 20, 2007	Fowler 309 12:30 pm	Eric Sundberg Occidental College	Proving Fisher's Inequality with Linear Algebra
	This week we will use linear algebra to prove a generalization of Fisher's inequality. You can state a dual version of the generalized Fisher's inequality as follows. Suppose that you have collection of (distinct) subsets of {1,2,...,n} so that every two distinct subsets from your collection intersect each other in exactly k points and each subset has (strictly) more than k points. Then your collection can only contain at most n subsets.
April 13, 2007	Fowler 309 12:30 pm	Cheng Yeaw Ku California Institute of Technology	Erdos-Ko-Rado for Permutations and Set Partitions
	Suppose we have a set of permutations of {1, ..., n} in which any two of its members have at least t cycles in common. How large can this set be? We may also ask the same question for a collection of set partitions such that any two of them have at least t blocks in common. In this talk, we shall attempt to answer these questions. This is a joint work with David Renshaw.
April 6, 2007	Fowler 309 12:30 pm	Cheng Yeaw Ku California Institute of Technology	Intersecting Families and Designs in Combinatorics
	In this talk, we consider several new and classical results about intersecting families of several different types of combinatorial objects. Interestingly, they form a class of problems in Extremal Combinatorics which can be solved whenever certain highly regular combinatorial designs exist.
March 30, 2007	Fowler 309 12:30 pm	Eric Sundberg Occidental College	Extending Latin Rectangles to Latin Squares
	This week we will discuss how to extend a Latin Rectangle to a Latin Square. You can think of a Latin square as an n x n matrix whose entries are from the set {1,2,...,n} such that each row contains exactly one 1, exactly one 2, ..., exactly one n, and likewise for each column. A Latin Rectangle is an r x n matrix with r < n where each row contains exactly one 1, exactly one 2, ..., exactly one n, and each column contains at most one 1, at most one 2, ..., at most one n. We will use an old friend from last week in order to help us achieve our goal.
March 23, 2007	Fowler 309 12:30 pm	Eric Sundberg Occidental College	Hall's Marriage Theorem
	This week we will discuss Hall's Marriage theorem. You can view the theorem in the following context. Suppose that you have $n$ kids and a toy box with $m$ toys. Each kid has a list of toys that s/he would like to have. We wish to give each kid one toy from the toy box. Under what conditions are we guaranteed that each kid will receive a toy that s/he wants? In a wonderful fashion Hall's Marriage theorem answers this question for us. We will prove the Marriage theorem and hopefully have time to give an example of the Marriage theorem in action.
March 9, 2007	Fowler 309 12:30 pm	Adrian Ferenc Occidental College	Fibonacci Triangle
	This week we will have an active seminar because we'll attack a ``Fibonacci Triangle'' that Adrian Ferenc has graciously volunteered for our use. Adrian has discovered certain properties that this triangle possesses, and together we will spend the hour proving that these properties are indeed correct. It should be really fun!
March 2, 2007	Fowler 309 12:30 pm	Eric Sundberg Occidental College	Ramsey Theory (A Lower Bound)
	This week we'll finish our current series on Ramsey Theory by finding a lower bound for the Ramsey numbers. The proof will use the Probabilistic Method and will be very non-constructive. We'll essentially prove that there *exists* a 2-coloring of the complete graph with $2^{k/2}$ vertices that contains neither a red $k$-clique, nor a blue $k$-clique. The proof method is very interesting and very powerful, so I suggest that you do your best to make it to this talk. It's a great way to finish off the series!
February 23, 2007	Fowler 309 12:30 pm	Eric Sundberg Occidental College	Infinite Ramsey Theory
	This week we'll continue with Ramsey Theory by examining the infinite version of the question. For example, we may state infinite Ramsey as, ``if you have a countably infinite number of people crammed into a mondo room, then you're guaranteed to find an infinite number of them who all know each other, or an infinite number of them who all don't know each other.'' Stated in terms of graph theory, ``if you take the complete graph on the natural numbers and color each of its edges either red or blue, then you are guaranteed to find either an infinite red clique\footnote{A clique is a subgraph which contains all of its possible edges. Thus a clique with $k$ vertices (or $k$-clique) is a subgraph with $k$ vertices and ${k \choose 2} = k(k-1)/2$ edges.} or an infinite blue clique.''
February 16, 2007	Fowler 309 12:30 pm	Eric Sundberg Occidental College	Ramsey Theory
	What's the smallest number of people you can have in a room to guarantee that you can find a group of three of them who either all mutually know each other or all mutually don't know each other?