Find the largest independent set in a high-dimensional lattice-like graph For a given positive integer n, consider all binary strings of length 2n-1.  For a given string S, let L be an array of length n which contains the count of the number of 1s in each substring of length n of S. For example, if n=3 and S = 01010 then L=[1,2,1]. We call L the counting array of S.

We say that two strings S1 and S2 of the same length match if their respective counting arrays L1 and L2 have the property that L1[i] &lt;= 2*L2[i] and L2[i] &lt;= 2*L1[i] for all i. 

Task

For increasing n starting at n=1, the task is to find the size of the largest set of strings, each of length 2n-1 so that no two strings match.   

Your code should output one number per value of n.

Score

Your score is the highest n for which no one else has posted a higher correct answer for any of your answers.  Clearly if you have all optimum answers then you will get the score for the highest n you post. However, even if your answer is not the optimum, you can still get the score if no one else can beat it.  

Example answers

For n=1,2,3,4 I get 2,4,10,16.

Languages and libraries

You can use any available language and libraries you like. Where feasible, it would be good to be able to run your code so please include a full explanation for how to run/compile your code in linux if at all possible.

Leading entries


5 by Martin Büttner in Mathematica
6 by Reto Koradi in C++. Values are 2, 4, 10, 16, 31, 47, 75, 111, 164, 232, 328, 445, 606, 814, 1086.  The first 5 are known to be optimal. 
7 by  Peter Taylor in Java. Values are  2, 4, 10, 16, 31, 47, 76, 111, 166, 235.   
9 by joriki in Java. Values are 2, 4, 10, 16, 31, 47, 76, 112, 168.
2, 4, 10, 16, 31, 47, 76, 111, 166, 235

Notes

If we consider a graph G with vertices 0 to n and edges joining two numbers which match, then the tensor power G^n has vertices (x_0, ..., x_{n-1}) forming the Cartesian power {0, ..., n}^n and edges between matching tuples. The graph of interest is the subgraph of G^n induced by those vertices which correspond to the possible "counting arrays".

So the first subtask is to generate those vertices. The naïve approach enumerates over 2^{2n-1} strings, or on the order of 4^n. But if we instead look at the array of first differences of the counting arrays we find that there are only 3^n possibilities, and from the first differences we can deduce the range of possible initial values by requiring that no element in the zeroth differences is less than 0 or greater than n.

We then want to find the maximum independent set. I'm using one theorem and two heuristics:


Theorem: the maximum independent set of a disjoint union of graphs is the union of their maximum independent sets. So if we break a graph down into unconnected components we can simplify the problem.
Heuristic: assume that (n, n, ..., n) will be in a maximum independent set. There's a fairly large clique of vertices {m, m+1, ..., n}^n where m is the smallest integer which matches n; (n, n, ..., n) is guaranteed to have no matches outside that clique.
Heuristic: take the greedy approach of selecting the vertex of lowest degree.


On my computer this finds 111 for n=8 in 16 seconds, 166 for n=9 in about 8 minutes, and 235 for n=10 in about 2 hours.

Code

Save as PPCG54354.java, compile as javac PPCG54354.java, and run as java PPCG54354.

import java.util.*;

public class PPCG54354 {
    public static void main(String[] args) {
        for (int n = 1; n &lt; 20; n++) {
            long start = System.nanoTime();

            Set&lt;Vertex&gt; constructive = new HashSet&lt;Vertex&gt;();
            for (int i = 0; i &lt; (int)Math.pow(3, n-1); i++) {
                int min = 0, max = 1, diffs[] = new int[n-1];
                for (int j = i, k = 0; k &lt; n-1; j /= 3, k++) {
                    int delta = (j % 3) - 1;
                    if (delta == -1) min++;
                    if (delta != 1) max++;
                    diffs[k] = delta;
                }

                for (; min &lt;= max; min++) constructive.add(new Vertex(min, diffs));
            }

            // Heuristic: favour (n, n, ..., n)
            Vertex max = new Vertex(n, new int[n-1]);
            Iterator&lt;Vertex&gt; it = constructive.iterator();
            while (it.hasNext()) {
                Vertex v = it.next();
                if (v.matches(max) &amp;&amp; !v.equals(max)) it.remove();
            }

            Set&lt;Vertex&gt; ind = independentSet(constructive, n);
            System.out.println(ind.size() + " after " + ((System.nanoTime() - start) / 1000000000L) + " secs");
        }
    }

