187 – List of all presentations

January 10, 2012

For ease, I re-list here all the presentations we had throughout the term. I also include some of them. If you gave a presentation and would like your notes to be included, please email them to me and I’ll add them here.

  • Jeremy Elison, Wednesday, October 12: Georg Cantor and infinity.
  • Kevin Byrne, Wednesday, October 26: Alan Turing and Turing machines.
  • Keith Ward, Monday, November 7: Grigori Perelman and the Poincaré conjecture.
  • David Miller, Wednesday, November 16: Augustin Cauchy and Cauchy’s dispersion equation.
  • Taylor Mitchell, Friday, November 18: Lajos Pósa and Hamiltonian circuits.
  • Sheryl Tremble, Monday, November 28: Pythagoras and the Pythagorean theorem.
  • Blake Dietz, Wednesday, November 30: \mbox{\em Paul Erd\H os} and the Happy End problem.

Here are Jeremy’s notes on his presentation. Here is the Wikipedia page on Cantor, and a link to Cantor’s Attic, a wiki-style page discussing the different (set theoretic) notions of infinity.

Here are a link to the official page for the Alan Turing year, and the Wikipedia page on Turing. If you have heard of Conway’s Game of Life, you may enjoy the following video showing how to simulate a Turing machine within the Game of Life; the Droste effect it refers to is best explained in by H. Lenstra in a talk given at Princeton on April 3, 2007, and available here.

Here is a link to the Wikipedia page on Perelman, and the Clay Institute’s description of the Poincaré conjecture. In 2006, The New Yorker published an interesting article on the unfortunate “controversy” on the priority of Perelman’s proof.

Here are David’s slides on his presentation, and the Wikipedia page on Cauchy.

Here is a link to Ross Honsberger’s article on Pósa (including the result on Hamiltonian circuits that Taylor showed during her presentation).

Here are Sheryl’s slides on Pythagoras and his theorem. In case the gif file does not play, here is a separate copy:

The Pythagorean theorem has many proofs, even one discovered by President Garfield!

