## Reflections on national service

So, I’m nearing the end of my stint as a conscriptee, with about ten working days left. (Ten? Twenty? Same order of magnitude, whatever.)

I think my number-one takeaway from the whole experience is that my nature to procrastinate hasn’t really improved much at all. Maybe just a bit, though.

I’m desperately trying to clear all the shit I have accumulated from twenty-odd months of laziness, and hopefully I don’t have to pass this stuff on to the poor new guy and let him be swamped with work from the get-go.

Yet somehow I got awarded that “outstanding serviceman” thing. (Which I’ve referred to in an earlier post.) I tried to turn it down, but you know, things don’t always turn out the way we want them to. On the other hand, I didn’t try to the extent of pointing out that 90% of the recommendation write-up was either misleadingly exaggerated or outright fabricated. To date, I still haven’t fully read my own write-up; while I’ve proofread the write-ups for previous award recipients, I decided to let someone else go through this one. If I had done it myself, I probably would’ve deleted the 90%. My superiors/bosses were kinda “desperate” to give me this award before I left service, but whatever.

I’m not sure there’s much more I could write that I haven’t already. There’s the usual I-lost-faith-in-Singaporeans schtick but I’m sure you’re sick of that. Incidentally, I was watching some old Ch 8 drama on TV earlier (killing time etc.), and it kind of just struck me how, even if the characters are exaggerated (it’s television), the archetypes are actually present in society, and I’ve encountered them through all the hundreds of people I have to work with/for.

I really would like to thank my parents for at least making me not a completely inconsiderate jerk. (Even if they’ve screwed up all other parts of my personality.) It amazes me how some people are entirely incapable of looking at the big picture and somehow get stuck in some Nash equilibrium of selfishness.

## グラフ

So, like I covered in the last post about graphs, the hypercube graphs form a family of graphs with the property that any subgraph of any graph in the family is also an induced subgraph of some graph in the same family. A natural extension is to ask, what sets of graphs also have this property?

This question, by itself, turns out to have too many answers. Consider the set of all graphs; any subgraph of any graph in this set is obviously also in this set, and so trivially satisfies this property. On the other end of triviality, the set of graphs with no edges also satisfies this property.

Removing any finite number of graphs from these sets (hypercube graphs, all graphs, vertex-only graphs) still produces sets satisfying this condition.

Considering one-graph sets first, the only graphs where all its subgraphs are also induced subgraphs is pretty easily shown to be the vertex-only graphs. Proof: suppose otherwise, then the graph has at least one edge. By removing the edge, we get a graph with as many vertices but one less edge, which cannot be an induced subgraph.

What about pairs of graphs? With this, we get the case of having two vertex-only graphs (boring) and the case of having one one-edge graph and one vertex-only graph with at least as many vertices as the one-edge graph. In fact, it seems that any finite set of graphs satisfying this property necessarily has one vertex-only graph. Proof: let $G$ be a graph with the most vertices in such a set, and consider the subgraph with vertex set $V(G)$ and edge set $\{\}$. The only graph of order $v(G)$ that has this graph as an induced subgraph is itself; therefore, this graph is in the set.

This proof fails for infinite sets because there’s no largest graph.

Alternatively, we can also cast this as a question on infinite graphs. What infinite graphs have as induced subgraphs all of its subgraphs? Other than the trivial vertex-only graph, the Rado graph is one, and so is the infinite extension of the hypercube graph (where the vertex set is the nonnegative integers, and vertices are connected iff they differ in exactly one bit). What else?

## lolratings

Come for the yuri, stay for the tears.

The film is rated M18, and I’m going to guess that it’s because of this subplot. Hmm. (But of course, the rating in other countries is considerably less strict.)

## Sometimes, people _don’t_ grow up

I vaguely recall making a comment on how I’ve actually grown up before, either on this blog, my previous blog, or Twatter Twitter.

But what does it mean to grow up? I indulge in much the same things as I did five years before: watching shows (now online instead of on television, but much the same), doing mathematics, occasionally dabbling in origami. I gueeeess I can kinda include music listening in this because I didn’t use to do this music downloading thing in the past, but really, what I’ve been doing then and what I’m doing now is probably 80% the same. What about the rest; what’s different?

I’ve learnt to accept that people can have differing opinions. If I think A is better than B, but you think otherwise, and can justify your opinion, that’s not really something I can fault you for. Sometimes I can’t justify my own opinion either, which is something that’s appeared in some of the blog posts I’ve written.

