Contest Pigeons!

(This is a talk I gave for the Canadian IMO team at their 2014 winter camp at York University on Jan 3, 2014.)

The pigeonhole principle is a remarkable combinatorial theorem that looks silly and obvious, but turns out to be quite powerful and useful, especially in the context of contest problem solving. I’m going to present a couple of statements of the pigeonhole principle, then I’ll give some broad applications of it. I’ll end off with a list of problems.

Found them!

Continue reading Contest Pigeons!

Using Dushnik-Miller to prove that every sigma-compact group is ccc

(This is the write-up for a talk I gave in the Toronto Student Set Theory and Topology seminar on May 2, 2013.)

A couple of weeks ago I gave a talk for the set-theoretic topology course I was in, on the topic of cardinal invariants of topological groups. While I was preparing that presentation I discovered the following fact:

Theorem [Tkachenko, 1983] Every \sigma -compact group is ccc.

I will present a proof that I have adapted from Tkachenko’s original paper (“Souslin property in free topological groups on bicompacta”) and the proof that appears in Arhangel’skii & Tkachenko’s big purple book (Section 5.3 of Topological Groups and Related Structures). Both proofs involve first proving a Ramsey result about covers of a space, then using this to prove that a particular space has “weak-precalibre \aleph_1 ” (i.e. Property K) which is a property that implies ccc. Learning this proof has been part of my ongoing attempt to learn how Ramsey results show up in topology.

Continue reading Using Dushnik-Miller to prove that every sigma-compact group is ccc

A Survey of Cardinal Invariants of Topological Groups

(This is a presentation I gave for Bill Weiss’ course Set-Theoretic Topology on April 19, 2013. In class we discussed some cardinal invariants and how they are related; here I will survey what happens when we look at the cardinal invariants of topological groups.)

This review follows very closely the discussion in section 5.2 of Arhangel’skii and Tkachenko’s book “Topological Groups and Related Structures“. Another good resource is section 3 of Comfort’s article “Topological Groups” in the Handbook of Set-Theoretic Topology. The only thing I claim to be my own are the (unsourced) pictures I have provided.

Continue reading A Survey of Cardinal Invariants of Topological Groups

Kangaroo Contest 2013 Talk about Cryptography

On Sunday March 24, 2013, I gave a talk on the History of Cryptography [PDF], at the University of Toronto (Scarborough) for the parents of students writing the Kangaroo Contest. I had many questions after my talk, so here are some answers to the questions I received.


Where did you get this information?

Most of this talk came from Elementary Number Theory by David M. Burton, the Wikipedia article for RSA, and the Wikipedia article for Diffie-Hellman. As a general rule of thumb, Wikipedia is a reliable source for things of a mathematical nature (as only experts tend to edit the articles).

My child is interested in codes, what are some resources for them to learn more?

Here is a great introduction to modular arithmetic which serves as the foundation for learning about the math of cryptography. Modular arithmetic is like “clock math”, where 4 hours after 10 o’clock is 2 o’clock.

Codecademy is a very good way to start learning computer programming. It is a very fun website and is very motivating, and fun!

Continue reading Kangaroo Contest 2013 Talk about Cryptography

Let’s Make Some T-sequences

(This was the basis for a talk I gave at the Toronto Student Set Theory and Topology seminar on January 15, 2013. The assumed knowledge is an undergraduate course in general topology. This is only a draft, and will be updated soon.)


There are many questions in mathematics and sciences in general whose main object of study is the topological group. These objects are very versatile and can represent many of the structures we encounter. One question that I’ve been working on examines the (extreme) dynamical properties of topologies on the integers. On the recommendation of Vladimir Pestov (one of my advisors) I have been learning about T-sequences, which provide a rich method for producing topological groups with extreme behaviour. Here I will present two techniques involving T-sequences that help to answer two different questions about topological groups; one is about dynamics and the other is about combinatorial properties of \mathbb{N}^\N . These results all come from “Topologies on the Integers” by Protasov and Zelenyuk.

Continue reading Let’s Make Some T-sequences

Hindman’s Theorem write-up

It came to my attention that Leo Goldmakher had written up notes for a lecture I gave in August 2011 on the proof of Hindman’s Theorem via ultrafilters. The notes are quite nice so I thought I would share them.

Here is a link to the notes (pdf) and here is Leo’s website.

The lecture I gave follows the papers:

  • “An Algebraic Proof of van der Waerden’s Theorem” by Vitaly Bergelson, Hillel Furstenburg, Neil Hindman and Yitzhak Katznelson. (L’enseignement Mathematique, t. 35, 1989, p. 209-215)
  • Ultrafilters: Some Old and some New Results” (pdf) by W.W. Comfort. (Bulletin of the AMS, Volume 83, Number 4, July 1977)

The Battery Problem – Math for my Mom

(After writing some posts directed at other mathematicians, here is one for everybody.)

I’ve never actually done this.

I was sifting through some old issues of Crux Mathematicorum last Friday. For those of you who don’t know, this is a wonderful magazine that contains tons of math questions generally like those you would see in a math contest or olympiad, and the difficulty ranges from elementary school to undergraduate. In the September 2009 issue, I stumbled upon the following nice problem originally from the 2005 Brazilian Mathematical Olympiad. It is one of those problems that is mathematical in flavour and doesn’t need any previous math knowledge to begin thinking about the problem. For me, a nice problem is one that rewards you for thinking about it and can be attacked from many different angles.

So here’s the problem as stated:

We have four charged batteries, four uncharged batteries, and a flashlight which needs two charged batteries to work. We do not know which batteries are charged and which ones are uncharged. What is the least number of attempts that suffices to make sure the flashlight will work? (An attempt consists of putting two batteries in the flashlight and checking if the flashlight works or not.)

Continue reading The Battery Problem – Math for my Mom

A Taste of Infinite Combinatorics

When people ask me what I do I often give the ‘sexy answer’ that I study different sizes of infinity. This usually dazzles the listener and lets me talk about why I think math is beautiful as opposed to why it is useful “for getting chicks and dollar bills”.

Of course when a mathematician asks me what I do I need to give a more precise answer. (Also, I feel like, to many mathematicians, the study of cardinality seems like a parlor trick. “Been there, done that.”) So I’m going to give two (easy) facts that illustrate the types of results that go past the study of cardinality and peek into the world of infinite combinatorics.

The first observation is that people in set theory and set theoretic topology are obsessed with the real numbers (affectionately, “the reals”). Often discussions start with “This fact is true of the reals, but what about in other spaces?”. (For example, the reals have a countable dense subset – the rationals – and this is important enough that we gave it a name – separable.) Often in set theoretic topology we work under the heuristic that “everything is true in the reals”, and we look for which particular topological properties give us those facts.

So, it shouldn’t be surprising that we look for copies of the reals wherever we can.

Fact 1. There is a copy of the reals inside of the partial order (\mathcal{P}(\mathbb{N}), \subset^*)

Here A \subset^* B means A\setminus [0, n] \subset B for some n \in \mathbb{N} . This just means that A is almost contained in B . Another way to think of this partial order is that two sets are equivalent when they differ in only finitely many places. In plainspeak, besides finitely many exceptions, every element of A is also in B . (Also, \mathcal{P}(\mathbb{N}) is the family of all subsets of the natural numbers.)

proof of Fact 1. We need to construct a family of sets \{W_x : x \in \mathbb{R}\} such that when x < y we get W_x \subset^* W_y . Also, we should make sure that we didn’t construct something trivial. We should make sure that when x \neq y that W_x and W_y disagree on an infinite set.

Fix a bijection f: \mathbb{N} \rightarrow \mathbb{Q} . Let W_x := \{n \in \mathbb{N} : f(n) \leq x\} .

Sure enough, this has the above property that x < y implies W_x \subset W_y . The non triviality condition is given because whenever x < y there are infinitely many rationals between x and y . [QED]

There are other things to say about this partial order (along the lines of “It contains a copy of every countable partial order”), but I will leave those for another time.

The next thing is a standard fact that is often given as a challenge exercise for undergraduates.

Fact 2. There is a family \{W_x \subset \mathbb{N} : x \in \mathbb{R}\} such that if x \neq y then W_x \cap W_y is finite.

We will also have that each W_x is infinite. (Can you see what happens if we don’t insist on this?)

As a warm up, try finding an infinite (not necessarily uncountable) family with that property. (In this case you can do much better; you can make is so that the intersection of any two sets is empty.)

proof of Fact 2. Fix a bijection f: \mathbb{Q} \rightarrow \mathbb{N} . For each x \in \mathbb{R} , fix a sequence S_x of rationals that converges to x .

Note that if x \neq y then S_x \cap S_y is finite, because the two sequences are converging to two different reals.

So \{f[S_x] : x \in \mathbb{R} \} is the desired family. [QED]

There you go! Two facts that show how infinite combinatorics goes beyond just showing that \vert \mathbb{N} \vert < \vert \mathbb{R} \vert .