Finally, here is the Wikipedia page on \mbox{Erd\H os}. Oakland University has a nice page on him, including information on the \mbox{Erd\H os} number; see also the page maintained by Peter Komjáth, and an online depository of most of \mbox{Erd\H os's} papers.

Leave a Comment » | 187: Discrete mathematics | Tagged: , , , , , , | Permalink
Posted by andrescaicedo

580 -Partition calculus (4)

April 9, 2009

 

1. Colorings of pairs. I

 

There are several possible ways in which one can try to generalize Ramsey’s theorem to larger cardinalities. We will discuss some of these generalizations in upcoming lectures. For now, let’s highlight some obstacles.

Theorem 1 ({\mbox{Erd\H os}}-Kakutani) {\omega_1\not\rightarrow(3)^2_\omega.} In fact, {2^\kappa\not\rightarrow(3)^2_\kappa.}

 

Proof: Let {S={}^\kappa\{0,1\}.} Let {F:[S]^2\rightarrow\kappa} be given by

\displaystyle F(\{f,g\})=\mbox{least }\alpha<\kappa\mbox{ such that }f(\alpha)\ne g(\alpha).

Then, if {f,g,h} are distinct, it is impossible that {F(\{f,g\})=F(\{f,h\})=F(\{g,h\}).} \Box

Theorem 2 (Sierpi\’nski) {\omega_1\not\rightarrow(\omega_1)^2.} In fact, {2^\kappa\not\rightarrow(\kappa^+)^2.}

 

Proof: With {S} as above, let {F:[S]^2\rightarrow2} be given as follows: Let {<} be a well-order of {S} in order type {2^\kappa.} Let {<_{lex}} be the lexicographic ordering on {S.} Set

\displaystyle F(\{f,g\})=1\mbox{ iff }<_{lex}\mbox{ and }<\mbox{ coincide on }\{f,g\}.

Lemma 3 There is no {<_{lex}}-increasing or decreasing {\kappa^+}-sequence of elements of {S.}

 

Proof: Let {W=\{f_\alpha\colon\alpha<\kappa^+\}} be a counterexample. Let {\gamma\le\kappa} be least such that {\{f_\alpha\upharpoonright\gamma\colon\alpha<\kappa^+\}} has size {\kappa^+,} and let {Z\in[W]^{\kappa^+}} be such that if {f,g\in Z} then {f\upharpoonright\gamma\ne g\upharpoonright\gamma.} To simplify notation, we will identify {Z} and {W.} For {\alpha<\kappa^+} let {\xi_\alpha<\gamma} be such that {f_\alpha\upharpoonright\xi_\alpha=f_{\alpha+1} \upharpoonright\xi_\alpha} but {f_\alpha(\xi_\alpha)=1-f_{\alpha+1}(\xi_\alpha).} By regularity of {\kappa^+,} there is {\xi<\gamma} such that {\xi=\xi_\alpha} for {\kappa^+} many {\alpha.}

But if {\xi=\xi_\alpha=\xi_\beta} and {f_\alpha\upharpoonright\xi=f_\beta\upharpoonright\xi,} then {f_\beta<_{lex} f_{\alpha+1}} iff {f_\alpha<_{lex} f_{\beta+1},} so {f_\alpha=f_\beta.} It follows that {\{f_\alpha\upharpoonright\xi\colon\alpha<\kappa^+\}} has size {\kappa^+,} contradicting the minimality of {\gamma.} \Box

The lemma implies the result: If {H\subseteq S} has size {\kappa^+} and is {F}-homogeneous, then {H} contradicts Lemma 3. \Box

Now I want to present some significant strengthenings of the results above. The results from last lecture exploit the fact that a great deal of coding can be carried out with infinitely many coordinates. Perhaps surprisingly, strong anti-Ramsey results are possible, even if we restrict ourselves to colorings of pairs.

Read the rest of this entry »

3 Comments | 580: Topics in set theory | Tagged: , , , , , , , , , , , , | Permalink
Posted by andrescaicedo

580 -Partition calculus (3)

April 6, 2009

 

1. Infinitary Jónsson algebras

 

Once again, assume choice throughout. Last lecture, we showed that {\kappa\not\rightarrow(\kappa)^{\aleph_0}} for any {\kappa.} The results below strengthen this fact in several ways.

Definition 1 Let {x} be a set. A function {f:[x]^{\aleph_0}\rightarrow x} is {\omega}-Jónsson for {x} iff for all {y\subseteq x,} if {|y|=|x|,} then {f''[y]^{\aleph_0}=x.}

 

Actually, for {x=\lambda} a cardinal, the examples to follow usually satisfy the stronger requirement that {f''[y]^\omega=\lambda.} In the notation from Definition 16 from last lecture, {\lambda\not\rightarrow[\lambda]^\omega_\lambda.}

The following result was originally proved in 1966 with a significantly more elaborate argument. The proof below, from 1976, is due to Galvin and Prikry.

Theorem 2 (Erdös-Hajnal) For any infinite {x,} there is an {\omega}-Jónsson function for {x.}

 

Read the rest of this entry »

3 Comments | 580: Topics in set theory | Tagged: , , , , , | Permalink
Posted by andrescaicedo

580 -III. Partition calculus

March 21, 2009

 

1. Introduction

Partition calculus is the area of set theory that deals with Ramsey theory; it is devoted to Ramsey’s theorem and its infinite and infinitary generalizations. This means both strengthenings of Ramsey’s theorem for sets of natural numbers (like the Carlson-Simpson or the Galvin-Prikry theorems characterizing the completely Ramsey sets in terms of the Baire property) and for larger cardinalities (like the {\mbox{Erd\H os}}-Rado theorem), as well as variations in which the homogeneous sets are required to possess additional structure (like the Baumgartner-Hajnal theorem).

Ramsey theory is a vast area and by necessity we won’t be able to cover (even summarily) all of it. There are many excellent references, depending on your particular interests. Here are but a few:

  • Paul {\mbox{Erd\H os},} András Hajnal, Attila Máté, Richard Rado, Combinatorial set theory: partition relations for cardinals, North-Holland, (1984).
  • Ronald Graham, Bruce Rothschild, Joel Spencer, Ramsey theory, John Wiley & Sons, second edn., (1990).
  • Neil Hindman, Dona Strauss, Algebra in the Stone-{\mbox{\bf \v Cech}} compactification, De Gruyter, (1998).
  • Stevo {\mbox{Todor\v cevi\'c},} High-dimensional Ramsey theory and Banach space geometry, in Ramsey methods in Analysis, Spiros Argyros, Stevo {\mbox{Todor\v cevi\'c},} Birkhäuser (2005), 121–257.
  • András Hajnal, Jean Larson, Partition relations, in Handbook of set theory, Matthew Foreman, Akihiro Kanamori, eds., to appear.

I taught a course on Ramsey theory at Caltech a couple of years ago, and expect to post notes from it at some point. Here we will concentrate on infinitary combinatorics, but I will briefly mention a few finitary results.

Read the rest of this entry »

6 Comments | 580: Topics in set theory | Tagged: , , , , , , , , , , , | Permalink
Posted by andrescaicedo