;colours

Blah blah blah chromatic numbers of graphs.

This one isn’t too hard to prove. Given a -colouring of , group the vertices by colour, then since the vertices with the same colour induce a null subgraph of (correspondingly, a complete subgraph of ), is at least the size of the largest group of vertices, which is necessarily at least .

This follows from the above and the arithmetic-geometric mean inequality.

This isn’t too hard to prove with induction, but >induction. Proof later.

This follows from the above and the arithmetic-geometric mean inequality, again.

Back to trying to prove that. But then we’d need a digression first. This came up as an optional question for a graph theory assignment last year, and it was pretty much the killer question. I didn’t think of using induction then for whatever reason, and resorted to the power of the internet to get an answer. (Damn if I leave it blank.) I don’t actually recall much of the proof (neither did I understand much of it back then), but I recall finding it in some PDF file under a header ‘Some Slick Proofs’. I was like ‘screw it imma submit this’ (>me >actually doing homework), and so I did. And then Mr Lee Chan Lye (putting the full name here despite having done so for approximately one other teacher, because there’s a high chance I won’t remember anyone from school after a while) was like ‘you can also prove this using induction’. Story time over.

Lemma: Let be any graph with at least one vertex. Let . Then .
Proof: Clearly , since any -colouring applied to is still a valid colouring. By taking any -colouring, and assigning a new colour, a -colouring for is obtained, so and . ∎

Let be the proposition “ for all such that “. is trivially true, since both and are 0. Suppose that is true for some . For the purposes of coming to a contradiction later, assume that is false. There then exists a graph with such that .

Let . This is reminding me of /vg/ for obvious reasons. Then is a graph of k vertices, to which the proposition applies: . Applying the power of subtraction, . However, by applying the lemma, we also have . From these:

and
.

is necessarily at least since otherwise , where choosing one of the colours not used for any vertex in leads to a -colouring. Similarly, . Add these two inequalities to get . However, since , this leads to the absurd conclusion that , hence for any , so by induction the proposition is true for all nonnegative integers. ∎

Trying to adapt this back for the first statement in the start of the blog post doesn’t seem to work too well, since it leads to the pair of statements and , which are not by themselves false. Example: let and . , and for any choice of .

Anyway. Time for a completely unrelated graph theory finding observation. Let be a graph with vertex set (where is an ordered pair) and two vertices being adjacent iff they have either the i-coordinate the same and j-coordinate differing by one (modulo 4, where 0 and 3 can be considered to differ by one), or j-coordinate the same and i-coordinate differing by one (again, mod 4). Appealing more towards a graphic visualisation, a 4-by-4 square lattice graph with edges wrapped. (See pics that I can’t upload here because >SVG.)

This graph happens to be isomorphic to the hypercube graph , and allows consideration of the 4-cube’s symmetries as automorphisms of the graph. The six squares around a point are fairly obvious when the graph is drawn normally, but when drawn as a grid, two of the six squares (the ones that wrap across the boundary) are less obvious, but still existent, of course.

It’s possible to label the vertices on a 4-cube such that each axis gets assigned a power of two from 1 to 8, resulting in a numbering of vertices from 0 to 15, where adjacent vertices differ by one bit in their binary representation. By sheer coincidence, by removing all the points divisible by 3, one obtains a graph with no cycles… which happens to be the only way of removing 6 vertices from to obtain a forest (up to symmetry; there are 8 ways total, as mentioned two years ago). Of course, I’ve already proven that that was the only way of removing 6 vertices to obtain a forest years back, but representing it as a 4-by-4 grid that wraps makes a lot of the symmetries more obvious (you get 16 from translation, multiply by 4 for rotation, and 2 again for reflection (which covers 128 of the 384 symmetries); contrast the typical drawing as a regular octagon, which only has 8 from rotation, multiplied by 2 for reflection).

What’s this

I had an idea in mind for a blog post (which as you can see happens very rarely nowadays) but got interrupted by being forced to evict my room.

As you may know, I’m now participating in compulsory slave labour for the country. If you didn’t, now you know. I don’t like the experience there.

Let’s see. I’m not supposed to talk about what goes on in there. Oh wait, I’m not even supposed to divulge that I’m not supposed to talk about what goes on in there. In other words, no :blogging: about that shit. How boring, except I don’t really have much to say about that.

