2

I saw many questions about intersections on here but didn't find an answer to my question. My question: Imagine you have n points which are randomly spread over a table or a sheet of paper or something else. It can be a circle formation or a rectangular pattern or any other. Now you want to link all these points to each other. There are 3 rules you have to attend.

  1. There has to be a line* between 2 any points
  2. An intersection point can only contain 2 lines.
  3. The lines don't have to be straight.

*can be a curve in general.

Is there a formula to calculate this? For example if we have 5 points so there will be 5! = 120 links in general.How can I calculate the minimum number of intersections, which satisfies all the criteria without drawing 5 points and all possible constellations? The number 5 was just an example. What if we have 10 points? Or even for n points?

I hope, you can help me.

Masirius
  • 315
  • As you may have noticed, the resulting number will be independent of the points choosen. – Loreno Heer Aug 26 '15 at 15:32
  • 1
    There is an article from 1963 in which upper bounds for the number you're looking for are written down. But I think there is no explicit formula up to the present day. The article is entitled "On the number of crossings in a complete graph" by Harary and Hill. – frog Aug 26 '15 at 15:39

1 Answers1

1

If I understand your problem correctly, this is exactly the same as Turán's brick factory problem. There is a conjecture Zarankiewicz's Conjecture which states the number to be $$\left \lfloor{\frac{n}{2}}\right \rfloor \left \lfloor{\frac{n-1}{2}}\right \rfloor \left \lfloor{\frac{m}{2}}\right \rfloor \left \lfloor{\frac{m-1}{2}}\right \rfloor $$ for a complete bipartite graph $K_{m,n}$.

For the complete graph there is a related conjecture stating the number to be

$$\frac{1}{4}\left \lfloor{\frac{n}{2}}\right \rfloor \left \lfloor{\frac{n-1}{2}}\right \rfloor \left \lfloor{\frac{n-2}{2}}\right \rfloor \left \lfloor{\frac{n-3}{2}}\right \rfloor .$$

Loreno Heer
  • 4,460
  • So if I understand your advise, there is at least 1 intersection between the lines created for 5 points, cause the result of the formula above is 1. Am I right? So for 10 points there should be at least 60 intersections? – Masirius Aug 26 '15 at 16:04
  • @Masirius yes this is correct, but keep in mind this is only a conjecture. It has been tested up to a certain number, but there is no proof that it holds for arbitrary numbers. – Loreno Heer Aug 27 '15 at 09:43
  • Here they found 62 for 10. Why are there 2 more?

    http://www.combinatorics.org/ojs/index.php/eljc/article/download/v8i1r23/pdf

     – Masirius Aug 27 '15 at 13:25
  • @Masirius The paper talks about the rectilinear crossing number, this number is not necessary equal to the (non-rectilinear) crossing number. – Loreno Heer Aug 27 '15 at 13:38
  • 1
    Ok, I got it! Thank you very much for your help! – Masirius Aug 27 '15 at 14:01