At this point, I’d like to bring up once again the quip of me “cheating” in the Euclidean geometry exam in Year 2; just by knowing some things, people might assume you know other things too. This is actually pretty dangerous sometimes, because it’s a device that can be used to easily kill arguments. People generally know I’m a guy capable of dealing with mathematics/logic pretty well, and at the same time I make sure people also know that so they don’t argue with me over pointless things I should know better about. Operative word being “should”; sometimes I really am just bullshitting, even if I don’t realise it myself! (This of course has nothing to do with “maturity”, but was just something that happened to come to mind.)

But anyway, earlier this year there was a talk in camp by some external speakers, and it turned out pretty much like how talks in NUS High did. People not paying attention, chatting with each other, generally being disrespectful, et cetera. I don’t remember the subject of the talk, but it was probably something important, like about dengue or something. (If it weren’t important, I wouldn’t have faulted the audience for not caring about it!) It’s rather disgraceful, even, because the average age of the people in camp is somewhat higher. Not only because we graduate from school before being conscripted, but with the additional factor that (spoilers) where I am, a relatively huge chunk of people are also poly grads (and poly diplomas usually take 3-5 years, versus 2 for JC/equivalent). (There’re also some dropouts but those seem to be a minority; my impression however may be biased because the largest group of my customers have as a prerequisite A-levels/equivalent or a diploma.)

Yet, in NUS High, I recall of teachers asking us to be more mature, given how we weren’t primary school children / Year 1/2 students / etc. Actually, come to think about it, this is kind of an infinite regress: if we don’t act like their ideals (putting aside who that “their” is supposed to refer to), then they’ll just claim we’re not acting our age. But whatever.

## Numbers

When should numbers be spelt out in English, and when numerals?

The most common style guides I’ve seen suggest spelling out for numbers ten or below, and numerals for anything higher.

Which is actually really retarded because it leads to ugly-looking statements like “ten or 11″ instead of the more consistent-looking “10 or 11″ / “ten or eleven”.

I’ve mostly tried to be consistent with the way I use numbers in this blog, though it’d be pertinent to note that being a (somewhat) mathematical blog, the rules ought to be different from writing essays or articles.

Small numbers that result from some calculation are written in numerals. Otherwise, they’re written in English. Large numbers are always written in numerals.

I don’t set a hard threshold but generally things that require compound words or more than one word are numerals-only. (“twenty” is go, “twenty-one” is no go.)

The above rule gets a bit murky when it comes to combinatorics because “counting” things isn’t really a calculation, yet it’s also sometimes possible to express the counting as a formula to be evaluated. Luckily, combinatorial explosion also means this doesn’t come up often.

## The new interface sucks

### Section −1: Preface

This post has been updated multiple times since it was originally published to fix some minor mistakes and for general cleaning up. Summary of changes: a “the the” typo, using the word “acyclic” in place of “cycle-free”, correcting a mention of $Q_8$ being the smallest hypercube graph to have $C_8$ as an induced subgraph (this happened over about four edits), relaxing the parity restriction (with another edit to escape the braces in a formula), and adding this preface.

### Section 0: Introduction

We may define the family of hypercube graphs, $Q_k$ for nonnegative integer $k$, as such:

$\displaystyle V(Q_k)=\left\{0,\cdots,2^k-1\right\}$
$\displaystyle E(Q_k)=\left\{(i,j)|H(i\oplus j)=1\right\}$

where $H$ is the Hamming weight (i.e. binary digit sum) and $\oplus$ is binary xor. Note that $v(Q_k)=2^k$ and $e(Q_k)=k2^{k-1}$.

The parity of a vertex may be defined as the parity of its Hamming weight; i.e. the even vertices are 0, 3, 5, 6, … and the odd vertices are 1, 2, 4, 7, … This categorisation incidentally also provides a two-colouring of the vertices, and is closely related to the Thue-Morse sequence.

### Section 1: Induced subgraphs of hypercube graphs

Given the above, as induced subgraphs are identified by the vertices present, we may represent an induced subgraph of $Q_k$ as a sequence of (at most) $2^k$ bits. An induced subgraph of a hypercube graph is also an induced subgraph of any larger hypercube graph, hence we do not need the dimensionality in order to interpret a binary sequence as an induced subgraph of a hypercube graph. Furthermore, we may assume that a sequence is followed by an infinite trail of zeros.

