Fujimura.tex: Difference between revisions
No edit summary |
No edit summary |
||
Line 22: | Line 22: | ||
For any equilateral triangle $(a+r,b,c)$,$(a,b+r,c)$ and $(a,b,c+r)$, the value $y+2z$ forms an arithmetic progression of length 3. A Behrend set is a finite set of integers with no arithmetic progression of length 3 (see {\tt http://arxiv.org/PS\_cache/arxiv/pdf/0811/0811.3057v2.pdf}). By looking at those triples $(a,b,c)$ with $a+2b$ inside a Behrend set, one can obtain the lower bound of $\overline{c}^\mu_n \geq n^2 exp(-O(\sqrt{\log n}))$. | For any equilateral triangle $(a+r,b,c)$,$(a,b+r,c)$ and $(a,b,c+r)$, the value $y+2z$ forms an arithmetic progression of length 3. A Behrend set is a finite set of integers with no arithmetic progression of length 3 (see {\tt http://arxiv.org/PS\_cache/arxiv/pdf/0811/0811.3057v2.pdf}). By looking at those triples $(a,b,c)$ with $a+2b$ inside a Behrend set, one can obtain the lower bound of $\overline{c}^\mu_n \geq n^2 exp(-O(\sqrt{\log n}))$. | ||
It can be shown by a 'corners theorem' of Ajtai and Szemeredi that $\overline{c}^\mu_n = o(n^2)$ as $n \rightarrow \infty$. | It can be shown by a 'corners theorem' of Ajtai and Szemeredi \cite{ajtai} that $\overline{c}^\mu_n = o(n^2)$ as $n \rightarrow \infty$. | ||
An explicit lower bound is $3(n-1)$, made of all points in $\Delta_n$ with exactly one coordinate equal to zero. | An explicit lower bound is $3(n-1)$, made of all points in $\Delta_n$ with exactly one coordinate equal to zero. | ||
An explicit upper bound comes from counting the triangles. There are $\binom{n+2}{3}$ triangles, and each point belongs to $n$ of them. So you must remove at least $(n+2)(n+1)/6$ points to remove all triangles, leaving $(n+2)(n+1)/3$ points as an upper bound for $\overline{c}^\mu_n$. | An explicit upper bound comes from counting the triangles. There are $\binom{n+2}{3}$ triangles, and each point belongs to $n$ of them. So you must remove at least $(n+2)(n+1)/6$ points to remove all triangles, leaving $(n+2)(n+1)/3$ points as an upper bound for $\overline{c}^\mu_n$. |
Revision as of 17:38, 25 July 2009
\section{Fujimura's problem}\label{fujimura-sec}
Let $\overline{c}^\mu_n$ be the size of the largest subset of the trianglular grid $$\Delta_n := \{(a,b,c)\in {\mathbb Z}^3_+ : a+b+c = n\}$$ which contains no equilateral triangles $(a+r,b,c), (a,b+r,c), (a,b,c+r)$ with $r>0$. These are upward-pointing equilateral triangles. We shall refer to such sets as 'triangle-free'. (Kobon Fujimura is a prolific inventor of puzzles, and in this puzzle asked the related question of eliminating all equilateral triangles.)
The following table was formed mostly by computer searches for optimal solutions. We also found human proofs for most of them (see {\tt http://michaelnielsen.org/polymath1/index.php?title=Fujimura's\_problem}).
\begin{figure} \centerline{ \begin{tabular}{l|llllllllllllll} $n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13\\ \hline $\overline{c}^\mu_n$ & 1 & 2 & 4 & 6 & 9 & 12 & 15 & 18 & 22 & 26 & 31 & 35 & 40 & 46 \end{tabular} } \label{lowFujimura} \caption{Fujimura numbers} \end{figure}
For any equilateral triangle $(a+r,b,c)$,$(a,b+r,c)$ and $(a,b,c+r)$, the value $y+2z$ forms an arithmetic progression of length 3. A Behrend set is a finite set of integers with no arithmetic progression of length 3 (see {\tt http://arxiv.org/PS\_cache/arxiv/pdf/0811/0811.3057v2.pdf}). By looking at those triples $(a,b,c)$ with $a+2b$ inside a Behrend set, one can obtain the lower bound of $\overline{c}^\mu_n \geq n^2 exp(-O(\sqrt{\log n}))$.
It can be shown by a 'corners theorem' of Ajtai and Szemeredi \cite{ajtai} that $\overline{c}^\mu_n = o(n^2)$ as $n \rightarrow \infty$.
An explicit lower bound is $3(n-1)$, made of all points in $\Delta_n$ with exactly one coordinate equal to zero.
An explicit upper bound comes from counting the triangles. There are $\binom{n+2}{3}$ triangles, and each point belongs to $n$ of them. So you must remove at least $(n+2)(n+1)/6$ points to remove all triangles, leaving $(n+2)(n+1)/3$ points as an upper bound for $\overline{c}^\mu_n$.