Loop removal

I've actually been thinking whether this information really belongs here, since it's a bit more like applied maths than pure maths, but heck. Anyway, an introduction to the no-loop problem, posed by Douglas. In it's most original form, you started out with an m×n rectangular grid, and the no-loop number is the minimum number of cells that need to be removed so that there are no loops that can be formed from orthogonal connections. In a less primitive form, it involves graphs, and the no-loop number is now the number of vertices that need to be removed so that there are no cycles. The no-loop problem then asks what the no-loop number is, for a certain graph or m×n rectangular grid. Douglas also mentioned a variant on the rectangular grid version earlier this year, removing dominoes (adjacent cells) instead of single cells, but I won't cover this here now. I've written quite a bit of stuff already before this blog was started, you can see them here, and here. (Note that the second link might die soon.)

The n×n squares have been pretty extensively checked for correctness, and so are the 6×n grids. I've reviewed the 6×6 proof more than thrice, 7×7 proof twice, and 8×8 proof twice, so they're almost definitely right. The current big question is what the asymptotic removal density is. (If you're so dense (no pun intended), the removal density refers to the no-loop number divided by the total number of cells.) I've conjectured that it's 1/3, having found 3 ways to fill the grid, loopless, at that density. However, it almost seems wrong, in that the currently known limit is for the 15×15, at 0.2977… removal density, significantly less than 1/3=0.3333…. If you can find a tile that tiles loopless at a density lower than 1/3, I salute you. It's not trivial, if it exists. Also, bonus reward if you can show that that isn't optimal, and extra bonus if you show whether the asymptotic removal density is irrational.

Another issue I'm currently tackling is also the exact removal density, at least for some values of m in m×n. I've only managed to do this for m∈{1, 2, 3, 4, 6}, and was trying to work it out for m=5. m=7 or 9 seems out of reach for now, and m=8 looks barely possible.

As for the graph generalisation, I haven't done much work on it, having focused solely on the rectangular grids. However, do note that I have proven that the four-dimensional hypercube graph needs 6 vertices removed, and that the five-dimensional hypercube graph needs somewhere between 12 and 14 (inclusive). The former proven by showing equivalence of upper and lower bounds, latter, well, duh. Anyone can do better with a 13 or 12 upper bound?