Search Results

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 …

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 …

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, …

This sort of addresses the question in your last paragraph, but it is actually a bit tangential. Hopefully it is still of interest. It is well known that every planar graph has an embedding such t …

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 …

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 …

In a comment to this question, Tim Gowers remarked that using the axiom of choice, one can show that there exists a subset of the plane that intersects every line exactly twice (although it has yet to …

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^{\ …

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 …

If the length divided by the width is rational, then yes. Just partition the rectangle into congruent squares and cut each square along a diagonal.

Regarding III, the Alexandrov-Urysohn Theorem gives sufficient conditions. Any zero-dimensional, separable, nowhere compact, and completely metrizable space is homeomorphic to $J$.

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 …

If you only care about the length of the path between the first and last bus stops, then it looks like you are trying to solve the shortest Hamiltonian path problem (HPP). This is related to the more …

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$ …

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'.