Simple to state open problems

The Square of a Directed Graph

(Taken from the DIMACS site)
DESCRIPTION: This problem deals with the "square of an oriented graph." An oriented graph is a simple graph (no loops or multiple edges) in which each edge is replaced by an arc. Thus you produce a simple directed graph without pairs of "reversed arcs."

To get the square of an oriented graph (or any directed graph) you leave the vertex set the same, keep all the arcs, and for each pair of arcs of the form (u,v), (v,w), you add the arc (u,w) if that arc was not already present. An example of an oriented graph and its square is shown above.

Here is the open problem: Prove that for every oriented graph, D, there exists a vertex whose out-degree at least doubles when you square the oriented graph. In the example above, the vertices A, B, C, E and G satisfy this property. (For vertices A and G, 2*0=0). Nate learned of this problem from Paul Seymour. David Fisher proved this theorem for tournaments, i.e., orientations of complete graphs.

Points on a Parabola

(Taken from the DIMACS site)
DESCRIPTION:The problems is this: How many points can you find on the (half) parabola y=x^2, x>0, so that the distance between any pair of them is rational? This problem sounds like a geometry problem, but it is likely to require techniques in number theory. That's because, to determine if the distance between (a,b) and (s,t) is rational, you need to test whether (a-s)^2 + (b-t)^2 is the square of a rational number...and such questions typically fall into the realm of number theory.

Of course, since this is an open problem, no-one can claim to know just what field the problem lies in, since no-one knows the solution.

I believe it is not even known if there are more than 5 points on the parabola which satisfy the condition. It is certainly not known if there is an infinite family with pairwise rational distances. We can quickly see that there are three such points in the following way: Pick two rational numbers, say 1/5 and 3/5, and let those be the distances between the pairs of points AB and BC. If you fix those distances and slide the points up the parabola, the distance AC will gradually increase, bounded above by 4/5. Since the rational numbers are dense in the reals, there will be many placements of the points so that AC is a rational distance.

It is not too hard to show that if you have N points on the parabola with rational distances between them, then you can find N points on the parabola with integer distances between them.

The Turnpike Reconstruction Problem

(My Advisor introduced me to this problem)
DESCRIPTION: Suppose you have been given a set of n points on a line. Then its easy to find the interpoint distance between them. Now suppose that you have been given this distance multiset. Then give a polynomial time algorithm to find a set of points that satisfy this distance multiset.
Mangesh Gupte <mangesh[at]csa.iisc.ernet.in>
Last modified: Mon Apr 18 01:39:48 2005