Recently (okay, this news is rather outdated now because of my permanent temporary chronic acute blogging hiatus), Katawa Shoujo was released. Despite the obviously Japanese name, it’s a visual novel / dating sim made by weeaboos, where the premise is that the protagonist goes to a school for disabled people.

That’s pretty much exactly like where I’m at in the slave labour camp. Except there’s a significant proportion of aspies which don’t exist in Katawa Shoujo, and there are only males. How utterly boring.

THIS BLOG POST BROUGHT TO YOU BY TEN INTERRUPTIONS OVER THE SPAN OF TIME I TRIED TO WRITE IT. I HATE EVERYBODY I LIVE WITH.

Ammonia

TAKE YOUR SHITTY ARGUMENTS ELSEWHERE I DON’T WANT TO LISTEN TO YOU‒ well scratch that there are some people I have to want to listen to even if they infuriate me much.

I’d like to point out a certain flaw about the word “want” as used in common speech. At the very basic level you have the “I want to do this because it makes me happy” kind of “want”. That’s a “want” I believe everybody can consider a real “want”. The ambiguity comes in at somewhat more complex types of “want”s, like a “doing this lets me not suffer” kind of “want”. It’s debatable whether that counts as a “need” or a “want”. And then you have a “doing this makes me suffer now but is better in the long run” kind of “want”. Is that a “want”? A “need”?

And then, by necessity any action that has already been done was “wanted”, even if they’re now undesirable (with new information, or simply bipolarity). If it weren’t wanted, that means there wasn’t a “want” to do the action, ergo the action would not have been done.

You have varying levels of “want”. There’s a “I want this, but only if I don’t have to pay for it”, and then there’s an attachment to the amount to pay (“I want this, only if I have to pay less than “), and the next step up is “I want this and I’ll use whatever I can to get it”. Note that what’s being paid might not necessarily be money, but other things human subjects attach value to (those with sentimental value, for example). And while the latter two “want”s are quite clearly true “want”s in the layman (read: inexact) definition of “want”, they’d fall under the third type of “want” in the second paragraph. Which is highly debatable.

Anyway back to main topic which is ranting about my life and why I hate everything (except you, I love you guys (maximum homo if you’re male, maximum hetero if you’re female)).

Ever since I learnt of the concept of not consuming dinner at the dining table, I’ve had a habit of taking my bowl to wherever else to consume the stuff inside the bowl (which I hesitate to call food at times). Or well, not so much a habit as something I had the capability of doing and actually did. The “adults” I live with (I realise I can’t use that to refer to everybody else anymore because I’m legal now, but screw that) seem to have a pretty gigantic issue with that though, especially recently. Well yes of course I can’t tell them I’m busy putting subtitles on Japanese cartoons (illegally, even) and expect them to be fine with it, but it’s not like I take my bowl off to my room every day.

Heck, I don’t think I’ve even been doing that the past few days before today.

>2012

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

My good

If you weren’t living in a cave you should know that I’ve been fairly interested in random number generators. Not just the pseudo- kind, of course, but I can’t really do much research about real RNGs without some proper funding. And sufficient motivation, because data collection is tedious. (The real reason is more like because I’m really clumsy with objects, and handling a hardware RNG so much probably isn’t going to make it last long.)

I recently torrented TAOCP (feeling guilt, will buy the book another time), just for volume 2 actually, because Seminumerical Algorithms. Which contains a chapter on pseudorandom number generators. It’s fairly interesting, but the age of the book precludes inclusion of more recent (but still rather dated) algorithms like ISAAC, but I’m pretty fine with just studying about simpler RNGs (by which I actually mean PRNG, but that’s an extra letter) if that means I get more solid (instead of empirical) results.

Summarising from the book, a sequence can be defined as random if every string of every length appears with the same probability. Hold on, this sounds just like the definition of normality… yeah. There’s actually a hardly-known RNG that uses the digits of a proven-to-be-normal-in-binary number, with the seed being where the digit reading starts. But there are simpler normal numbers. Considering for now just normality in base 2, a binary analogue of the Champernowne constant, could theoretically function as a perfect random number generator, but the obvious flaw is obvious:

The seed is essentially the random number itself. In other words, this is effectively like using a very large random number table. Sure, it’s random, but only asymptotically; it’s impossible to have a uniform distribution over the nonnegative integers, so there’ll inherently be some bias, and therefore predictability given sufficiently many digits of output, by autocorrelating and stuff.

(Last edited on February 24, 2011 at 2:08 pm. DRAFT QUEUE CLEARING.)

Passwords

I think I’ve got one post on the old blog about a new password scheme. I haven’t really thought much of it since then, but considering how often passwords are getting leaked nowadays this is kinda important. You should already know I use a dictionary password. I don’t really give a shit because there’s nothing to my name and therefore there’s nothing to lose. That’s what I say now, but I think I’ll shit bricks if any of my accounts get broken into. (Figuratively of course.)

I currently can’t be arsed to find the old post, and I don’t really remember what’s in it because it’s been so damn long since I wrote it, so I’ll just go by memory. Currently, if you’re trying to log in to a web site you’ll have to give the web site your password. HTTPS provides authentication and encryption, so there isn’t much problem, until you realise that many sites also require your email address to sign up, and if you’re a lazy piece of shit you’ll probably be using the same password for both accounts, and the site you just signed up for can use that password to access your email.

Of course, being lazy, you want to use the same password everywhere, or something to that effect. What do you do? One way is to keep a file with proper cryptographically random passwords, and encrypt that with your favourite insecure password. Programs exist that do this for you. It’s still a suboptimal solution though, because you have to keep that file. It’s kind of like the issue I have with Bitcoins. Generally I don’t bother with backups (hurr durr), but these are actually worth something more valuable than my time. Also, those crypto-random passwords are completely unrelated to the master password, so if you lose the file somehow you lose everything.

Currently passwords are usually stored salted and hashed on the server (note: depending on how not-retarded the person coding the server is, this may or may not be the case)

(Last edited on July 19, 2011 at 12:10 pm. DRAFT QUEUE CLEARING.)

Let me laugh harder

Here be the Archive Team’s take on file formats. (Nope, not going to copy that. Chances are, WordPress.com will go down before AT does, and that’s a long time in the future.)

I find it pretty ridiculous. Archive Team, of all people, suggesting plain text, and PNG and SVG on the same page? Along with Ogg (presumably Vorbis) and AVI? I call bullshit. Plain text is an understandable choice, because even if a file was sent to an alien civilisation, with reference to real written/printed text, it’s very possible (and not hard) to decipher it using frequency analysis. (Assuming English, of course.) As for pictures, Windows bitmap and PNM look like the best candidates, for obvious reasons; these are again easily reverse engineered. (Well, BMP not so much because of all the random headers, but generally they’re unimportant.)

Now, Gzip (and compression formats in general) is something that cannot be reverse engineered easily. How many compression formats are in common use today? There’s Gzip, Bzip2, Zip, 7z, Xz, RAR and maybe a bunch of slightly more niche formats. There’s no way to define the “best” one to use for everything: Gzip has low encode/decode requirements, but isn’t supported by default on Windows (lol). Bzip2 compresses well, but isn’t supported on Windows either. Xz has even better compression, but again isn’t supported on Windows, not to mention Xz is actually pretty niche and apart from a certain free software distributor (lolgnu) nobody ever seems to use it. Zip is supported almost everywhere, and is kind of the de facto standard, except that this standard magically evolves over time. Support for encryption and non-Deflate compression algorithms (including Wavpack, even) were just added in relatively recently. 7z is… well, some people use it. As for RAR, lolderp.

The only time-proof compression format is to have none at all. This is feasible for text, pictures and audio, but video… that’s hard. One hour of 24 fps 1920×1080 4:2:0 8-bit video already takes up ~75 MB per second, or ~268 GB per hour.

(Last edited on September 9, 2011 at 8:53 pm. DRAFT QUEUE CLEARING. Also this post is at least partially factually inaccurate, iirc, which was the reason I didn’t finish it.)

Queues

I believe there was a post titled “Cues” not too long ago. Well that was a post about me ranting about shit, and just two posts back I mentioned I keep private stuff private, which is the only reason I decided to slap password protection on it. It’s important k. Anyway, back to queues.

