Procrastination and subcubes

Looks like there's potential for internet disruption on April 1. It's probably not going to amount to much, but since the FOCS deadline is April 2, you may want to have a version of the paper into the system ahead of time just in case. Actually, ignore the malware; you shouldn't need a reason like that to aim ahead of the deadline, it's just a good idea regardless.

On a not-very-closely-related subject, this weekend I was thinking about intersection graphs of \( k \)-dimensional faces of hypercubes. In an n-dimensional hypercube there are \( \tbinom{n}{k}2^{n-k} \) \( k \)-faces; they can be represented as strings of n characters k of which are stars and the rest of which are 0's and 1's. The faces of a hypercube (interpreted as sets of vertices) have the Helly property — if a collection of strings of 0's, 1's, and *'s match each other pairwise, there is a string of 0's and 1's that they all match — so the cliques just consist of sets of \( k \)-faces sharing a common hypercube vertex; therefore, the clique number of these graphs is (n choose k). An independent set in the graph is just a set of disjoint \( k \)-faces; by double counting the vertices per face and faces per vertex it's easy to see that the independence number is \( 2^{n-k} \). The chromatic number is \( \tbinom{n}{k} \): it is at least the clique number, and partitioning faces into groups of parallel faces produces a coloring with this many colors. When one sees chromatic number equal to clique number, one should think perfect graphs, and these graphs are perfect when \( k=1 \) (the line graphs of hypercubes, like other line graphs of bipartite graphs, are perfect) but not in general.

Here's a drawing of one of these graphs, the intersection graph of the 1-dimensional faces (that is edges) of a three-dimensional cube.

Why should one care about cliques and independent sets and colorings of these graphs, if one is a theoretical computer scientist? Because the induced subgraphs of these intersection graphs come up in the theory of probabilitically checkable proofs. If the vertices of a hypercube represent bitstrings (and are interpreted as proofs) a \( k \)-face of the graph represents a proof checker that looks at \( n-k \) bits of a probabilistically checkable proof, doesn't look at the other \( k \) bits, and has to decide whether to accept or reject the proof based on what it sees. The graph induced by the checkers that accept what they see has a big clique if there's a valid proof, consisting of the checkers whose faces include the corresponding hypercube vertex, and has no big cliques otherwise (because in this case all proofs are invalid and all cliques have few accepting checkers). This basic idea, of a connection between proof checkers and cliques, comes from a 1996 JACM paper by Feige et al and has been used by many papers since, most recently Zuckerman, to show that clique-finding is hard.

But if the intersection graphs of subcubes were perfect, so would be their induced subgraphs arising from this reduction. And since clique numbers of perfect graphs can be computed in polynomial time, it would be possible to use this idea to prove \( \mathsf{P}=\mathsf{NP} \). So it's either good news or bad that these graphs aren't perfect: it's bad news because it prevents the proof of an amazing result, but it's good news because if it were true it would put a lot of complexity theorists out of work.

Comments: