On Gromov’s theorem on groups of polynomial growth

This article documents my presentation of Gromov’s theorem on groups of polynomial growth at the MIT combinatorics reading group. The presentation is based on Gromov’s 1981 paper, Groups of polynomial growth and expanding maps, Kleiner’s 2007 paper, A new proof of Gromov’s theorem on groups of polynomial growth, and Tao’s 2009 blog post, A finitary… Continue reading On Gromov’s theorem on groups of polynomial growth

Published
Categorized as Mathematics

On the basis exchange property

One of the students in my class, Undergraduate Seminar on Discrete Mathematics, asks if the exchange property of a matroid can be strengthened to the following, of which I was completely unaware. Strong basis exchange property. For every pair of bases and , there exists such that both and are still bases. As it turns… Continue reading On the basis exchange property

Minimal Distance to Pi

Here is a problem from Week of Code 29 hosted by Hackerrank. Problem. Given two integers and (), find and print a common fraction such that and is minimal. If there are several fractions having minimal distance to , choose the one with the smallest denominator. Note that checking all possible denominators does not work… Continue reading Minimal Distance to Pi

A Short Proof of the Nash-Williams' Partition Theorem

Notations. – the set of natural numbers; – the family of all subsets of of size ; – the family of all finite subsets of ; – the family of all infinite subsets of ; The infinite Ramsey theorem, in its simplest form, states that for every partition , there exists an infinite set such… Continue reading A Short Proof of the Nash-Williams' Partition Theorem

欺诈猜数游戏(下)

接上次的日志,先重复一下谜题: 欺诈猜数游戏在甲和乙之间进行,甲和乙都知道正整数 和 。游戏开始时,甲先选定两个整数 和 ,其中 。甲告诉乙 的值,但对 守口如瓶。乙试图通过提问来获得与 相关的信息:每次提问,乙任选一个由若干正整数组成的集合(可以重复使用之前提问中使用过的集合),问甲“是否属于?”。乙可以提任意数量的问题。每次提问之后,甲立刻回答是或否,甲可以说谎话,但在任意连续 次回答中至少有一次回答是真话。 在乙问完所有想问的问题之后,乙必须指出一个至多包含 个正整数的集合 ,若 属于 ,则乙获胜;否则甲获胜。证明:对所有充分大的整数 ,存在整数 ,使得乙无法保证获胜。 为了解决第二个问题,需要从甲的角度考虑问题,每一次回答问题后,使得乙无法缩小 范围。 为此我们考虑贪心策略:甲每次在乙提出的集合和其补集中选择元素较多的那个集合。很明显这个策略有一个弱点:如果乙每次提问都问“ 是不是 呢?”那甲如果每次只顾眼前利益,应当回答“不是。”但经过 轮之后,甲就能轻松排除 ,从而缩小 的范围。 于是甲的策略必须是一种折中的策略,既要顾及眼前的利益,又不能放弃长期的利益。我们设定 。 于是甲在觉得到底要选择乙提出的集合或是其补集前,对 到 中每个数都进行打分。甲对 的打分是 ,其中 而 满足 在最近连续 次选择的集合中都不出现。根据每个元素的打分,甲在 和 中选择会使得之后整个集合总分较低的那个集合。 为了让证明成立,设定 。下面,我们通过归纳法证明每一次所有元素的总分不超过 。根据打分规则,最开始总分是 ,命题显然那成立。假设目前的总分是 ,乙给出集合 ,如果甲选 ,则总和变为 ,如果甲选 ,则总和变为 。由于甲会选择使得总和变得更小的那个策略,于是他回答后总和至多为 。由于 ,总和小于 。命题成立! 如果 连续 次没有被甲选中,则其得分已经为… Continue reading 欺诈猜数游戏(下)

An Upper Bound on Stirling Number of the Second Kind

We shall show an upper bound on the Stirling number of the second kind, a byproduct of a homework exercise of Probabilistic Combinatorics offered by Prof. Tom Bohman. Definition. A Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of objects into non-empty subsets and… Continue reading An Upper Bound on Stirling Number of the Second Kind

A Probabilistic Proof of Isoperimetric Inequality

This note is based on Nicolas Garcia Trillos’ talk, Some Problems and Techniques in Geometric Probability, at Carnegie Mellon University on January 29, 2015. In particular, we demonstrate a probabilistic proof of the isoperimetric inequality. The proof can also be found in Integral Geometry and Geometric Probability by Luis A. Santaló. Theorem. For a convex set… Continue reading A Probabilistic Proof of Isoperimetric Inequality