It’s not too uncommon to encounter a situation where multiple people are trying to use a resource that can only be used by at most one person at any time, and normally different people will hog the resource for a differing amounts of times (but assume it’s constant regardless of whatever position in the queue they’re in). Now suppose how pissed off (because everyone wants to be first) a person is roughly proportional to the ratio of the waiting time to the execution time, and you want to minimise the overall pissed-off-ness of everybody. (Theoretically, optimising this would be roughly equivalent to having the wait:execution ratio the same for everybody.)

First-come-first-serve is the general strategy used in real life. It also sucks. Without a context regarding the order, this isn’t any different from a random ordering.

Another one that comes to mind is to just sort, and have people with faster tasks be earlier in the queue. This unfortunately leads to a problem where if more people with fast tasks join the queue as the resource is being used, the slowest task never gets done. It also violates the

(Last edited on September 17, 2011 at 1:45 am. DRAFT QUEUE CLEARING. I also have no idea how I was going to finish that sentence.)

Web browsers have horrible download managers

Yeah, it’s not really like we should be expecting a complete download manager in web browsers, but holy shit they suck. IE’s is the most fabulous. By that I mean worst. If I’m not mistaken it’s still using that ancient interface of showing a pop-up then querying a download location, and giving some retarded-looking progress bar if you use Windows 7. (Herp, did anyone actually think Windows 7′s progress bar looks nice? Seriously, it looks horrible.) It’s horrible, because that’s all it can do. It’s the bare minimum a download manager can offer— wait, you can’t really call that a “manager”, if all it does it download. IE is the most deficient in this regard, assuming I’m not subconsciously biasing against it from memory (because I don’t actually use it).

Chrome’s is somewhat derpy. The way downloads are initiated is stupid, to begin with, and while that’s not technically part of the download manager, it affects the downloading process, so I shall describe it. Apparently, what Chrome does is if it encounters something with an unknown type (using MIME, presumably), it’ll treat that file as something to be downloaded, and automatically download it unless you change some setting. It’s dumb, because this can also happen when a server running PHP momentarily derps up and doesn’t set the MIME type or something, leaving the browser to extrapolate type information from the extension (which for the purposes of this example is assumed to be “.php”). And then it leads to magical clutter of the downloads folder with random HTML files with a .php extension that seemingly came out of nowhere, from the point of view of the user. Of course, that’s not the only cause; generally, random server derps can cause Chrome to download all sorts of things. And I believe it should even be possible for a (malicious) server to force Chrome to download random junk, with the only indication being the download bar at the bottom (which is pretty obvious, unless such an attack uses small files that download quickly, but that wouldn’t do much harm).

Now on to the actual download manager. Like the rest of the main Chrome interface, it’s rather minimalistic. But it’s an actual manager in the sense that it can handle more than one download in the same interface. And it even allows pausing and resuming downloads (depending on whether the server allows it, of course)! Yeah, but that’s all there is to it. Now, if you try to cancel a partial download, it’ll delete the file. It makes sense, given that Chrome is retarded enough to automatically download everything. With Firefox this is different, but wait for that.

If I remember correctly the last time Firefox’s download manager interface changed significantly was from the 2.0 → 3.0 transition. (And that was a long time ago.) Unlike Chrome, Firefox’s download manager goes in a separate window.

And then at this point I got sufficiently distracted while writing this post. To be continued. (Posting it publicly first to prevent it from getting stuck in the draft queue (23 posts and counting) forever.)

(Last edited on October 9, 2011 at 2:06 am. DRAFT QUEUE CLEARING.)

Weekly opinion blog post

Oh great just as I type out the title I forget what I was going to rant about.

Anyway, just going to rant about something (else).

Gigantic TV screens are a dumb idea. For that matter, I also hate the standard 16:9 aspect ratio. It’s unnecessarily complicated; while 9 and 16 are both nice square numbers, the ratio deviates too much from being square, or even √2. (Lol HTML sqrt tags, haven’t done those in a while.) I don’t see any benefits to using 16:9 (in landscape) over 8:5 (also known as 16:10 by people too stupid to divide by two).

(Last edited on October 26, 2011 at 7:47 pm. DRAFT QUEUE CLEARING.)