HW2

1. $\mathrm{Cars}{C}_1,C_2,\dots ,C_n$ want to park on a one-way street with ordered parking spaces $1,2,\dots ,n$. Each car $C_i,1\le i\le n$, has a preferred space $a_i$ (here $a_i\in [n]$ ). The cars follow these rules:

• (i) Each car goes to its preferred parking spaces if it is empty.
• (ii) Otherwise, it moves forward and parks in the next available space.
• (iii) If there is no space available, then the car leaves the street and fails to park.

The preference sequence $\left(a_1,a_2,\dots ,a_n\right)$ is called a parking function of length $n$ if all the cars can park. For example, $(3,2,1)$ is a parking function of length 3 , while $(3,2,2)$ is not. Prove that the number of parking functions of length $n$ is $(n+1{)}^{n-1}$.

大二做过又忘记了，但是又非常经典。考虑 $n+1$ 个环形车位，此时都能停进去。

2. Show that if $R(r-1,s)$ and $R(r,s-1)$ are both even, then $R(r,s)\le R(r-1,s)+R(r,s-1)-1$.

类似于证明

$R(s,t)⩽R(s-1,t)+R(s,t-1)$.

Link to original

构造一个 $R(r-1,s)+R(r,s-1)-1$ 个点的边界情况

3. Let $s_n$ denote the least positive integer such that in any partition of $\left\{1,2,\dots ,s_n\right\}$ into $s$ subsets, there is a subset $S$ in the partition with $x,y,z\in S$ such that $x+y=z$. In class we will prove that $s_n$ exists.

• (i) Prove that $s_1=2,s_2=5,s_3=14$.
• (ii) Show that $s_n\ge 3s_{n-1}-1$.
• (iii) Show that $s_n\ge \frac{1}{2}\left(3^n+1\right)$.

同样做过，只需要对着 $s_{n-1}$ 构造 $s_n$ 时的摆放方式

4. Use the Hales-Jewett Theorem to show that there exists an integer $N$ such that any $r$-coloring of $\{1,2,\dots ,N\}$ contains a monochromatic 3-term arithmetic progression $a,a+d,a+2d$ with $d\ne 0$. (Hint: Use an alphabet of size 3 and write each number in its base 3 representation.)

三进制把数字写成向量形式，染完色找 monochromatic combinatorial line。

5. Show that if a graph on $n$ vertices has $e$ edges, then it has at least $\frac{e}{3n}\left(4e-n^2\right)$ triangles.

类似于

• $ex(n,C_3)=[n^2/4]$

Link to original

对一条边的两点考虑它们的邻域的最小交集

6. Let $G=(V,E)$ be a graph on $n$ vertices which does not contain four vertices $v_0,v_1,v_2,v_3$ with $\left\{v_i,v_j\right\}\in E$ precisely if $i-j\equiv 1(\mathrm{mod}4)$. Show that $G$ has at most $\frac{n}{4}(1+\sqrt{4n-3})$ edges.

花里胡哨的，其实就是找 $C_4$ free. 类似于

$ex(n,\{C_3,C_4\})⩽n\sqrt{n-1}/2$.

Link to original

计算 path $(x,y,z)$ 的大小，因为 $x,z$ 确定后如果有两个 $y$ 就会得到 $C_4$.