Search Results

Yes, there are non-square rectangles that admit a perfect squaring. The smallest number of squares in a perfect squaring of a rectangle is 9. On the other hand the smallest number of squares in a per …

Pilipczuk and Siebertz proved that every planar graph has such a partition with an even stronger property. Namely, each part $V_i$ is a geodesic path, and the graph obtained by contracting each part …

In the case that the pursuers have to actually catch the fugitive, this was answered in the article Escaping an infinitude of lions by Mikkel Abrahamsen, Jacob Holm, Eva Rotenberg, and Christian Wulff …

No polynomial-time algorithm exists, unless P=NP. Indeed, even for TSP instances where all distances are $1$ or $2$ (note that these automatically satisfy the triangle inequality), Engebretsen and Kar …

Update. The recent paper Every $d(d+1)$-connected graph is globally rigid in $\mathbb{R}^d$ by Soma Villányi gives a positive answer to the question. Old Answer. I think this is still an open problem, …

For A), here is a construction that gives $2\binom{n}{3}$ defective triples, which is almost best possible. Let $D$ be a digraph with vertex set $[n]$ and arcs $(i,i+1)$ and $(i+1, i)$ for all $i \in …

There is a wide body of work on this in connection with the classic De Bruijn–Erdős theorem. De Bruijn–Erdős Theorem. Every set of $n$ points in the plane (not all lying on the same line) deter …

No. The set of all $\{0,1\}$-sequences is also a clique in $G$. Thus, $\chi(G) \geq 2^{\aleph_0}$. On the other hand, the set of all bounded real sequences has size $2^{\aleph_0}$, so $\chi(G)=2^{\ …

Here is a generalization to arbitrary finite metric spaces. Recall that the Sylvester-Gallai theorem easily implies the following theorem. Theorem to be generalized. Every non-collinear set of $n$ …

This is an answer to your last question. As far as I know, it is still open whether there exists a dense subset $S$ of the plane with all pairwise distances rational. Such a set $S$ would imply a po …

Yes. See this paper of Negami. The main result is that for any fixed knot (or link) of type $k$, there is a constant $R(k)$ such that every straight line embedding of $K_{R(k)}$ in $\mathbb{R}^3$ con …

Note that the answer is yes in 2 dimensions, since any polygon can be triangulated (without adding additional vertices). Thus, every point in the interior sees at least 3 vertices of $P$. One can …

Terry Tao has a nice blog post on a 'cheap version' of the Kabatjanskii-Levenstein bound mentioned in Lucia's answer, using the so-called 'tensor product trick'.

The answer to the third question is no. This is a rather counter-intuitive discovery of Micha Perles from the sixties. See this paper of Ziegler, for a simpler construction and other pertinent infor …

As Boris Bukh points out, three points suffice, but I'd like to point out that your question is related to this MO question. Here is a summary of the information in the previous question. For the …