Proof of Erdős-Stone Theorem Part II

The following result finishes the guided proof of Erdős-Stone Theorem that started here.

Lemma

Fix $r\in\mathbb{N}$ and $\epsilon>0$. For sufficiently large $n$, starting with any $n$-vertex graph $G$ with at least $(1-1/r+\epsilon)\frac{n^2}{2}$ edges we can keep removing vertex one by one with degree less than $(1-1/r+\epsilon/2)|V(G)|$. When we get stuck, the final graph has $\Theta(n)$ vertices.

Proof

Let $\alpha=1-1/r$. Suppose when we get stuck there are $x$ vertices left. The number of removed edges is less than $(n+(n-1)+\ldots+(x+1))(\alpha+\epsilon/2)$, or $(\alpha+\epsilon/2)\frac{(n+x+1)(n-x)}{2}$. There are at most $\binom{x}{2}$ edges remaining. Hence we have inequality $(\alpha+\epsilon/2)\frac{(n+x+1)(n-x)}{2}+\binom{x}{2}\geq \frac{n^2}{2}(\alpha+\epsilon)$. Thus $\frac{\epsilon}{2}n^2-(\alpha+\epsilon/2)n\leq(1-\alpha-\epsilon/2)x^2$.

$\diamond$

Proof of Erdős-Stone Theorem Part I

Erdős-Stone Theorem (1946): Fix $s,r\in\mathbb{N}$ and $c>0$. If $n$ is sufficiently large, then every $n$-vertex graph with $t_r(n)+cn^2$ edges contains $K_{r+1}[s]$.

A fundamental theorem in extremal graph theory. Note that $t_r(n)=(1-1/r)\frac{n^2}{2}-O(n)$, so it could also be replaced with $(1-1/r)\frac{n^2}{2}$.

The proof here follows the hints from Lovász L., Combinatorial problems and and exercises, 2nd ed. (North-Holland, 1993).

In this part, we show a weaker result.

Lemma

Fix $s,r\in\mathbb{N}$ and $\epsilon>0$. For sufficiently large $n$, every $n$-vertex graph with minimum degree at least $(1-1/r+\epsilon)n$ contains $K_{r+1}[s]$.

Proof

By induction on $r$. For $r=1$, every vertex has degree at least $\epsilon n$. There are $\binom{n}{s}$ $s$-sets in $V(G)$, and each vertex is fully connected to as least $\binom{\epsilon n}{s}$ $s$-sets. So for the lemma to hold when $r=1$, it suffices to show that $n\binom{\epsilon n}{s}/\binom{n}{s}\geq s$, which is simple.

In the induction step, let $t=\lceil\frac{s}{\epsilon}\rceil\geq s$. Suppose there exist $r$ disjoint $t$-sets $A_1,A_2,\ldots,A_r$ such that vertices from different $t$-sets are adjacent. Let $U=V(G)-\cup_{i=1}^rA_i$. We want to show that in $U$ there are sufficiently many vertices that are adjacent to at least $(r-1)t+s$ vertices in $V(G)-U$. Each of these vertices in $U$ must be fully connected to an $s$-set in each $A_i$, and the combinations of $r$ $s$-sets is $\binom{t}{s}^r$, which is finite.

Between $U$ and $V(G)-U$ there are at least $rt((1-\frac{1}{r}+\epsilon)n-(rt-1))$ edges, so on average each vertex in $U$ is adjacent to $\frac{rt((1-\frac{1}{r}+\epsilon)n-(rt-1))}{n-rt}$ vertices in $V(G)-U$. That expression, for sufficiently large $n$, is indeed at least $(r-1)t+s$. Hence there are at least $\frac{|U|}{1+t-s}=\frac{n-rt}{1+t-s}=\Theta(n)$ vertices in $U$ adjacent to at east $(r-1)t+s$ vertices in $V(G)-U$.

$\diamond$

IMO 2022 Problem 6

Let $n$ be a positive integer. A Nordic square is an $n \times n$ board containing all the integers from $1$ to $n^2$ so that each cell contains exactly one number. Two different cells are considered adjacent if they share a common side. Every cell that is adjacent only to cells containing larger numbers is called a valley. An uphill path is a sequence of one or more cells such that:

(i) the first cell in the sequence is a valley,

(ii) each subsequent cell in the sequence is adjacent to the previous cell, and

(iii) the numbers written in the cells in the sequence are in increasing order.

Find, as a function of $n$, the smallest possible total number of uphill paths in a Nordic square.

Author: Nikola Petrović

==============================

Solution:

The total number of uphill sequences can be counted in another way as downhill sequences: starting from each cell, keep going down to a lower neighbor until reaching a valley. Let $a_i$ be the number of downhill sequences starting from cell of height $i$. We can count the sequences of a Nordic board as we build it in the following way. 

Starting from an empty Nordic board, pick a cell to have height $1$ and write down $a_1$, then pick another to have height $2$ and write down $a_2$, and so on until the Nordic board is completed. The rule for $a_i$ is: sum up all existing $a_j$s adjacent to the cell of height $i$, or if all neighbors are empty then $a_i=1$ (meaning that the cell is a valley). What is the minimum of $S=a_1+a_2+\ldots+a_{n^2}$?

There are $2n(n-1)$ pairs of unordered adjacent cells, each contributing at least $1$ to $S$. Moreover as we write down $a_1=1$, it doesn't have contribution from any pair of unordered adjacent cells. Thus $S\geq 2n(n-1)+1$. What is the condition for equality? There are two sub-conditions:

(i) Except for $a_1$, all $a_i$s that are equal to $1$ are adjacent to exactly one other $1$ when written down.

(ii) All $a_i$s larger than $1$ are adjacent to only $1$s and no empty cells or $a_j$s larger than $1$ when written down.

This translates to the following operation. Starting from an empty $n\times n$ board, mark some of its cells one by one such that all marked cells (except for the first one) are adjacent to exactly one marked cell when marked, and when done there are no adjacent unmarked cells. If this is possible, then the minimum is $2n(n-1)+1$. Below we prove that it's always possible.

Proof:

We will mark the cells row by row. We begin with the first row, where all are marked and only the leftmost and rightmost can be skipped. In the second row we mark every other cell. Below are possible outcomes of the first two rows where $1$ denotes marked cell and $0$ is unmarked.

$\begin{array} {ccccc} 0&1&1&1&1 \\ 1&1&0&1&0\\ \end{array}$

Starting from the third row, we proceed from one end where the previous row has $0$ to the other end in the only possible way. In the example below we only show the previous and current rows, and the current row is marked in red.

$\begin{array} {cccccccccccc} 0&1&1&0&1&0&1&1&1&0&1&1 \\ \color{red}{1}&\color{red}1&\color{red}0&\color{red}1&\color{red}1&\color{red}1&\color{red}0&\color{red}1&\color{red}0&\color{red}1&\color{red}1&\color{red}0\\ \end{array}$

If the previous row has $1$ at both ends, then proceed from either end to the other in one of two possible ways, for example:

$\begin{array} {cccccccccccc} 1&1&1&0&1&0&1&1&1&1&1&1 \\ \color{red}0&\color{red}1&\color{red}0&\color{red}1&\color{red}1&\color{red}1&\color{red}0&\color{red}1&\color{red}0&\color{red}1&\color{red}0&\color{red}1\\ \end{array}$

or

$\begin{array} {cccccccccccc} 1&1&1&0&1&0&1&1&1&1&1&1 \\ \color{red}1&\color{red}0&\color{red}1&\color{red}1&\color{red}0&\color{red}1&\color{red}1&\color{red}0&\color{red}1&\color{red}0&\color{red}1&\color{red}0\\ \end{array}$

The only time things may go wrong is when both ends of the previous row is $0$, for example the operation could not succeed in this example.

$\begin{array}{cccc}0&1&1&0\\ \color{red}1&\color{red}?&\color{red}?&\color{red}1\\ \end{array}$

However, this can be avoided. We can have $1$ at both ends of the second row and then proceed. At every new row, if the previous row has $1$ at exactly one end, then the other end of the current row will be $1$. If the previous row has $1$ at both ends, then at least one of the two possible ways of marking the current row avoids $0$ at both ends. By induction, no row would have $0$ at both ends.

