>2012

Looks like I haven’t even blogged in December. Shit, man. I think I’m kind of losing interest in real life.

I’ve had plans to an hero for some time already (months, at least, don’t remember exactly how long) but kept procrastinating. I think I’m still undecided over how I’ll proceed with this. Ideally I’d want a pain-free method since I’m really pain-averse, but I guess there aren’t alternatives for things like this.

I had some coffee about an hour ago. It did not have much effect. It’s not really keeping me awake or making me feel sleepy. It’s just… like that. Nothing.

And then on a whim I just decided to bust out my notepad/notebook (these things are actually pretty handy even though I never bother flipping back and reading past pages because my thoughts are always highly context-dependent and there’s just about no way to figure out what I’m writing unless I pen down everything that’s conspiring around me when I write) and work on that no loop problem. Remember from 2009 when I said I made a program (HTML+JS, but still!) to check if a given configuration had loops? Yeah, I still have that. On my previous laptop. Which I haven’t touched in more than a year. Screw that. Also programming is boring. Anyway. I managed to work out huge portions of what I’ve worked out before (just to confirm, because mistakes are possible, and also because I lost much of the work I had before).

A brief (re)introduction to the no loop problem would be in order. Given a graph, of all the induced subgraphs that are forests, determine the order of the largest such subgraph (and also the number of vertices “removed”, the “no-loop number”, which is more of interest due to the way the problem was originally stated). Of particular interest are square grid graphs, because they’re easy to work with (and were also part of the original problem formulation). I did a short write-up (short by my own standards, which would be “extremely short” by just about anybody else’s) about this applied to hypercube graphs, but I didn’t get far because of bugs in code which left results unreliable. (I could probably redo the code, but it’s :effort: and I’m too uninspired to do anything requiring thinking.)

Q₂: 1 removed (trivial)
Q₃: 3 removed (almost trivial)
Q₄: 6 removed
Q₅: between 12 and 14, inclusive (14 assuming the program was correct)
for : no results beyond what’s trivially implied by the above (lower bound of , or assuming the program was correct), although intuitively (and very roughly) speaking an upper bound of seems possible to prove easily. Think removing vertices by parity, then plugging back vertices where possible. Not sure how far a greedy algorithm would go with this. These bounds aren’t very tight though, which sucks. (Also lol suddenly TeX.)

Now back to square grids. (“back to” would be inappropriate here actually since I didn’t even begin with that, but whatever. Deciphering this blog’s content is part of the fun of reading it, no? >implying reading this blog is fun) Because they’re great fun. I wonder how many hours I’ve spent working on them by hand. The trivial result that a 1×1 board (oh yeah, we’ll also ignore treating the grid as a graph), or slightly more generally board requires no squares removed is kind of useless. The next step up is 2×2, which happens to be , and it’s pretty obvious that the NLN (hooray abbreviations) for this is 1, since the whole graph is a cycle. It’s not hard to extend this further, to give the result that the NLN for boards is .

That illustrates the usefulness of a lemma I omitted earlier because it was kinda obvious. For any two disjoint subgraphs of a graph, the NLN of the larger graph is at least the sum of the NLNs of the subgraphs. This readily generalises to more than two disjoint subgraphs. In the square lattice case, it allows splitting grids into smaller grids to easily obtain lower bounds.

Moving on to larger boards, we’ll skip first, and proceed to . If is even, by splitting the grid into 2×2 blocks, a lower bound of is obtained; otherwise is odd, and a lower bound of is obtained. There exists a 4×2 grid that tiles horizontally (assuming height-by-width notation like matrices (contrast the more sane and commonly used width-by-height notation used about everywhere else)) with two squares removed, leading to an upper bound of for even ; for odd half of the tile can be appended to the right end of a , with a total of squares removed, and an upper bound of . It’s effectively solved for even now, but odd still needs more work, and it’s going to be even more awkward trying to type out a proof without diagrams, but I’m too lazy to pull up diagrams, so you’ll have to trust me on this: the NLN for a grid is , regardless of parity.