$()$ is the empty graph, $(1)$ is isomorphic to the graph of one vertex, $(1,1)$ is isomorphic to a path of order two, $(1,1,1,1)$ is isomorphic to a cycle of length four, $(0,1,1,1,1,1,1)$ is isomorphic to a cycle of length six, $(1,1,1,0,1,0,0,0,1)$ is isomorphic to a five-vertex star, et cetera.

### Section 2: Untitled

All (finite) trees are isomorphic to some induced subgraph of some hypercube graph. By extension, so are all (finite) forests.

Likewise, all even cycles are isomorphic to some induced subgraph of some hypercube graph. By extension, all bipartite graphs are too.

A proof by construction is tedious but not difficult, and is left as an exercise for the reader.

As hypercube graphs are bipartite, nonbipartite graphs cannot be subgraphs of hypercube graphs. Therefore, all subgraphs of hypercube graphs are also induced subgraphs of hypercube graphs, though an embedding as an induced subgraph may be of higher dimensionality.

For example, the cycle $C_8$ is a subgraph of $Q_3$, but the smallest hypercube graph that has it as an induced subgraph is $Q_4$, where eight vertices form some sort of a tetrahedral antihyperprism. (I so totally invented this word.) One such embedding would be $(0,1,1,1,1,0,1,0,1,1,0,0,1)$.

### Section 3: Parity-restricted induced subgraphs

There are two ways of having a parity restriction. For an induced subgraph with only vertices of even parity, $c(G)=v(G)$ and $e(G)=0$, which is rather boring and uninteresting. Instead, consider an induced subgraph such that $V(Q_k-G)$ only has even vertices, or equivalently, such that $V(G)$ contains all odd vertices in $Q_k$. This notion of parity restriction does depend on the dimensionality; additionally, a graph satisfying the parity restriction may be isomorphic to a graph that doesn’t, for any given dimensionality.

This definition may be relaxed to give the mostly functionally equivalent requirement of $|\{H(v)|v\in V(Q_k-G)\}|=1$, or in other words, that $G$ contains all vertices of a particular parity.

If a parity-restricted induced subgraph is acyclic, its components are all stars (assuming that the trivial one-vertex graph is considered a star).

### Section 4: There is no section four

Unrelated to graphs or even the current topic, but somewhat related to geometry in higher dimensions, the only regular polygons that can be embedded with integer coordinates in arbitrarily many dimensions are the triangle, square and hexagon, where the triangle and hexagon require three dimensions and the square requires two dimensions. A proof follows from Niven’s theorem, which was previously mentioned on this blog regarding linear recurrences.

### Section 5: Experimental results

For dimensions 2, 3, 4 and 5, the set of largest (by vertex count) acyclic induced subgraphs includes parity-restricted graphs, though is not always limited to them.

For instance, $(0,1,1,1,1,1)$ does not satisfy the parity restriction for $k=3$, but is isomorphic to a five-vertex path, which is acyclic.

## What is a lulz?

>>> A = [filter(lambda x:popcnt(x)==k,range(65536)) for k in range(17)]
>>> filter(check_forest,A[10])
[27606, 28086, 31134, 38889, 40569, 46701, 54891, 59799]


I don’t expect you to remember those numbers, but they last appeared in this 2010 blog post. I recoded it in Python, though I deliberately left it easy to port to C. (Stealth update note: try not to run that in CPython. Use PyPy instead; it’s a lot faster. This doesn’t have any dependency on external libraries, so using PyPy should be straightforward. There’s some “dead” code which is really just WIP stuff that isn’t finished yet.)

>>> map(lambda k:len(filter(check_forest,A[k])),range(17))
[1, 16, 120, 560, 1796, 4080, 6488, 6848, 4090, 1008, 8, 0, 0, 0, 0, 0, 0]


This bit also agrees with what I mentioned on zznq in an accompanying blog post regarding $Q_4$. As a bonus, my numbers for $Q_5$ match up: this code counts 2160 (not necessarily distinct) 18-vertex induced forests of $Q_5$, as expected.

$Q_5$ has 3840 automorphisms though, and $\gcd(2160,3840)=240$. Does this mean we have nine distinct graphs, each with sixteen automorphisms? Or maybe there’s an automorphism that’s not a hypercube automorphism. Hmm. Guess I should write a symmetry checker too.

