\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphicx}
\providecommand{\abs}[1]{\lvert#1\rvert}
\providecommand{\norm}[1]{\lVert#1\rVert}

\newtheorem{thm}{Theorem}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{fact}[thm]{Fact}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{eg}{Example}
\newtheorem{ex}{Exercise}
\newtheorem{defi}{Definition}
\newtheorem{hw}{Problem}
\newenvironment{sol}
  {\par\vspace{3mm}\noindent{\it Solution}.}
  {\qed}

\newcommand{\ov}{\overline}
\newcommand{\cb}{{\cal B}}
\newcommand{\cc}{{\cal C}}
\newcommand{\cd}{{\cal D}}
\newcommand{\ce}{{\cal E}}
\newcommand{\cf}{{\cal F}}
\newcommand{\ch}{{\cal H}}
\newcommand{\cl}{{\cal L}}
\newcommand{\cm}{{\cal M}}
\newcommand{\cp}{{\cal P}}
\newcommand{\cz}{{\cal Z}}
\newcommand{\eps}{\varepsilon}
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\dist}{\mbox{\rm dist}}
\newcommand{\bn}{{\mathbf N}}
\newcommand{\br}{{\mathbf R}}
\newcommand{\bz}{{\mathbf Z}}
\newcommand{\expe}{{\mathsf E}}
\newcommand{\prob}{{\mathsf{Pr}}}

\setlength{\parindent}{0pt}
%\setlength{\parskip}{2ex}
\newenvironment{proofof}[1]{\bigskip\noindent{\itshape #1. }}{\hfill$\Box$\medskip}

\begin{document}

$\;$\hfill Do not need to hand in

\begin{center}
{\LARGE\bf Homework 13}
\end{center}

\begin{hw} Let $f : \br^2 \rightarrow [3]$ be a 3-colouring of the plane. Prove that
there will be two points $a$ and $b$, such that $|ab| = 1$, and $f(a) = f(b)$.
\end{hw}

\begin{sol}
First consider any equilateral triangle $abc$, if two of the three vertices are coloured the
same, then we are done.

Otherwise, consider any pair of points $c$ and $c'$ with $|cc'| = \sqrt{3}$. There are points
$a$ and $b$ such that both $abc$ and $abc'$ are equilateral triangles. So we are done, or any
such $c$ and $c'$ has the same colour. Which implies that, centered at any point $c$, all points on the circle with radius $\sqrt{3}$ has the same color. There are certainly infinitely many pairs with distance $1$ on the circle.
\end{sol}

\begin{hw}
Let $2 \leq k \leq \sqrt{n}$. Consider a set $S$ of $n$ points in the plane. A line is called
{\em good} if it contains at least $k$ points from $S$. Prove that there are
at most $c n^2 / k^3$ good lines, where $c$ is a constant independent of $n$ and $k$.
\end{hw}

\begin{sol}
For any good line with points appear on it as $v_1$, $v_2$, ..., $v_s$ in that order,
where $s \geq k$. We draw $s-1$ straight edges $v_i v_{i+1}$ ($1 \leq i < t$). This, together
with $S$ as the set of vertices, form a particular drawing of a graph $G$ on
$n$ vertices and $m \geq t(k-1)$ edges, where $t$ is the number of good lines.

Since the drawings of the edges lie on $t$ straight lines, so there are at most $\binom{t}{2}$
intersections of the lines. So
\[ cr(G) \leq \binom{t}{2} \;\;(*) \]
On the other hand, by the crossing lemma, either $m < 4n$, which implies
\[ t(k-1) < 4n  \;\; \Rightarrow \;\; t < \frac{4n}{k-1}, \]
or the crossing number is at least $\frac{m^3}{64n^2}$, which implies
\[ cr(G) \geq \frac{t^3(k-1)^3}{64n^2} \]
and by (*),
\[ t \leq \frac{32n^2}{(k-1)^3}.\]
In any case,
\[ t \leq \min(\frac{4n}{k-1},  \frac{32n^2}{(k-1)^3}).\]
It is an easy exercise to find a constant $c$ such that $t \leq c n^2 / k^3$.
\end{sol}

\begin{hw} The $L_1$ distance for two points in the plane is
\[ d((x, y), (x', y')) = |x - x'| + |y - y'|. \]
Let $n \geq 2$ and $V$ be the set of points in the plane
\[ V = \{ (1, 3), (2, 4), (3, 1), (4, 2) \} \cup \{ (n+i, 2n-i) : i = 0, 1, 2, ..., n\}.\]
And let the hypergraph $\cf$ be the one with the edges
\[
\{ \{a, b, c\} \subseteq V : |\{a, b, c\}| = 3, d(a, b) + d(b, c) = d(a, c) \}.
\]
How many different lines are there in this system?
\end{hw}

\begin{sol} Let $a = (1,3)$, $b = (2, 4)$, $c=(3,1)$, $d=(4,2)$, and $e_i = (n+i, 2n-i)$,
and $W = \{e_i | 0 \leq i \leq n\}$.

When $n = 2$, $b = e_0$ and $d = e_2$. The lines are $\overline{ab}=\{a, b\}$, $\overline{cd}=\{c, d\}$. All of $\overline{ac}$, $\overline{bd}$, $\overline{ad}$, $\overline{bc}$ contains the two generating points and $e_1$. $\overline{ae_1} = V - b$, $\overline{be_1} = V - a$, $\overline{ce_1} = V - d$, and $\overline{de_1} = V - c$. All the $10$ lines are different.

When $n = 3$,
\[|\overline{ac}|=|\overline{bd}|=|\overline{ad}|=|\overline{bc}|=2;\]
\[\overline{ab} = \{a, b\} \cup W - \{e_3\};\]
\[\overline{cd} = \{c, d\} \cup W - \{e_0\};\]
\[\overline{e_ie_j} = W;\]
\[\overline{ae_0} = \overline{be_0} = \{a, b, e_0\};\]
\[\overline{ae_1} = \overline{be_1} = \{a, b, e_1\};\]
\[\overline{ae_2} = \{a, b, e_2\};\]
\[\overline{be_2} = \{a, b, e_2, e_3\};\]
\[\overline{ae_3} = \{a, e_3\};\]
\[\overline{be_3} = \{b, e_2, e_3\};\]
Similarly, there are 6 lines generated by one of $\{c, d\}$ and one of the $e_i$'s. There are
$19$ different lines.

For $n \geq 4$, we have
\[ \overline{ab} = \{a, b\} \cup W;\]
\[ \overline{cd} = \{c, d\} \cup W;\]
\[ \overline{ac} = \{a, c\};\]
\[ \overline{bd} = \{b, d\};\]
\[ \overline{ad} = \{a, d\};\]
\[ \overline{bc} = \{b, c\};\]
\[ \overline{ae_i} = \overline{be_i} = \{a, b, e_i\}, 0 \leq i \leq n;\]
\[ \overline{ce_i} = \overline{de_i} = \{c, d, e_i\}, 0 \leq i \leq n;\]
\[ \overline{e_ie_j} = W \]
There are $2n+9$ different lines.
\end{sol}

\begin{hw} Let $\cf$ be a 3-uniform hypergraph on $[n]$ where among any four points there
are less than $4$ hyperedges. Prove that in this system there is a line equal to $[n]$,
or there are at least $n$ different lines.
\end{hw}

{\em Remark.} Any pair of points generate a line, some of the lines are the same (considered as sets of points). If $a$, $b$, $c$, $d$ are four distinct points and $\overline{ab}=\overline{cd}$, then there are 4 hyperedges among those 4 points. Therefore, any line is repeated at most $n-1$ times. This already proves that the number of lines is at least $n / 2$.

We note the reasoning above as

\begin{lemma} If, in $\cf$, $\overline{ab} = \overline{cd}$, then $\{a, b\} \cap \{c, d\} \neq \emptyset$.
\end{lemma}

The statement clearly holds when $n = 3$.
Now we use induction to prove that, when $n \geq 4$, there are always $n$ lines, {\em no matter} there is a line
equals $[n]$ or not. The basis, when $n = 4$, are still easy and we omit the details.

We call the unordered pair $\{a, b\}$ the {\em generator} of $\overline{ab}$. By the lemma, any two generators share a point. Assume there are two generators $\{p, x\}$ and $\{p, y\}$ generate the same line $L$. Let $W = V - \{p\}$. By induction, there are at least $n-1$ lines
\[L_i' = \overline{a_ib_i}', i = 1, ..., n-1\]
in $\cf - \{p\}$. (We use ' to indicate the lines are in the system of $\cf - \{p\}$.)

Let $L_i = \overline{a_ib_i}$ be the line in the system of $\cf$. $L_i = L_i'$ or $L_i' \cup \{p\}$. The $L_i$'s intersect $W$ with different sets, so they are $n-1$ different lines.
If $\overline{px} \neq L_i$ for all $i$, then we are done by induction. If $\overline{px} = \overline{py} = \overline{a_ib_i}$ but $\{a_i, b_i\} \neq \{x, y\}$, then we have a contradiction against the lemma.

Now, suppose there are $t$ different lines. We colour $K_n$ with $t$ colours, mark $ab$ with colour $i$ if $\overline{ab}$ is the $i$-th line. By the discussion above, $K_n$ is partitioned into $t$ triangles and edges (*). It is easy to see that, when $n > 6$, $t \geq \binom{n}{2} / 3 \geq n$. It is also easy to see (exercise again) when $n = 5, 6$, we need at least $n$ colours in order to do (*). \qed

\end{document}

