10
$\begingroup$

Given a complete graph of n vertices (no three of which are no collinear) in the plane and straight edges, what is the maximal possible number of "incidental intersections" of edges, i.e., number of non-vertices at which two distinct edges intersect each other, not counting multiplicity?

This is a question that I pose to the students in my Mathematics for Elementary School Teachers as a way to understand mathematical conjecturing and proving -- and not always finding the solution. But it occurs to me that it might be handy to know whether the answer is actually known or not.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ I assume you're drawing the edges as straight line segments? $\endgroup$
    – Qiaochu Yuan
    Commented Oct 21, 2010 at 10:06
  • $\begingroup$ If multiple intersections are forbidden, it is open problem: en.wikipedia.org/wiki/Crossing_number_(graph_theory) I do not see, why it should be easier if they are permitted (and not counted)... $\endgroup$
    – Fedor Petrov
    Commented Oct 21, 2010 at 11:40
  • $\begingroup$ Fedor, I think what's open is the crossing number, which is the minimum number of non-vertex intersections, but OP is asking for the maximum. $\endgroup$
    – Gerry Myerson
    Commented Oct 21, 2010 at 12:38
  • $\begingroup$ Indeed! But then the answer is $+\infty$? Or edges are supposed to be line segments? $\endgroup$
    – Fedor Petrov
    Commented Oct 21, 2010 at 12:57
  • $\begingroup$ Reminds me of a problem discussed in amazon.com/Out-Labyrinth-Setting-Mathematics-Free/dp/0195147448, which you should totally read if you're teaching Mathematics for Elementary School Teachers. I used that exact problem with a Math Circle of 7-year-olds a few years ago, and it went over well. $\endgroup$
    – Jonah Ostroff
    Commented Oct 21, 2010 at 15:09

3 Answers 3

Reset to default
8
$\begingroup$

Assuming straight line segment edges, any 4 vertices determine 6 edges with at most one non-vertex intersection, so you can't have more than $n$-choose-4. You will have $n$-choose-4 if no vertex is interior to any triangle of vertices, which is to say if all $n$ vertices lie on the boundary.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ This isn't enough; for example, if the vertices lie at the nth roots of unity then lots of edges will intersect at the origin. You need some kind of general position requirement. $\endgroup$
    – Qiaochu Yuan
    Commented Oct 21, 2010 at 11:30
  • 2
    $\begingroup$ @Qiaochu, you are right, to get $n$-choose-4 you must arrange that no three lines meet at a non-vertex point. Of course, that's easily done; if three meet, just move one vertex a tiny bit. $\endgroup$
    – Gerry Myerson
    Commented Oct 21, 2010 at 12:35
3
$\begingroup$

This problem (although phrased slightly differently) is #1.3.5 in Loren C. Larson's "Problem Solving Through Problems."

The rephrase of this is, "On a circle, n points are selected and the chords joining them in pairs are drawn. Assuming no three of the chords are concurrent (except at the endpoints), how many points of intersection are there?"

This is $\binom{n}{4}$, as any four of our points on the circle determine a (unique) intersection point, and any intersection point determines the boundary chords.

[This might've been better as a comment on Gerry's answer, but there's a whole family of similar problems to the question asker's in that chapter of the book (which are also excellent problems to give to a math club.)]

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the citation -- I didn't know about this book, to my embarassment. I like the almost Zen-like redundancy of the tile. $\endgroup$
    – Brendan Foreman
    Commented Oct 22, 2010 at 11:28
  • $\begingroup$ The nice continuation of this problem is, with the construction above, how many regions did you break the circle into? The pattern at the beginning is (for n=# points on the circle): 1,2,4,8,16... Then 31. It's another good counterexample to the, "Test the first five cases then make a conjecture." $\endgroup$
    – Gwyn Whieldon
    Commented Oct 22, 2010 at 12:28
1
$\begingroup$

If you let me do something silly, then I can put all the points in a line. Technically this gives an infinite number of points of intersection, since every point on the line segment is a point of intersection of two edges. If instead I count the number of pairs of edges which contain a non-vertex in their intersection then I still get

\begin{equation*} \binom{\binom{n}{2}}{2} - \sum_{1 < i \leq j < n} (i-1)(n-j), \end{equation*}

which I guess is maximum (it's more than $\binom{n}{4}$).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .