Half the chance for every silent set

When a press skips its own light changed one rule of the lights game. In the original, pressing a light toggles it and its neighbours; in the variant, it toggles the neighbours only. With that change, the theorem that every network can be lit stops holding, and the essay counted how often it fails. Of the 32,768 labelled networks on six vertices, 18,259 can be taken from all off to all on, a share of $0.557$; on seven vertices the share is $0.436$; and random networks to forty vertices keep alternating between about $0.56$ for even sizes and $0.44$ for odd. It explained the alternation — an adjacency matrix over the two-element field has even rank, so a network with an odd number of vertices always has a silent set — and left open where the two numbers themselves come from.

This essay computes them. The answer has two parts. The first is a chain: as a network grows one vertex at a time, the dimension of its space of silent sets goes up or down by exactly one at each step, with chances that depend only on the dimension, and that chain gives the law of the dimension exactly at every size. The second is a halving: a network with a $k$-dimensional space of silent sets can be lit about one time in $2^k$. Together they predict $0.560562$ and $0.439438$, the exact counts close in on the prediction vertex by vertex, and the two numbers add up to one.

Press everything #

Start with the simplest press pattern of all: press every vertex once. A press toggles the pressed vertex’s neighbours, so each vertex is toggled once for each of its neighbours, and it ends lit exactly when its number of neighbours, its degree, is odd. In the language of the matrix, pressing everything is applying the adjacency matrix $A$ to the all-ones vector, and the result, $A\mathbf 1$, is the vector of degrees taken mod 2.

That gives one class of networks for free. If every degree is odd, pressing everything lights everything, and the network is litable. On six vertices there are $2^{10} = 1{,}024$ labelled networks with all degrees odd, and every one of them can be lit, against $55.7$ per cent of networks in general. The right-hand network in the figure has four vertices of degree 2, and pressing everything lights only the two of degree 3, leaving the question of whether the four even-degree vertices can be lit some other way. That is the question in general: since pressing everything always lights the odd-degree vertices, a network is litable exactly when its even-degree vertices can be lit by themselves.

It also gives a class of networks that can never be lit. If every degree is even, then pressing everything changes nothing, $A\mathbf 1 = 0$, so the all-ones vector is itself a silent set. On an odd number of vertices it is a silent set of odd size, and the counting argument for silent sets says that is a certificate of failure: every press toggles an even number of lights inside a silent set, so an odd number of them can never all be on. So on seven vertices, every network whose degrees are all even — 32,768 of them, since such networks correspond to networks on six vertices — is unlitable.

Four small networks by hand #

The two rules already decide the smallest cases, and working them shows how much the degrees carry. The triangle has three vertices of degree two. Every degree is even and the number of vertices is odd, so the whole triangle is a silent set of odd size — pressing all three corners toggles each corner twice — and all on is unreachable. Indeed any press lights exactly the two other corners, and two presses either cancel or light a single corner and darken another; no combination ever has all three on.

The complete network on four vertices has every degree three, so pressing all four lights everything, at once. The star with one centre and three leaves has degrees three, one, one and one, all odd, so pressing all four vertices lights them all as well: the centre is toggled by each of three leaves and each leaf by the centre. The path on three vertices has degrees one, two and one. Pressing everything lights the two ends and leaves the middle dark, and the middle, of even degree, has to be lit separately: pressing one end toggles only the middle, so pressing all three and then that end again — that is, pressing the middle and the other end — lights the path. Its single silent set is the two ends together, which has an even number of members, as the rule requires.

So the degree parities are a first sorting of every network: all odd and it is certainly litable, all even on an odd number of vertices and it certainly is not, and otherwise the even-degree vertices must be reached by some pattern of presses. The boards on which every light goes out found the same kind of sorting on square grids, where the question was decided by the board’s dimensions; on a general network there is no such shortcut, and the sorting by degrees is where the probability takes over.

The even-degree vertices decide #

The next figure groups all the networks on six and seven vertices by how many vertices have odd degree, which is always an even number, since the degrees add up to twice the number of edges.

On six vertices, networks with no odd-degree vertex can be lit $0.425$ of the time, those with two or four odd-degree vertices $0.547$, and those with six, as shown, always. On seven vertices, networks with no odd-degree vertex can never be lit, and those with two, four or six can be lit $0.443$ of the time — the same share for all three groups, to every digit of the count. The equalities are exact: $0.425$ is $435/1{,}024$, which is also the share of litable networks on five vertices, and $0.547$ is the share on four. Those coincidences say that the families are related by correspondences that move a network between sizes, and the figure records them without supplying the correspondences. What it does establish is that the degree parities carry much of the answer, and that when they carry all of it — all odd, or on an odd number of vertices all even — the answer is certain.

A kernel that moves by one #

The rest of the answer is in the space of silent sets: the kernel of $A$ over the two-element field, the press patterns that change nothing. Its dimension $k$ is the number of independent silent sets, and $2^k$ is how many there are in all. A network is litable exactly when every one of them has an even number of members.

Build a random network one vertex at a time, each new vertex joined to each old one independently with chance one half — the model of the moment a giant appears at its densest setting, where every network on the given vertices is equally likely. Adding a vertex adds a new row and column to $A$, the column being the new vertex’s random set of neighbours. Two things can happen. If that column lies outside the space spanned by the old columns, the rank goes up by two — the new row comes with it — and the kernel dimension drops by one. If the column lies inside that space, the rank does not change, and the kernel dimension rises by one. The second case cannot add one to the rank, which is what would keep $k$ the same, because $A$ is alternating: for any vector $x$, $x^{\mathsf T} A x$ counts each edge inside $x$ twice and so is nought, and that forces the new diagonal entry to be consistent with the old columns. So $k$ moves by exactly one at every step, never staying put.

The chances are fixed by the dimension alone. The old column space has codimension $k$, so a uniformly random column lies inside it with chance $1/2^k$. So the dimension follows a Markov chain: from $k$ it moves to $k - 1$ with chance $1 - 1/2^k$ and to $k + 1$ with chance $1/2^k$, starting at $k = 1$ for a single vertex. The rule was checked directly, not just argued, on every way of adding a vertex to every network of up to five vertices, 33,866 additions, and in every one the dimension moved by exactly one. A chain that rises rarely from large $k$ and almost always from $k = 0$ settles quickly into a law that alternates with the parity of the size, as the time spent and the share held described for chains in general: at forty vertices the matrix is invertible with chance $0.4194$ and has a two-dimensional kernel with chance $0.5592$, and at forty-one the kernel is a single line with chance $0.8388$.

The chain against the networks #

The chain is a claim about every network at once, and it can be checked against the counts.

For six and seven vertices, where every network is counted, the shares agree with the chain’s law exactly, as fractions: the chain is not an approximation for random networks but a description of them. For the sampled sizes, 20 to 31 vertices, the shares agree within sampling error, and they are already indistinguishable from the limit. The law converges fast because the chain is strongly pulled towards small dimensions. A kernel of dimension four needs two unlikely rises in a row, at chances of a quarter and an eighth, and dimension six needs more; at forty vertices dimension six has chance $4 \times 10^{-5}$.

This is part of the classical theory of matrices over finite fields, in which the number of alternating matrices of each rank has long been known exactly, and the chain is the cleanest way to see it. Its consequence for the lights game is that the distribution of silent sets is known exactly at every size. What remains is the second part of the question: given a $k$-dimensional space of silent sets, how often are they all even?

Each dimension halves the chance #

If the all-ones vector sat in a random position relative to the kernel, each independent silent set would be even or odd by a fair coin, and all $k$ of them would be even with chance $1/2^k$. There is no reason in advance to expect that. The all-ones vector is not random — it is the vector the game is about — and the degree argument above shows it is tied to the matrix in specific ways. The next figure measures it.