    private static Set&lt;Vertex&gt; independentSet(Set&lt;Vertex&gt; vertices, int dim) {
        if (vertices.size() &lt; 2) return vertices;

        for (int idx = 0; idx &lt; dim; idx++) {
            Set&lt;Set&lt;Vertex&gt;&gt; p = connectedComponents(vertices, idx);
            if (p.size() &gt; 1) {
                Set&lt;Vertex&gt; ind = new HashSet&lt;Vertex&gt;();
                for (Set&lt;Vertex&gt; part : connectedComponents(vertices, idx)) {
                    ind.addAll(independentSet(part, dim));
                }
                return ind;
            }
        }

        // Greedy
        int minMatches = Integer.MAX_VALUE;
        Vertex minV = null;
        for (Vertex v0 : vertices) {
            int numMatches = 0;
            for (Vertex vi : vertices) if (v0.matches(vi)) numMatches++;
            if (numMatches &lt; minMatches) {
                minMatches = numMatches;
                minV = v0;
            }
        }

        Set&lt;Vertex&gt; nonmatch = new HashSet&lt;Vertex&gt;();
        for (Vertex vi : vertices) if (!minV.matches(vi)) nonmatch.add(vi);
        Set&lt;Vertex&gt; ind = independentSet(nonmatch, dim);
        ind.add(minV);
        return ind;
    }

    // Separates out a set of vertices which form connected components when projected into the idx axis.
    private static Set&lt;Set&lt;Vertex&gt;&gt; connectedComponents(Set&lt;Vertex&gt; vertices, final int idx) {
        List&lt;Vertex&gt; sorted = new ArrayList&lt;Vertex&gt;(vertices);
        Collections.sort(sorted, new Comparator&lt;Vertex&gt;() {
                public int compare(Vertex a, Vertex b) {
                    return a.x[idx] - b.x[idx];
                }
            });

        Set&lt;Set&lt;Vertex&gt;&gt; connectedComponents = new HashSet&lt;Set&lt;Vertex&gt;&gt;();
        Set&lt;Vertex&gt; current = new HashSet&lt;Vertex&gt;();
        int currentVal = 0;
        for (Vertex v : sorted) {
            if (!match(currentVal, v.x[idx]) &amp;&amp; !current.isEmpty()) {
                connectedComponents.add(current);
                current = new HashSet&lt;Vertex&gt;();
            }

            current.add(v);
            currentVal = v.x[idx];
        }

        if (!current.isEmpty()) connectedComponents.add(current);
        return connectedComponents;
    }

    private static boolean match(int a, int b) {
        return a &lt;= 2 * b &amp;&amp; b &lt;= 2 * a;
    }

    private static class Vertex {
        final int[] x;
        private final int h;

        Vertex(int[] x) {
            this.x = x.clone();

            int _h = 0;
            for (int xi : x) _h = _h * 37 + xi;
            h = _h;
        }

        Vertex(int x0, int[] diffs) {
            x = new int[diffs.length + 1];
            x[0] = x0;
            for (int i = 0; i &lt; diffs.length; i++) x[i+1] = x[i] + diffs[i];

            int _h = 0;
            for (int xi : x) _h = _h * 37 + xi;
            h = _h;
        }

        public boolean matches(Vertex v) {
            if (v == this) return true;
            if (x.length != v.x.length) throw new IllegalArgumentException("v");
            for (int i = 0; i &lt; x.length; i++) {
                if (!match(x[i], v.x[i])) return false;
            }
            return true;
        }

        @Override
        public int hashCode() {
            return h;
        }

        @Override
        public boolean equals(Object obj) {
            return (obj instanceof Vertex) &amp;&amp; equals((Vertex)obj);
        }

        public boolean equals(Vertex v) {
            if (v == this) return true;
            if (x.length != v.x.length) return false;
            for (int i = 0; i &lt; x.length; i++) {
                if (x[i] != v.x[i]) return false;
            }
            return true;
        }

        @Override
        public String toString() {
            if (x.length == 0) return "e";

            StringBuilder sb = new StringBuilder(x.length);
            for (int xi : x) sb.append(xi &lt; 10 ? (char)('0' + xi) : (char)('A' + xi - 10));
            return sb.toString();
        }
    }
}