Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
I assume you're drawing the edges as straight line segments? –  Qiaochu Yuan Oct 21 '10 at 10:06
    
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)... –  Fedor Petrov Oct 21 '10 at 11:40
    
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. –  Gerry Myerson Oct 21 '10 at 12:38
    
Indeed! But then the answer is $+\infty$? Or edges are supposed to be line segments? –  Fedor Petrov Oct 21 '10 at 12:57
    
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. –  Jonah Ostroff Oct 21 '10 at 15:09
show 2 more comments

3 Answers 3

up vote 7 down vote accepted

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.

share|improve this answer
3  
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. –  Qiaochu Yuan Oct 21 '10 at 11:30
1  
@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. –  Gerry Myerson Oct 21 '10 at 12:35
add comment

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.)]

share|improve this answer
    
Thanks for the citation -- I didn't know about this book, to my embarassment. I like the almost Zen-like redundancy of the tile. –  Brendan Foreman Oct 22 '10 at 11:28
    
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." –  Gwyn Whieldon Oct 22 '10 at 12:28
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.