[Math] Minimum intersection of n lines

intersection-theory

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.

Best Answer

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

Related Question