N points in a plane

Ask the math tutor!

N points in a plane

Postby harry.petrone » Sun Mar 26, 2017 4:10 am

Find the maximum number of points in a plane for which, among any 3 of them, there is always one pair having a distance of 1.





harry.petrone
 
Posts: 2
Joined: Sun Mar 26, 2017 4:07 am
Reputation: 0

Re: N points in a plane

Postby harry.petrone » Sun Mar 26, 2017 4:16 am

This is probably graph theory but it is not my favorite subject :)
I guess we start with unit circles where all the points of distance 1 lie.
Not sure what to do next.

harry.petrone
 
Posts: 2
Joined: Sun Mar 26, 2017 4:07 am
Reputation: 0

Re: N points in a plane

Postby Guest » Sun Mar 26, 2017 8:47 am

The answer is 7.

Probably the easiest way to go about it is to inductively (on the number of vertices) construct all edge minimal graphs (where an edge indicates the vertices are of distance 1).

On 1 vertex there is one graph (just the vertex itself).

On 2 vertices there is one graph (just the pair of vertices with no edge between them (remember we are looking for edge minimal graphs)).

On 3 vertices there is one graph (an edge together with an isolated vertex).

On 4 vertices there are two graphs, which we can deduce by building on the 3 vertex case. If we add an extra vertex there are only a few ways we could join it to the 3 vertex case:
a) No edges from the new vertex. This forces all the other edges to be present, resulting in the minimal graph which is a triangle together with an isolated vertex.
b) One edge, from the new vertex to the isolated vertex. We don't need to add any other edges to make this work, the graph of two separate edges is edge minimal.
c) One edge, from the new vertex to an end point of an edge. This forces the edge from the other end of the "3-vertex case edge" to the isolated vertex to be present, which means this graph contains case (b) so is not edge minimal.
d) two edges, one to the isolated vertex, the other to the end point of the existing edge. Not minimal because it contains case (b).
e) two edges, both to the end points of the existing edge. Not minimal contains case (a).
f) three edges. Not minimal contains case (a).

On 5 vertices there are two graphs. A triangle with an edge, and a pentagon. I'll leave the reasoning as an exercise for you to do.

On 6 vertices there are two graphs. One of them is two triangles, I'll leave the other one for you to find.

On 7 vertices there is one graph, and on 8 vertices there are no graphs, I'll leave these as an exercise for you to do.

Hope this helped,

R. Baber.

Guest
 

Re: N points in a plane

Postby Math Tutor » Mon Mar 27, 2017 7:31 am

Mr. Rabber is a genius.

Math Tutor
Site Admin
 
Posts: 385
Joined: Sun Oct 09, 2005 11:37 am
Reputation: 13

Re: N points in a plane

Postby Guest » Mon Mar 27, 2017 10:29 am

For sure!

Guest
 

Re: N points in a plane

Postby jason » Sun Apr 02, 2017 4:14 am

Nice problem!

Edge minimal graphs? No idea what this is :(
Any shape, anyone?

jason
 
Posts: 11
Joined: Wed Jan 11, 2017 10:17 am
Reputation: 0

Re: N points in a plane

Postby Guest » Sun Apr 02, 2017 8:20 am

Minimal is a mathematical term that indicates of all the things that can be compared with the object, nothing is smaller. See
http://math.stackexchange.com/questions ... nd-minimal
In our case, the objects are graphs (on a fixed number of vertices), the comparison operator is defined as subgraph inclusion. If graph A is a (strict) subgraph of graph B (i.e. A is just B but with some edges missing) then A is less than B, or equivalently, B is greater than A. If A is not a subgraph of B, and B is not a subgraph of A, we say that they are not comparable.

On three vertices there are three graphs that satisfy the problem's criteria:
a) The graph on three vertices and one edge between two of the vertices.
b) The graph on three vertices and two edges.
c) The graph on three vertices with all three edges present.
However, only (a) is edge minimal, it is a subgraph of (b) and (c). If we take any graph that satisfies the criteria and is edge minimal, then add edges (without breaking the condition that it is planar) we'll still end up with a graph satisfying the criteria. The edge minimal graph is the underlying thing that is satisfying the criteria.

By keeping track of just the edge minimal graphs we reduce the number of graphs we need to keep track of at each stage. For example on 4 vertices there are 6 graphs that work, but only 2 are edge minimal. On 5 vertices there are 8 graphs that work, but again only 2 are edge minimal. The problem is a lot more manageable when only looking for the edge minimal cases.

Hope this helped,

R. Baber.

Guest
 

Re: N points in a plane

Postby Guest » Sun Apr 02, 2017 8:34 am

Another way of looking at it, is that the edge minimal examples are the "simplest" graphs that satisfy the criteria.

If I have a graph that satisfies the criteria but I can remove an edge and it still satisfies the criteria, then the graph I started with wasn't as simple as it could have been (it wasn't edge minimal: there was a simpler "smaller" subgraph that was inside it).

If I have a graph that satisfies the criteria but whatever edge I try removing always results in something that does not satisfy the criteria, then the graph is as simple as possible (it is edge minimal: there are no simpler "smaller" subgraphs inside it that work).

R. Baber.

Guest
 

Re: N points in a plane

Postby Guest » Sun Apr 02, 2017 12:27 pm

Sorry I made a minor mistake: there are only 7 graphs that work on 5 vertices.

R. Baber.

Guest
 

Re: N points in a plane

Postby Guest » Tue Apr 11, 2017 9:32 am

Guest wrote:The answer is 7.

Probably the easiest way to go about it is to inductively (on the number of vertices) construct all edge minimal graphs (where an edge indicates the vertices are of distance 1).

On 1 vertex there is one graph (just the vertex itself).

On 2 vertices there is one graph (just the pair of vertices with no edge between them (remember we are looking for edge minimal graphs)).

On 3 vertices there is one graph (an edge together with an isolated vertex).

On 4 vertices there are two graphs, which we can deduce by building on the 3 vertex case. If we add an extra vertex there are only a few ways we could join it to the 3 vertex case:
a) No edges from the new vertex. This forces all the other edges to be present, resulting in the minimal graph which is a triangle together with an isolated vertex.
b) One edge, from the new vertex to the isolated vertex. We don't need to add any other edges to make this work, the graph of two separate edges is edge minimal.
c) One edge, from the new vertex to an end point of an edge. This forces the edge from the other end of the "3-vertex case edge" to the isolated vertex to be present, which means this graph contains case (b) so is not edge minimal.
d) two edges, one to the isolated vertex, the other to the end point of the existing edge. Not minimal because it contains case (b).
e) two edges, both to the end points of the existing edge. Not minimal contains case (a).
f) three edges. Not minimal contains case (a).

On 5 vertices there are two graphs. A triangle with an edge, and a pentagon. I'll leave the reasoning as an exercise for you to do.

On 6 vertices there are two graphs. One of them is two triangles, I'll leave the other one for you to find.

On 7 vertices there is one graph, and on 8 vertices there are no graphs, I'll leave these as an exercise for you to do.

Hope this helped,

R. Baber.


Dear R. Baber, what is the graph with 7 vertices? And how do we deduce there are no graphs with 8 vertices?

Guest
 


Return to Ask the tutor



Who is online

Users browsing this forum: No registered users and 1 guest