Re: [math-fun] Rectilinear crossing numbers
Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
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.
How would one go about enumerating all arrangements?
This looks relevant: http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/orderty...
Thanks. But that apparently just points to abstracts of papers that aren't online, and binary data files in undocumented formats. I re-ran my program on two billion arrangements of seven points, and counted the RCNs of each. This time, I discarded any arrangements that contained any vertical line. Earlier I had just not worried about the resulting divide-by-zero errors, as those would cause errors only in the ninth digit or later. I also checked for the other possible source of division by zero, parallel lines, but as always those never happened. I did not check for three points in a line. Anyhow, I got surprising results. There are no longer just 13 possible RCNs for n=7, there are 24: 9: 2854081 10: 1 11: 11027816 12: 1 13: 23633438 14: 6 15: 57311057 16: 2 17: 146814179 18: 4 19: 239174223 20: 6 21: 275889258 22: 4 23: 384422525 24: 1 25: 309111456 26: 2 27: 205481998 28: 2 29: 180328085 30: 1 31: 116777008 35: 47174846 I'm not sure this isn't a bug. Can someone come up with a proof that there can't be any even-numbered RCN for 7 points? Or that there can be? I got similar results for n=9, except that this time it's the even numbers that are very common and the odd numbers that are very rare: 36: 13927 38: 66278 40: 180469 42: 327642 44: 533071 46: 890830 47: 1 48: 1463260 49: 1 50: 2562426 51: 7 52: 4240140 53: 8 54: 6419703 55: 2 56: 10012353 57: 12 58: 15368762 59: 22 60: 21885908 61: 25 62: 31885941 63: 50 64: 44747612 65: 28 66: 57233553 67: 74 68: 75238774 69: 76 70: 93957198 71: 67 72: 105470193 73: 86 74: 121665340 75: 78 76: 132425970 77: 73 78: 133795238 79: 69 80: 142405957 81: 61 82: 139308013 83: 64 84: 126803508 85: 45 86: 125471727 87: 32 88: 110246476 89: 25 90: 93769089 91: 23 92: 89460437 93: 20 94: 67815191 95: 7 96: 54064073 97: 19 98: 54720289 99: 5 100: 33644869 101: 3 102: 26704075 103: 6 104: 26087965 105: 4 106: 11087442 107: 1 108: 13027353 110: 11485129 112: 1437325 113: 1 114: 5655861 116: 3348265 120: 2333611 126: 737762 I haven't done the full run for higher n yet, but there are preliminary signs that n=11 and n=17 will be almost but not quite all evens, and that n=13 and n=15 will be almost but not quite all odds. There's no sign of these biases for n=even.
On 22/07/2020 03:18, Keith F. Lynch wrote:
How would one go about enumerating all arrangements?
This looks relevant: http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/orderty...
Thanks. But that apparently just points to abstracts of papers that aren't online, and binary data files in undocumented formats.
The "theory" link goes to a list of papers that are all online there on the site -- all those ".ps.gz" links.
I re-ran my program on two billion arrangements of seven points, and counted the RCNs of each. This time, I discarded any arrangements that contained any vertical line. Earlier I had just not worried about the resulting divide-by-zero errors, as those would cause errors only in the ninth digit or later. I also checked for the other possible source of division by zero, parallel lines, but as always those never happened. I did not check for three points in a line. Anyhow, I got surprising results. There are no longer just 13 possible RCNs for n=7, there are 24:
9: 2854081 10: 1 11: 11027816 12: 1 13: 23633438 14: 6 15: 57311057 16: 2 17: 146814179 18: 4 19: 239174223 20: 6 21: 275889258 22: 4 23: 384422525 24: 1 25: 309111456 26: 2 27: 205481998 28: 2 29: 180328085 30: 1 31: 116777008 35: 47174846
I'm not sure this isn't a bug. Can someone come up with a proof that there can't be any even-numbered RCN for 7 points? Or that there can be?
For a convex 7-gon we have (7 choose 4) = 35 crossings. (Counting by multiplicity, if any crossings coincide.) When you move the points around, the number of crossings only changes when a point crosses a line. When this happens, 7-1=6 crossings appear or disappear, one for each other point. So the parity of the number of crossings, when no three points are collinear, is always the same as that of (7 choose 4). In general, when n is odd, the parity will always be the same as that of (n choose 4). That is: even when n is 0,1,2,3 mod 8 and odd when n is 4,5,6,7 mod 8. For even n, this argument doesn't lead to any restriction. I think your isolated 1s and 2s and so forth are occurring when you have points collinear or nearly enough collinear that numerical errors can produce inconsistent results. I suggest checking for collinearity and ignoring configurations where any three points are "too close" to collinear. -- g
participants (2)
-
Gareth McCaughan -
Keith F. Lynch