I also figured out why my earlier code counted only 1952, which actually also meant that the forest-checking function was correct, and only my “optimisations” were wrong. I divided $Q_5$ into two $Q_4$s, then looped over the case where both $Q_4$s had seven vertices removed (1744 ways), then the case where one has six removed and the other eight removed (416 ways). I counted only half of the second case in my earlier code.

Anyway, the largest forest in $Q_6$ has 36 vertices. The code spits out 240 entries, which makes me suspect they’re all isomorphic. (I don’t have the code to check isomorphism yet, as mentioned above.) I haven’t crunched the numbers on $Q_7$, but it’s probably 73 or 74.

Also related: this note. Though what we’re looking at here are largest induced forest subgraphs of hypercube graphs, not just trees. Probably not very different though.

Update: I went ahead and crunched numbers for $Q_7$ and $Q_8$; the orders of the largest induced subforests are 72 and 144, respectively. On the other hand, it’s ≤287 for $Q_9$. I’d have to generate a list of 143-vertex induced subforests of $Q_8$, and that sounds like it’d be large. This improves the lower bound of removal density from 7/16 to 225/512. Not a big increase by any measure, but it’s better than nothing!

## Hush

I was toying with the snub square tiling recently.

Actually, before that, I was playing with dodecagons. We see them pretty much daily on analogue clocks, but have you ever noticed that regular hexagons and dodecagons are the only ones that may be divided into other regular polygons? This isn’t actually hard to prove; consider the exterior angle of any regular polygon with such a property and evaluate the relevant inequalities.

The hexagon divides into six triangles, and the dodecagon divides into six triangles, six squares and a hexagon (or, in other words, twelve triangles and six squares).

There are three ways of attaching two triangles to a square. One of these three ways involves having the two triangles adjacent to each other. Let’s disregard that for now. This leaves two ways: attaching the two triangles on opposite edges of the square, or on adjacent edges.

How many ways can we cover a snub square tiling with these tiles? For the former, it turns out that after placing a tile, all the other tiles are forced. The result is a 3-colourable tiling where all tiles are in just two possible orientations. (There would be diagrams if I could’ve been bothered to learn how to draw them, but deal with the words.)

The latter actually has infinitely many tilings, I believe. Taking every other vertex, you either end up with a right isosceles triangle or an equilateral triangle. Furthermore, it can be treated as an equilateral triangle with two protrusions and one dent, and if you try to match up the protrusions and the dents, for six triangles arranged in a hexagon, you end up with a hexagon with six outwards protrusions—exactly a regular dodecahedron. (But this isn’t part of a snub square tiling, because the snub square tiling never has six triangles around a vertex.) Anyway…

We need some way of restricting the number of tilings we care about. If we restrict ourselves to the tile-transitive tilings, we end up with only two tilings, one of them 2-colourable (where the tiles are in only two possible orientations), and the other 3-colourable (where the tiles are in four possible orientations).

Derp, I figure this post is kinda pointless without pretty pictures. Oh well. Left as an exercise for the reader, etc.

## Low-hanging fruit

The principal value of $\zeta'(1)$ turns out to be $-\gamma_1$, so we can in fact manipulate the previous series into this, with the understanding that the principal value should be used.

$\displaystyle\sum_{k=0}^\infty\frac{\zeta'(2k+1)}{2k+1}=0$

& el tee semicolon hr slash & gee tee semicolon

I’ve been really, really, really burnt out recently. The new guy’s wrecking havoc all over the place and in the one day I took leave, he managed to mess my whole desk up.

Yeah, like, why was he even at my desk instead of the one he was assigned to?

Herp derp.

## More rainbows

I was playing with the limit for $\gamma_1$ again today, and came across a simpler series for it.

Watch this.

$\displaystyle\gamma_1=\sum_{k=1}^\infty\frac{\zeta'(2k+1)}{2k+1}$

Two bits per term, same as the slower of the two series in the previous post about this. Of course, it still has that pesky $\zeta'$ in it, which is kinda annoying to evaluate to high precision.

I initially got this by shifting $\log^2(n)$ into $\log^2\sqrt{n(n+1)}$ instead of $\log^2(n+1/2)$, with some of the terms cancelling out conveniently. Of course, if you work backwards from this instead, you find out that using $\log(n)\log(n+1)$ turns out to give this sum pretty much directly.

There are many ways of doing a “half-term shift”, and clearly they produce different and possibly interesting results. The earlier series may actually prove to be more efficient for computation as half as many $\zeta'$ evaluations would be needed for the same precision; $\zeta$ and the harmonic numbers are much easier to compute.