$\diamond$

Number of chains

This is from paper Nonlinearity of Davenport-Schinzel Sequences and of a Generalized Path Compression Scheme by Hart and Sharir, section 4.1.

A sequence of integers $U=(u_1,u_2,\ldots)$ does not contain  (not necessarily contiguous) subsequence $xyxyx$ where $x\neq y$. $u_j\in\{1,2,\ldots,n\}$ for each $j$. Moreover, for $k=1,2,\ldots,n-1$, the first appearance of $k$ precedes that of $k+1$. Finally, no two consecutive integers are identical.

Define a chain as a maximal decreasing contiguous subsequence of $U$.

Lemma. $U$ has at most $2n$ chains.

===================================

Proof:

We will modify $U$ which may or may not reduce its chains. Let $a<b<c<\ldots$ be integers in $\{1,2,\ldots,n\}$, which may not be consecutive.

Observation 1. $U$ does not have consecutive subsequences $cba$ and $bac$.

Proof: If it has $cba$, remove $b$. If it has $bac$, remove $a$. $\square$

Let $I=(i_1,i_2,\ldots)\subset U$ be the maximal leading subsequence of $U$ where $i_j=j$ for each $i_j\in I$.

Observation 2. $I$ does not end with $c$ followed by $ab$.

Proof: If it does, $U$ has $abcab$ and no more $a$ thereafter. We can then remove $a$'s, reduce $n$ by $1$, and reduce the number of chains by $2$. $\square$

Observation 3. $I$ does not end with $b$ followed by $ab$.

Proof: If it does, $U$ has $abab$ and no more $a$ thereafter. We can remove $a$'s and the second $b$, reduce $n$ by $1$, and reduce the number of chains by $2$. $\square$

Eventually, we arrive at $U$ with $I=(1,2,3,\ldots,n)$ followed by one or no integer. It has $n\leq 2n$ chains.

$\square$

Digits in $2^n$

This problem was heard from here. Let $a_n$ be the number of odd digits in the base-$10$ expansion of $2^n$. Prove that

$$
\sum_{n=1}^{\infty}\frac{a_n}{2^n}=\frac{1}{9}.
$$

What a amazing property!

=====================

Proof:

Write $2^n$ in decimal digits $\ldots d_{n,1}d_{n,0}$. Observe that $d_{i,j}$ is odd if and only if $5\leq d_{i-1,j-1}\leq 9$, which happens if and only if $d_{i-2,j-1}d_{i-2,j-2}\in \{[25,49], [75,99]\}$, which....and so on. So

Claim 1

$d_{n,i}$ is odd if and only if $10^{-i}\in\cup_{k=1}^{2^n}[k2^{-n}-2^{-n-1},k2^{-n})$.

Immediately we have

Claim 2

$d_{n,i}$ is odd if and only if the $n$-th digit after decimal point in $10^{-i}$'s binary representation is $1$.

Now we have everything. The sum $\sum_{n=1}^{\infty}\frac{a_n}{2^n}$ is nothing but $\sum_{i=1}^{\infty}10^{-i}$, which is $\frac{1}{9}$.

Q.E.D.

Pick the bigger real

Source

I write down two distinct reals secretly and call them $x$ and $y$. You can pick one of them to observe its value. Then, you will need to decide whether $x$ or $y$ is larger. Your strategy should produce the right answer with probability more than $\frac{1}{2}$ for any $(x,y)$.

At one point I thought it's impossible, but then...

====================

Solution:

First, select $x$ or $y$ with equal probabilities. Say the observed value is $z$. Then with probability $f(z)$ claim that it's the larger one. Obviously the only requirement for $f$ is to be strictly monotonic, which can be achieved easily. For example, let $f(z)=\frac{e^z}{1+e^z}$.

Alternative solution:

From source: draw a random real $w$ from a fixed distribution where each open interval has non-zero support. Compare $w$ with $z$ and claim $z$ is the larger if and only if $z>w$. Clearly, if $w$ is between $x$ and $y$ then the answer will be correct. Otherwise the probability of being right is $\frac{1}{2}$, therefore the overall chance is more than $\frac{1}{2}$.