Timeline for More precise bound for the maximin number of arrows pointing to a square when square grid is filled with arrows
Current License: CC BY-SA 4.0
40 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 2, 2022 at 16:47 | comment | added | Wolfgang | So would it be more feasible if you start right away with a pattern like figure 6 or 7, maybe perturb it a bit, remove the symmetry condition and ask the algorithm to gently decrease the number of received hits of cells which have more than the minimum? BTW I would be curious to know how much CPU time it took typically e.g. for figure 6 or 7. | |
| Jan 31, 2022 at 17:55 | comment | added | RobPratt | Imposing symmetry and $34$ arrows pointing to each cell yields an infeasible problem. | |
| Jan 30, 2022 at 8:01 | comment | added | Wolfgang | Wow, I wouldn't have thought that such a strong constraint is possible! Now intuitively, the more constraints, the more interesting patterns show up (provided of course that a solution exists), and if you enforce moreover vertical and horizontal symmetry, a solution still should exist, probably taking more time to complete the algorithm, but definitely worth it. And BTW, have you noticed that the pattern is not all too far away from figures 6 and 7? So... | |
| Jan 30, 2022 at 3:53 | comment | added | JetfiRex | Figure 9 and 10 gives the pattern that is shown in the proof... that is beautiful, but... I hope to see there a construction (not only the calculation result) for the concrete bound soon... | |
| Jan 30, 2022 at 0:56 | history | edited | RobPratt | CC BY-SA 4.0 |
added 199 characters in body
|
| Jan 29, 2022 at 8:30 | comment | added | Wolfgang | Thank you for that, and sorry for bothering you again - these heat maps just suggest to me new directions to search. What about an optimal solution, in which the minimum (i.e. 34 here) is achieved for as many cells as possible? And then the contrary, for as few cells as possible, which may reveal new patterns again? I also see that fig. 9 and 10, though not related, feature almost the same triangles on the borders, with a slope clearly $\ne1$. So this region seems to play an important role. What then about optimal solutions where the maximum of hits of a cell is as low (or high) as possible? | |
| Jan 28, 2022 at 22:40 | comment | added | RobPratt | @Wolfgang I named them Figure 1 through 11 just now. | |
| Jan 28, 2022 at 22:38 | history | edited | RobPratt | CC BY-SA 4.0 |
added 138 characters in body
|
| Jan 28, 2022 at 20:22 | comment | added | Wolfgang | Would you mind labelling your diagrams with a, b, c... to refer more easily? | |
| Jan 28, 2022 at 20:19 | comment | added | Wolfgang | Thank you for the heat maps! But the first (symmetric) one should have the scale from 34 to about 44, if each integer gets a different colour, shouldn't it? I suppose this one belongs to your solution above "if you further restrict each direction to appear $n^2/4$ times...", right? | |
| Jan 28, 2022 at 17:08 | history | edited | RobPratt | CC BY-SA 4.0 |
edited body
|
| Jan 28, 2022 at 16:48 | history | edited | RobPratt | CC BY-SA 4.0 |
added 413 characters in body
|
| Jan 28, 2022 at 12:07 | comment | added | Wolfgang | I was thinking again about averages. In the construction of my answer, we have avg/min=13/12. I suppose that in your scenarios this ratio is much tighter, i.e. closer to 1. But are there cells getting several more hits than the minimum number? If so, it would be nice to know where they tend to be (center? maybe some preferred regions?), so if you could provide heat maps for each scenario, that might give new insights about which regions are more/less "critical" wrt to the general minimum of hits. Maybe some (roughly how many?) cells can even be modified without affecting the minimum? | |
| Jan 25, 2022 at 21:09 | comment | added | Martin Rubey | I looked at the analogous problem for a triangular region, which is probably much easier to analyse. Here the optimal values for side length $1$ to $26$ are $0, 0, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 5, 6, 6, 7, 7, 7, 8, 8, 9, 9, 10, 10, 10$. | |
| Jan 25, 2022 at 19:36 | history | edited | RobPratt | CC BY-SA 4.0 |
added 631 characters in body
|
| Jan 25, 2022 at 16:44 | comment | added | LeechLattice | The comment above shows we have $(\frac{34+6/7}{50}-o(1))n$ solutions. On the other hand, is this LP solution the unique best solution of the LP? I have also tried LP relaxations and get similar values (approximately $\sqrt \frac 1 2 -\frac {1}{2n}$ for $n \times n$, $0.69710...$ for $n=50$, compared to your $0.69714...$) but my solutions are messy, like the first picture in your answer. It may also be helpful if you can share your LP solver and the formulation of the problem in it. | |
| Jan 25, 2022 at 16:26 | comment | added | LeechLattice | Actually LP solutions serve as lower bounds: If we have a fractional assignment for $N\times N$, we can generate random arrow fillings on a $MN\times MN$ square. Dissect the $MN\times MN$ square into $N^2$ $M\times M$ sub-squares, corresponding to cells of the $N\times N$ LP solution. In a sub-square, let the directions of the cells be i.i.d random variables with P(pointing at direction x) (x∈{↑, ↓, ←, →}) at least the quantity of the direction x in the LP solution. Then as $M \rightarrow \infty$, the value on $MN \times MN$ almost surely matches the LP value with $o(n)$ error. | |
| Jan 25, 2022 at 15:05 | history | edited | RobPratt | CC BY-SA 4.0 |
added 434 characters in body
|
| Jan 25, 2022 at 14:59 | history | edited | RobPratt | CC BY-SA 4.0 |
added 434 characters in body
|
| Jan 25, 2022 at 7:36 | comment | added | JetfiRex | @Wolfgang Currently we can't say anything about the mixed structure... Something looked as stripes may be a part of mixed density and they're close to each other (For example, the density is kind of $f(x+y)$ or something.) I would not like to guess anything because the density has a square root of it and I think it may be from the integral of the linear function... and although i admit i tried (piecewise) linear density is because it Seem to be the simplest. | |
| Jan 25, 2022 at 7:24 | comment | added | Wolfgang | @JetfiRex The problem is "linear", and after the experiments it seems even clearer that at least one of the optimal constructions will consist of diagonal "segments" of a colour. It won't be "piecewise constant" proportionally to $n$, maybe part of it will, but probably it will also contain factors like $\lfloor n\sqrt{2}\rfloor$. (and this is not exactly proportional to $n$!) E.g. there may be stripes in the corners with a density half way between 1 and 2, guess what? | |
| Jan 25, 2022 at 2:38 | comment | added | JetfiRex | I am not sure whether we are going to do the experiments again... But I strongly suggest to transform the problem from ILP to LP... Piecewise constant construction won't produce any irrational numbers. To produce that square root, I think we may try at least, linear density... | |
| Jan 24, 2022 at 19:37 | history | edited | RobPratt | CC BY-SA 4.0 |
added 188 characters in body
|
| Jan 24, 2022 at 17:49 | comment | added | Wolfgang | Now that one (minimizing the number of D and U) looks extremely interesting... including the stripes in the corners. If your CPU allows, it would be definitely worth to try similar constraints for bigger n. And it looks like another example of the intriguing fact that in combinatorics, sometimes the optimal solutions are not the most symmetric ones. | |
| Jan 24, 2022 at 16:42 | history | edited | RobPratt | CC BY-SA 4.0 |
added 277 characters in body
|
| Jan 24, 2022 at 15:26 | comment | added | Wolfgang | Thank you for trying! What a pity it doesn't work, at least not with as big as $n/4$. BTW note the interesting optical effect: green and purple spots in a red environment seem much darker than in a blue environment! :) OTOH forcing symmetry is a good idea. You might try to add diagonal symmetry too (it's already pretty much there). And maybe enforcing small red resp. blue triangles in each corner. I start believing that this trial and error will eventually lead to a (certainly not THE) nice, describable optimal pattern. | |
| Jan 24, 2022 at 14:55 | comment | added | Martin Rubey | This is now findstat.org/StatisticsDatabase/St001767 (except that my code is apparently much worse than yours). | |
| Jan 23, 2022 at 21:39 | comment | added | JetfiRex | I suggest some way: If we can allow one entry be "half right, half down" or so on, would the optimality change? because if $n$ go to $2n$, it can split into four and two of them going right, two of them going down, and so on. The ILP can be done with LP somewhat... | |
| Jan 23, 2022 at 20:10 | history | edited | RobPratt | CC BY-SA 4.0 |
added 276 characters in body
|
| Jan 23, 2022 at 15:02 | comment | added | Wolfgang | (cont'd) If so, running the process several times may show which stripe widths are best suited for an optimal pattern, before starting tedious calculations. :) | |
| Jan 23, 2022 at 15:02 | comment | added | Wolfgang | For the last pattern, at the top in the middle there are 2 more or less "homogeneous" right triangles of sides n/4 (a red one to the left and a blue one to the right), likewise for the other sides of the big square (the two purple triangles are quite well visible, too). It might be worth to add that constraint, i.e. fix the arrows in those 8 triangles. The rest may group together (or be groupable together) in stripes forming diamonds around the center (for diamond sides $>n/(2\sqrt{2})$ only partial, because overlapped/"overwritten" by the 8 small triangles). (to be cont'd) | |
| Jan 23, 2022 at 10:16 | comment | added | Sean Eberhard | Is there a solution with $D_4$ or maybe even $D_8$ symmetry? | |
| Jan 23, 2022 at 1:57 | comment | added | JetfiRex | I'm sorry, but can I ask you to do me a favor... It seems that the construction has a central square boundary and there seem to be vague boundary on the four corners... Just like the location of the green entries in the proof of $n/\sqrt 2$. If you can give an asymptotic construction of $n/\sqrt 2$ based on your findings, I will really appreciate you for your work... Thank you so much for your work in advance! | |
| Jan 22, 2022 at 22:29 | comment | added | JetfiRex | Good news: That friend of mine suggested a $\sqrt 2/2$ upper bound, which, If your hypothesis (the exact number somewhat matches the sequence you gave me) is correct and we can construct using the pattern, this upper bound and lower bound matches. | |
| Jan 22, 2022 at 21:52 | history | edited | RobPratt | CC BY-SA 4.0 |
added 228 characters in body
|
| Jan 22, 2022 at 18:41 | history | edited | RobPratt | CC BY-SA 4.0 |
added 178 characters in body
|
| Jan 22, 2022 at 18:14 | history | edited | RobPratt | CC BY-SA 4.0 |
added 208 characters in body
|
| Jan 22, 2022 at 17:41 | comment | added | JetfiRex | So... A248183 suggested $\sqrt{2}/2$ asymptotic... which is really close to the upper bound $\sqrt{3}-1$. This suggested some mixed pattern though | |
| Jan 22, 2022 at 17:35 | history | edited | RobPratt | CC BY-SA 4.0 |
added 41 characters in body
|
| Jan 22, 2022 at 17:28 | history | answered | RobPratt | CC BY-SA 4.0 |