The term "rectilinear crossing number" (RCN) for Kn (the complete graph on n points) seems to be used interchangeably for the smallest such number and for every such number. Is there an official way to distinguish? I hope it's clear from context in the following which I mean in each case. Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:

.... So your numbers are right.

Thanks. I always like to hear that. :-)

"Keith F. Lynch" <kfl@KeithLynch.net> wrote:

...

So with six points I expected to get four possible numbers of crossings. Instead, I got eleven, from 3 to 15. I don't know what most of them mean.

...

I looked up 1,2,3,11 in OEIS, and I get way too many hits. I guess I'll have to try 7 points, to get the next term.

I tried 7 through 30 vertices. The series seems to start 1,1,1,2,3,11,13,47,52,136. But the last three terms are almost certainly wrong. The 11 (for K6) is probably right, since I get at least a six-digit number of hits for every RCN that gets any hits at all (3,4,5,6,7,8,9,10,11,12,15). The 13 (for K7) is probably right, since I get at least a five-digit number of hits for every RCN. The 47 (for K8) is probably wrong, since one of them (64) gets only one hit. Other than that, they all get at least a four-digit number of hits, and 15 of them get more than a million hits each. Given how irregular that one is, I'm no longer certain of the 13, or even the 11. With that caveat, the series doesn't seem to be in OEIS. The 136 (for K10) is certainly wrong, since the smallest RCN I found was 63, but A014540 says the (minimal) RCN for K10 is 62. The smallest RCNs I get for K11 through K30 also exceed the official numbers. And the *largest* RCNs I get for K13 through K30 are all too low, meaning that the odds of more than a dozen randomly placed points all being on their convex hull are very slim. OEIS says the RCN for K28 is definitely either 7233 or 7234. I get 8995, which gets just one hit. That's with 2.5 million random sets of 28 points. Sigh.

The maximum number of intersections is always (n choose 4). If you pick any four of the vertices, there's just one interior intersection formed by edges between them.

Thanks.

The number of _distinct points_ they produce can be less when more than two edges meet at a point.

As a computer guy, I've always been comfortable with the idea that two points can be in the same place. Apparently mainstream mathematicians don't think that way.

I don't have much intuition for which of the numbers in [rectilinear crossing number, (n choose 4)] are actually attainable. Unless the pattern is very simple, I suspect it's going to be pretty tough to count them.

Indeed. Scattering points at random, as I've been doing, can at best give a lower limit to how many such numbers there are for Kn. And at best can give an upper limit to the minimal RCN for each Kn. What's needed is a way to look at every possible arrangement of n points. By "arrangement" I don't mean the uncountable infinity of possible locations of points in the unit square, I mean a difference that makes a difference. After some thought, I'm convinced that a crossing number for a specific arrangement of n points can only change if one of the points crosses an edge. So for any n there are certainly only a finite number of arrangements. There are n-choose-3 triangles and for each triangle each vertex is either in it or not in it. (A vertex can be in multiple triangles, since many triangles overlap.) (I don't count the vertices *of* a triangle as being in that triangle.) So the maximum number of arrangements is 2^n * n-choose-3. It will usually be much less, since most such arrangements are impossible. (Alternatively, for each pair of edges that don't share an endpoint, they either cross or not, so that's 2^(3*(n-choose-4)), but I think that's usually a much larger number.) How would one go about enumerating all arrangements? Starting from a regular n-gon, you could do a depth-first or breadth-first search in which vertices cross accessible edges, where "accessible" means the vertex can cross it without crossing another edge first and without dragging one of its own edges across another vertex. You'd be done when every possible move reaches an arrangement that's already been found. Getting back to n=6, I still have no idea, for most of the 11 RCNs, which of them correspond to each of the four possible perimeters (triangle containing three points, ..., convex hexagon containing no points), or whether one of them can correspond to two possible perimeters. I had previously guessed that the number of RCNs was equal to the number of possible perimeters, at least through n=6. For n=7, I thought I might get an additional RCN that distinguishes between a triangle containing a convex quadrilateral and a triangle containing a triangle containing a point, for a total of 6 RCNs. Instead I get 13. Who knew that points in a plane and the lines connecting them could be so complicated? Does anyone know of any good online sources that explain what's known? I looked up the RCN Project, but there's little useful information there, and its website doesn't seem to have been maintained or updated since about a decade ago anyhow. One thing I have noticed is that the next to largest RCN for Kn always seems to be n-3 less than the largest RCN for Kn. That makes sense, since pushing one of the vertices just enough that the figure is no longer convex means the edge connecting its neighboring vertices to each other no longer crosses anything, when previously it had crossed all but 2 of the N-1 edges that terminate on the vertex we moved.