Find the largest independent set in a high-dimensional lattice-like graph
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();
        }
    }
}