As a side note I used to have a bunch of text files with nicely ASCII art illustrated proofs (for with , 5×5, 6×6, 7×7, and maybe more) hosted somewhere which is (un)fortunately no longer accessible. Oh, a complete list of all 4-removed 4×4 grids too (40 of them, 6 not counting symmetric equivalents, iirc). They’re also all on the old laptop, which is no longer accessible either. Sometimes it’s just unhelpable.

Now going back to , which is going to be easier. If is less than 4 you can easily work the NLNs out (0, 1 and 2 for respectively). That, combined with the knowledge that , leads to the lower bound , which also happens to be tight because of the existence of a 3×4 horizontal tile (“horizontal tile” meaning that it tiles horizontally, not that it is landscape, which it incidentally happens to be) with 3 squares removed, and some other things.

Now is about the right time to introduce the concept of removal density: the ratio of the number of squares removed to the total number of squares in a grid. In the above examples, for all had removal density 1/4 in the limit of . This doesn’t hold when , since (proof omitted) and . The asymptotic removal density for can be shown to be 5/18 with some effort, but the asymptotic removal density for is as yet uncertain, bounded by 19/70 (from ) and 11/40 (from existence of a 5×8 tile with 11 removed). I’m guessing that , which would conclusively answer this as 11/40, but unfortunately there’s no obvious way to prove this short of a massive brute force-like approach. I don’t feel like doing that now (hint hint read the second paragraph of this post). 11/40. Larger seem completely out-of-reach for now.

As for general upper bounds, as , the best I managed to come up with is still 1/3. It’s kind of frustrating; two of the three methods I have of covering with 1/3 removal density seem to leave few gaps, and are generally hard to improve on. (The third method is a 2×3 tile, which sucks compared to the other two because it doesn’t exploit the finiteness of ; they’re all asymptotically equivalent (in terms of density).)

Anyway, enough of pointless exposition. I know nobody’s going to read that. Not even myself. Number dump, because that’s marginally more useful. (If I do fail with my planned an heroism, these numbers are likely to be more useful than pointless exposition.)

for various values of :
5: 6
6: 8
7: 9
8: 10
9: 11 (assuming I didn’t make any wrong assumptions, the only two 5×9 grids with 11 squares removed are mirrors of each other)
10: 13
11: 14
12: 16
13: 17
14: 19
15: 20
16: 21-22 22
17: 22
18: 24
19: 25
20: 27
21: 28
22: 29-30 30
23: 30-31 31
24: 32-33 33
25: 33
26: 35
27: 36
28: 38
29: 39
30: 40-41 41

Update: After some fiddling with numbers. Only applies if , if that’s not the case, then well, the numbers are above. If or mod 8, , otherwise \rfloor.

if ; in particular, . Density is clearly 5/18 here; a similar upper bound for the density can be derived for even , but how tight it is for is unsure because the amount of effort required to prove shit grows exponentially with both and , making overall effort growth rate superexponential.

for small (because extending this is much effort):
2: 3
3: 5
4: 7
5: 9
6: 11
7: 13 (notice a pattern here?)
8: 14-15 15
9: 16-17 17
10: 18-19
:

Density is clearly bounded between 13/49 17/63 and 2/7. This one is more frustrating because it’s guaranteed that the density will never hit 2/7, but a way of removing squares with lower asymptotic density has not been found (and probably doesn’t exist).

On to …

2: 4
3: 6
4: 8
5: 10
6: 13
7: 14-15 15
8: 18 (not verified recently, but it better be correct)
9: 19-21
10: 22
11: 24-25
12: 26-27

And squares ( meaning , of course):

1²: 0
2²: 1
3²: 2
4²: 4
5²: 6
6²: 10
7²: 13
8²: 18
9²: 22
10²: 27-28 (old blog says it’s definitely 28, haven’t verified because I recall it being much effort)
11²: 32-34
12²: 40-42
13²: 45-49
14²: 54-58
15²: 62-67
16²: 72-76

The upper bounds for 10² onwards appear to be the best I can get. It doesn’t seem trivial to lower them (if that’s even possible). On the other hand the lower bounds can be considered to be “trivial” since they’re all derived from smaller rectangular boards directly. (That’s also true of all the lower bounds listed above.) It’s possible and not hard to brute force through all 4×4 4-removed grids, but the larger grids tend to have a lot of solutions.

Previously, previously. (I would search for more links but WordPress.com is seriously lagging for me.)