Combinatorics - 0

This entry will attempt some problems from Yufei Zhao’s additive combinatorics and graph theory course (available at MIT-OCW), along with some asymptotic warmups and a geometric problem of Erdos.

Notation

Throughout, $\mathbb{N} = \{1,2,3,\dots\}$ and $[N] = \{1,\dots,N\}$. For the base case below, let $[0]$ be empty.

1 - Schur’s Theorem: Finitary and Infinitary

Schur’s theorem (infinitary): Any coloring of $\mathbb N$ with finitely many colors contains a monochromatic solution to $x+y=z$ (qualitative).

Schur’s theorem (finitary): For every $r\in\mathbb N$, there exists $N(r)\in\mathbb N$ such that when $[N(r)]$ is colored arbitrarily with $r$ colors, there exist $x,y,z\in[N(r)]$, all of the same color, such that $x+y=z$.

Let us pay attention to the subtlety here: the finitary form says that, if you pick a finite number of colors, there exists some large $N$ that only depends on the number of colors, such that any coloring of $[N]$ with these many colors contains a monochromatic $x+y=z$.

It is very clear that the finitary version implies the infinitary version. Assume the finitary version is true, and now color $\mathbb N$ arbitrarily with, say, $r$ colors. Of course the finitary version lets us find a monochromatic solution to $x+y=z$ somewhere in the inherited coloring of $[N(r)]$.

Now suppose the finitary version is false.

Suppose $r\in\mathbb N$ (and fix it). If the finitary version is false, then for each $N\in\mathbb N$, there exists a coloring $\phi_N\colon[N]\to[r]$ for which there is no monochromatic solution to $x+y=z$ in $[N]$.

Consider the sequence $S_0=\phi_1,\phi_2,\dots$. Construct a new function $\phi\colon\mathbb N\to[r]$ inductively.

We maintain the following claim:

For each $n\ge0$, there exist nested subsequences $S_0\leftarrow S_1\leftarrow\cdots\leftarrow S_n$ such that whenever $\phi_i,\phi_j\in S_t$ have $[t]$ in their domains, $\phi_i|[t]=\phi_j|[t]$. That is, $S_t$ is the subsequence of $S_{t-1}$ that stabilizes the image of $[t]$ (with $S_0$ being the original sequence).

We shall prove this by induction. The base case $n=0$ is immediate, since $[0]$ is empty.

Suppose the claim holds for some $n\ge0$. It is sufficient to show that there exists a subsequence $S_{n+1}$ of $S_n$ that stabilizes $\phi_x|[n+1]$.

Notice that there are finitely many $\phi_x\in S_n$ for which $[n+1]$ is not contained in the domain of $\phi_x$. Drop them, and obtain a subsequence $S'_n$ of $S_n$.

Now there must be some subsequence $S_{n+1}$ of $S'_n$ which stabilizes the color of $\phi_x(n+1)$. Thus, together, the colorings in $S_{n+1}$ stabilize the image of $[n+1]$, proving the claim.

We can picture the construction as the following infinite triangular table:

              1             2             3          4       ...
phi_1      phi_1(1)
phi_2      phi_2(1)      phi_2(2)
phi_3      phi_3(1)      phi_3(2)      phi_3(3)
phi_4      phi_4(1)      phi_4(2)      phi_4(3)   phi_4(4)
  .            .             .             .          .
  .            .             .             .          .

Passing to $S_n$ stabilizes the first $n$ columns. This is the diagonalization: at the $n$-th step we settle the $n$-th coordinate while preserving all the coordinates settled earlier.

Now notice that whenever $\phi_x\in S_n$, $\phi_x\in S_0$ and $[n]$ is a subset of $\phi_x$‘s domain.

Of course, $\phi_x$ being in $S_0$ implies that there is no monochromatic solution to $x+y=z$ in its domain, and thus $\phi_x|[n]$ has no monochromatic solution to $x+y=z$ in $[n]$.

Now thus, we construct $\phi\colon\mathbb N\to[r]$ by having $\phi(n)=\phi_x(n)$ for any $\phi_x\in S_n$. It is clear that $\phi$ is a well-defined coloring and has no monochromatic solutions to $x+y=z$.

Thus, it cannot be the case that the infinitary version is true while the finitary version is false.

Therefore, the two statements are equivalent to each other.

We have dealt with the proof of Schur’s theorem before, so we can chill.

2 - The Erdos Problem

Definition 0. We say a point $x\in(\mathbb R^2)^n\cong\mathbb R^{2n}$ is unital if, for any distinct $i,j\in[n]$, $\lVert x_i-x_j\rVert_{\mathbb R^2}\ge1$.

Definition 1. We say two unital points $x,y$ are equivalent if the sets of $n$ points they describe in $\mathbb R^2$ have the same diameter.

We will massage the problem down into something simpler, but first we have to show that the set of unital points has some element with lowest $\mathbb R^2$ diameter. The issue here is, of course, that the set of unital points may only get arbitrarily close to having the lowest diameter.

It is quite obvious that whatever point that is, it can be translated, and its $\mathbb R^2$ diameter is at most $n-1$: consider $x=((0,0),(0,1),\dots,(0,n-1))$.

Any configuration with diameter greater than $n-1$ is irrelevant to the minimum. If a configuration has diameter at most $n-1$, choose its first point and translate it to the origin. Every other point then lies in $[-n,n]^2$.

Thus it is enough to look inside the compact box $M=\{(0,0)\}\times([-n,n]^2)^{n-1}$.

We claim that the function $f_{ij}\colon M\to\mathbb R$ given by $x\mapsto\lVert x^i-x^j\rVert_{\mathbb R^2}$ is continuous.

Just for this proof, it will be easier to have the following notation: $p\in M$ is written as $(p_x^1,p_y^1,p_x^2,p_y^2,\dots,p_x^n,p_y^n)$.

We will make use of the following lemma. Let $|b_x-a_x|,|b_y-a_y|<\delta$, and let $a=(a_x,a_y)$ and $b=(b_x,b_y)$. Then $\lVert b-a\rVert<\sqrt2\,\delta$.

And another lemma: $\big|\lVert u\rVert-\lVert v\rVert\big|\le\lVert u-v\rVert$.

Notice $u=(u-v)+v$, so applying the triangle inequality gives $\lVert u\rVert-\lVert v\rVert\le\lVert u-v\rVert$. Similarly, $v=(v-u)+u$, and together we get the desired result.

Now take a $\delta$ open box around $p$, and some $q$ in it. For each $k$, we have $|q_x^k-p_x^k|,|q_y^k-p_y^k|<\delta$, and thus $\lVert q^k-p^k\rVert<\sqrt2\,\delta$.

Now,

$$\begin{aligned} |f_{ij}(q)-f_{ij}(p)| &=\big|\lVert q^j-q^i\rVert-\lVert p^j-p^i\rVert\big|\\ &\le\lVert(q^j-p^j)-(q^i-p^i)\rVert\\ &\le\lVert q^j-p^j\rVert+\lVert q^i-p^i\rVert\\ &<2\sqrt2\,\delta. \end{aligned}$$

That is, for any $\epsilon>0$, it suffices to have $\delta<\epsilon/(2\sqrt2)$.

Since each $f_{ij}\colon M\to\mathbb R$ is continuous, preimages of closed sets are closed. Let $M_{ij}=f_{ij}^{-1}([1,\infty))$. Then $M_{ij}$ is the closed subset of $M$ for which the points $x^i,x^j\in\mathbb R^2$ satisfy $\lVert x^j-x^i\rVert\ge1$.

Now notice $U^*=\bigcap_{i<j}M_{ij}$ is the closed subset of $M$ where each point is unital. Thus the unital points in $M$ form a compact set.

Now let $X$ be a compact set, and let $f_i\colon X\to\mathbb R$ be a finite collection of continuous maps. We claim that $f^*$, given by $x\mapsto\max_i f_i(x)$, is continuous.

First, another sweet little lemma. We claim that $\max(|b-a|,|d-c|)\ge|\max(d,b)-\max(c,a)|$.

Let $L=\max(|b-a|,|d-c|)$. Then

$$a-L\le b\le a+L, \qquad c-L\le d\le c+L.$$

The max function has chill properties. An obvious one is that $p\le q$ and $m\le n$ imply $\max(p,m)\le\max(q,n)$. Another chill property is $\max(x+r,y+r)=\max(x,y)+r$.

Using these two properties on the inequalities above, we get $\max(a,c)\le\max(b,d)+L$ and $\max(b,d)\le\max(a,c)+L$. Combining both gives the desired result.

Now, for any $\epsilon>0$, there exists a common $\delta>0$ such that for each $i$, $|f_i(x)-f_i(x_0)|<\epsilon$ whenever $d(x,x_0)<\delta$. This common $\delta$ exists because there are only finitely many functions. Therefore, $\max_i|f_i(x)-f_i(x_0)|<\epsilon$, and indeed, using induction on the previous lemma, we get $|f^*(x)-f^*(x_0)|<\epsilon$.

But now notice that the $\mathbb R^2$ diameter function from $M$ to $\mathbb R$ is the pointwise maximum of the $f_{ij}$, so it is continuous. Thus the restricted diameter function $\operatorname{diam}\colon U^*\to\mathbb R$ is continuous.

Of course, the image $\operatorname{diam}(U^*)$ is a compact subset of $\mathbb R$, i.e. it is both closed and bounded. That is to say, $\alpha=\inf(\operatorname{diam}(U^*))$ exists and is in $\operatorname{diam}(U^*)$. Hence there exists some unital point $u$ for which $\operatorname{diam}(u)=\alpha$.

Now we can discard all this machinery and state the problem without worry in its simplest form.

Consider the collection

$$\mathbf A(n)=\left\{A\subset\mathbb R^2:|A|=n,\ \lVert x-y\rVert\ge1\text{ for all distinct }x,y\in A\right\}.$$

That is, $\mathbf A(n)$ is the collection of unital subsets of cardinality $n$.

Let $\mathbf A^*(n)$ be the subset of $\mathbf A(n)$ where each set has the least diameter. The previous machinery shows that $\mathbf A^*(n)$ is nonempty.

Does there exist some $N\in\mathbb N$ for which, whenever $n>N$, every set in $\mathbf A^*(n)$ contains a unit equilateral triangle?

This is the question as stated by Erdos. It is open, and some believe it is false.

There is a decent reframing of the problem.

Let $\{x_1,x_2,\dots,x_n\}\in\mathbf A^*(n)$. We claim there exist $i,j$ for which $\lVert x_i-x_j\rVert=1$.

Otherwise every pair is more than $1$ away from each other. Thus we can shrink the configuration. Formally, suppose toward contradiction that for each $i\ne j$, $\lVert x_i-x_j\rVert>1$. Let $r^*=\min_{i<j}\lVert x_i-x_j\rVert>1$.

Set $y_i=x_i/r^*$. Then $\lVert y_i-y_j\rVert=\lVert x_i-x_j\rVert/r^*\ge1$, but the diameter of this new set is strictly smaller, a contradiction.

Thus we can take any unital set $X$ and assign to it its contact graph:

$$V(G_X)=X, \qquad E(G_X)=\big\{\{x_i,x_j\}:\lVert x_i-x_j\rVert=1\big\}.$$

Thus the question becomes: is there a sufficiently large $N$ such that, for every $n>N$, the contact graph of every minimizer in $\mathbf A^*(n)$ contains a $K_3$?

This is Erdos Problem 99.

3 - Asymptotic Notation

In the analysis of algorithms, we are mostly concerned with functions of the type $f\colon \mathbb N \to \mathbb R^+$, where $f(n)$ depicts the count of basic operations in the Word-RAM model for an input size of $n$. $f(n)$ is allowed to be real, just for relaxation.

Often $f$ is treated as increasing in $n$; it would be kind of weird if a larger input required less computation in our model. This does not have to be literally true for every operation count, which is one reason that the eventual definition below is convenient.

Definition (Asymptotic Notation): Let $f,g\colon\mathbb N\to\mathbb R^+$. We say $f=O(g)$ if there exist $C>0$ and $N_0\in\mathbb N$ such that $f(n)\le Cg(n)$ whenever $n\ge N_0$.

We say $f=\Omega(g)$ if $g=O(f)$, and $f=\Theta(g)$ if both $f=O(g)$ and $g=O(f)$. Moreover, the family of functions $\{f:f=O(g)\}$ is the class $O(g)$. In such cases, we also write $f\in O(g)$.

Big-$O$ is quite loose: it only says that one function is eventually bounded by a constant multiple of another. Sometimes we want to say that one function becomes completely negligible next to another. We write $f=o(g)$ if $f(n)/g(n)\to0$ as $n\to\infty$.

Going the other way, we write $f=\omega(g)$ if $g=o(f)$, or equivalently if $f(n)/g(n)\to\infty$.

Finally, we write $f\sim g$ if $f(n)/g(n)\to1$. That is, the two functions not only have the same rough growth, but their ratio itself settles at $1$. We will also write $f=(1+o(1))g$ for the same thing.

Theorem (Any polynomial power beats any logarithmic power): For any $a,b\in\mathbb R^+$, $\log(n)^a=O(n^b)$. But $n^b\ne O(\log(n)^a)$.

Proof: First, we will show that there is an absolute constant $C>0$ such that $\log(n)^a\le Cn^b$. For $n\ge2$, notice $a\log(\log n)\le\log C+b\log n$, or equivalently $\log C\ge a\log(\log n)-b\log n$ (exploiting the fact that $\log$ is increasing).

Now set $g(x)=a\log(\log x)-b\log x$ for $x>1$. We claim that $g(x)$ has an absolute maximum. Indeed, $g'(x)=\frac1x\left(\frac{a}{\log x}-b\right)$.

Notice that $g'(x)=0$ at $x=e^{a/b}$, and for $x<e^{a/b}$, $g'(x)>0$, while for $x>e^{a/b}$, $g'(x)<0$. Hence $g(e^{a/b})$ is the absolute maximum of $g$. It is sufficient to set $\log C\ge g(e^{a/b})$ (and enlarge $C$ if we want to include the finitely many small values of $n$).

Now, we will show that there is no absolute constant $D>0$ such that $n^b\le D(\log n)^a$ eventually. Again, $b\log n\le\log D+a\log(\log n)$ would imply $\log D\ge b\log n-a\log(\log n)=-g(n)$.

Notice that $-g(x)$ is unbounded as $x\to\infty$, so no such $D$ exists. $\square$

Asymptotics Exercises

2. Find a simple, tight asymptotic bound for $\binom{n}{6006}$.

Solution: Definition yields $n(n-1)\cdots(n-6005)$ in the numerator (a degree $6006$ polynomial) and $6006!$ in the denominator (constant with respect to $n$). So $\binom{n}{6006}=\Theta(n^{6006})$.

---

3. Find a simple, tight asymptotic bound for $\log_{6006}\left(\left(\log\left(n^{\sqrt n}\right)\right)^2\right)$.

Solution: Recall exponent and logarithm rules: $\log(ab)=\log a+\log b$, $\log(a^b)=b\log a$, and $\log_a b=\log b/\log a$.

$$\begin{aligned} \log_{6006}\left(\left(\log\left(n^{\sqrt n}\right)\right)^2\right) &=\frac{2}{\log6006}\log(\sqrt n\log n)\\ &=\Theta(\log n^{1/2}+\log\log n)\\ &=\Theta(\log n). \end{aligned}$$

---

4. Show that $2^{n+1}\in\Theta(2^n)$, but that $2^{2^{n+1}}\notin O(2^{2^n})$.

Solution: In the first case, $2^{n+1}=2\cdot2^n$, which is a constant factor larger than $2^n$. In the second case, $2^{2^{n+1}}=\left(2^{2^n}\right)^2$, which is definitely more than a constant factor larger than $2^{2^n}$.

---

5. Show that $(\log n)^a=O(n^b)$ for all positive constants $a$ and $b$.

Solution: It is enough to show that $n^b/(\log n)^a$ limits to $\infty$, and this is equivalent to arguing that the log of this expression approaches $\infty$:

$$\begin{aligned} \lim_{n\to\infty}\log\left(\frac{n^b}{(\log n)^a}\right) &=\lim_{n\to\infty}(b\log n-a\log\log n)\\ &=\lim_{x\to\infty}(bx-a\log x)\\ &=\infty, \end{aligned}$$

as desired.

Note: for the same reasons, $n^a=O(c^n)$ for any $c>1$.

---

6. Show that $(\log n)^{\log n}=\Omega(n)$.

Solution: Note that $m^m=\Omega(2^m)$, so setting $n=2^m$ completes the proof.

---

7. Show that $(6n)!\notin\Theta(n!)$, but that $\log((6n)!)\in\Theta(\log(n!))$.

Solution: We invoke Stirling’s approximation,

$$n!=\sqrt{2\pi n}\left(\frac ne\right)^n\left(1+\Theta\left(\frac1n\right)\right).$$

Substituting in $6n$ gives an expression whose ratio to $n!$ grows without bound. But taking the logarithm of Stirling’s approximation gives $\log(n!)=\Theta(n\log n)$, and substituting in $6n$ yields only constant additional factors.

Asymptotic Analysis Using Limits

Using the eventual definition of big-$O$ notation, we have the following proposition.

Proposition (Finite limiting ratio and asymptotics): Let $f,g\colon\mathbb N\to\mathbb R^+$. If $\lim_{n\to\infty}f(n)/g(n)=C>0$, then $f=\Theta(g)$, and in particular $f=O(g)$.

Proof: Notice that for each $\epsilon>0$ there exists $N(\epsilon)$ such that, when $n>N(\epsilon)$, $\left|f(n)/g(n)-C\right|<\epsilon$.

Rearranging, and choosing any small epsilon that we like :), we have $(C-\epsilon)g(n)<f(n)<(C+\epsilon)g(n)$ eventually. Choosing $0<\epsilon<C$ gives both comparisons, and hence $f=\Theta(g)$. $\square$

Notice that $f=O(g)$ does not say too much about limits, and is well defined when neither $f$ nor $g$ converges. It only says that $f/g$ is eventually bounded above. In particular, its limit superior is finite, though the ratio itself need not have a limit.