It halves. Networks with an invertible matrix are always litable, since then every pattern can be reached. With a one-dimensional kernel the share is $0.496$ on seven vertices and $0.500$ on eleven, twenty-one and thirty-one; with two dimensions it is $0.253$ on twenty; with three, about $0.12$ to $0.13$ at every size sampled, against an eighth. The coupling between the all-ones vector and the kernel that the degrees create washes out: averaged over random networks of a given kernel dimension, the silent sets behave as though their parities were fair coins.

The prediction, and its two limits #

Multiplying the two parts gives a prediction for the share of litable networks at every size: the chance of each kernel dimension $k$ from the chain, times $1/2^k$, summed over $k$.

The prediction misses at the smallest sizes, where the degree constraints are strong: on two vertices it says $0.625$ and the truth is $0.5$; on three, $0.453$ against $0.375$. Then it closes in vertex by vertex, the gap $0.018$ at five vertices, $0.0069$ at six and $0.0044$ at seven, and from eight vertices on the sampled shares sit on it within their error. The limits are $0.560562$ for even sizes and $0.439438$ for odd ones, which are the numbers when a press skips its own light measured as about $0.56$ and $0.44$.

They add up to one, to the twelve decimal places the computation carries. The sum is a property of the chain rather than of the game — one step of the chain turns the even-size law into the odd-size law, and the two weighted sums come out complementary — and the figures check it numerically rather than derive it. In words, a large random network with an even number of vertices fails to be litable exactly as often as one with an odd number succeeds.

What the counts cannot show #

The chain is proved by the argument above and checked on every network to five vertices; its law at six and seven vertices agrees with the counts exactly. The halving is different. It is measured, on every network of seven vertices and on samples to thirty-one, and it holds within error at every size checked, but nothing here proves it. The figures show that the share of litable networks with a $k$-dimensional kernel is close to $1/2^k$; they do not show that it tends to $1/2^k$, and the exact counts at seven vertices — $0.496$, not $0.5$, for a one-dimensional kernel — show that it is not exact at finite sizes. A proof would need to show that the all-ones vector becomes asymptotically independent of the kernel, which is the precise form of the question the earlier essay left open.

The same caution applies to the limits. The two numbers $0.560562$ and $0.439438$ are the limits of the prediction; that the true shares converge to them depends on the halving holding in the limit. The samples agree to three decimal places at every size from eight to thirty-one, which is strong evidence and not a proof.

Still open: a reason for the halving #

The halving would follow if the all-ones vector were uniformly random relative to the kernel, and it is not; it is the vector whose image under $A$ is the degree vector, which is about as far from random as a vector can be. One route to a proof is through the degrees themselves. Pressing everything lights the odd-degree vertices, so litability is the question of whether the indicator of the even-degree vertices lies in the column space, and in a large random network that indicator is a random-looking set of about half the vertices whose dependence on the kernel might be controlled. Whether that can be made rigorous, and whether the resulting rate matches the gaps of $0.018$, $0.007$ and $0.004$ measured at five, six and seven vertices, is not settled here.

The structure the degree figure uncovered is open in a different way. That networks on six vertices with no odd-degree vertex are litable exactly as often as all networks on five, and networks on six with two odd-degree vertices exactly as often as all networks on four, are equalities of counts with no stated reason. They suggest a family of correspondences between networks of different sizes that preserve litability, and the cycles and the cuts, where the cycle and cut spaces of a network are exchanged by duality, is the kind of structure in which such correspondences usually live.

A chain and a coin #

The two numbers are now accounted for, with one assumption measured rather than proved. A network’s silent sets form a space whose dimension wanders up and down by one as vertices are added, almost always down from a large dimension and always up from nought, so that even-sized networks are usually invertible or have two independent silent sets, and odd-sized ones usually have exactly one. Each silent set is even or odd as though by a coin. An invertible network is always litable, a network with one silent set half the time, with two a quarter of the time, and the weighted average is $0.560562$ for even sizes and $0.439438$ for odd. The one rule that changed between the two lights games — whether a press toggles its own light — moved the share of litable networks from exactly one to these two numbers, and the matrix’s alternating structure is the whole of the reason.