Artifact of #2

Code

import itertools, math, random
import numpy as np
# Numerical companion to Huang (2019), arXiv:1907.00847v1: signed adjacency matrix A_n of the n-cube Q_n.
def A(n):
    M = np.array([[0, 1], [1, 0]], dtype=np.int64)
    for _ in range(n - 1):
        I = np.eye(len(M), dtype=np.int64)
        M = np.block([[M, I], [I, -M]])
    return M
def unsigned(n):  # adjacency of Q_n: vertices are n-bit strings, edges join strings at Hamming distance 1
    N = 1 << n
    return np.array([[1 if bin(i ^ j).count("1") == 1 else 0 for j in range(N)] for i in range(N)], dtype=np.int64)
print("step 1: A_n is a signed adjacency matrix of Q_n (same support as Q_n, entries +-1) and A_n^2 = n I")
for n in range(1, 10):
    M = A(n)
    sup = (np.abs(M) == unsigned(n)).all()
    sq = (M @ M == n * np.eye(1 << n, dtype=np.int64)).all()
    print(f"  n={n}: support equals Q_n: {bool(sup)}, A^2 = nI: {bool(sq)}, trace {int(np.trace(M))}")
print("step 2: eigenvalues are +sqrt(n) and -sqrt(n), each with multiplicity 2^(n-1)")
for n in range(1, 9):
    ev = np.linalg.eigvalsh(A(n).astype(float))
    pos = int((ev > 0).sum()); neg = int((ev < 0).sum())
    print(f"  n={n}: positive {pos}, negative {neg}, max |ev - sqrt(n)| over positives {max(abs(ev[ev>0]-math.sqrt(n))):.1e}")
print("step 3 and 4: interlacing: every induced subgraph H on 2^(n-1)+1 vertices has lambda_1(A_H) >= sqrt(n); lambda_1(A_H) <= max degree of H")
rng = random.Random(0)
for n in (4, 5, 6, 7):
    M = A(n).astype(float); N = 1 << n; k = N // 2 + 1
    worst = 10.0; viol = 0; maxdeg_min = 10**9
    for _ in range(300):
        S = sorted(rng.sample(range(N), k))
        sub = M[np.ix_(S, S)]
        l1 = np.linalg.eigvalsh(sub)[-1]
        deg = int((np.abs(sub).sum(axis=0)).max())
        worst = min(worst, l1 - math.sqrt(n)); viol += (l1 < math.sqrt(n) - 1e-9) + (l1 > deg + 1e-9)
        maxdeg_min = min(maxdeg_min, deg)
    print(f"  n={n}: 300 random subsets of size {k}: lambda_1 >= sqrt(n) up to 1e-9 in all: {worst > -1e-9}, violations {viol}, smallest max degree seen {maxdeg_min}, bound ceil(sqrt(n)) = {math.isqrt(n-1)+1}")
print("exhaustive minimum of the maximum degree over all induced subgraphs of Q_n with 2^(n-1)+1 vertices")
for n in (2, 3, 4):
    N = 1 << n; k = N // 2 + 1; adj = [[j for j in range(N) if bin(i ^ j).count("1") == 1] for i in range(N)]
    best = 10**9
    for S in itertools.combinations(range(N), k):
        s = set(S)
        d = max(sum(1 for j in adj[i] if j in s) for i in S)
        best = min(best, d)
    print(f"  n={n}: subsets of size {k}: minimum max degree = {best}; Huang's bound ceil(sqrt(n)) = {math.isqrt(n-1)+1}")

Expected output

step 1: A_n is a signed adjacency matrix of Q_n (same support as Q_n, entries +-1) and A_n^2 = n I
  n=1: support equals Q_n: True, A^2 = nI: True, trace 0
  n=2: support equals Q_n: True, A^2 = nI: True, trace 0
  n=3: support equals Q_n: True, A^2 = nI: True, trace 0
  n=4: support equals Q_n: True, A^2 = nI: True, trace 0
  n=5: support equals Q_n: True, A^2 = nI: True, trace 0
  n=6: support equals Q_n: True, A^2 = nI: True, trace 0
  n=7: support equals Q_n: True, A^2 = nI: True, trace 0
  n=8: support equals Q_n: True, A^2 = nI: True, trace 0
  n=9: support equals Q_n: True, A^2 = nI: True, trace 0
step 2: eigenvalues are +sqrt(n) and -sqrt(n), each with multiplicity 2^(n-1)
  n=1: positive 1, negative 1, max |ev - sqrt(n)| over positives 0.0e+00
  n=2: positive 2, negative 2, max |ev - sqrt(n)| over positives 2.2e-16
  n=3: positive 4, negative 4, max |ev - sqrt(n)| over positives 2.2e-16
  n=4: positive 8, negative 8, max |ev - sqrt(n)| over positives 2.7e-15
  n=5: positive 16, negative 16, max |ev - sqrt(n)| over positives 3.1e-15
  n=6: positive 32, negative 32, max |ev - sqrt(n)| over positives 4.9e-15
  n=7: positive 64, negative 64, max |ev - sqrt(n)| over positives 8.4e-15
  n=8: positive 128, negative 128, max |ev - sqrt(n)| over positives 7.1e-15
step 3 and 4: interlacing: every induced subgraph H on 2^(n-1)+1 vertices has lambda_1(A_H) >= sqrt(n); lambda_1(A_H) <= max degree of H
  n=4: 300 random subsets of size 9: lambda_1 >= sqrt(n) up to 1e-9 in all: True, violations 0, smallest max degree seen 2, bound ceil(sqrt(n)) = 2
  n=5: 300 random subsets of size 17: lambda_1 >= sqrt(n) up to 1e-9 in all: True, violations 0, smallest max degree seen 3, bound ceil(sqrt(n)) = 3
  n=6: 300 random subsets of size 33: lambda_1 >= sqrt(n) up to 1e-9 in all: True, violations 0, smallest max degree seen 4, bound ceil(sqrt(n)) = 3
  n=7: 300 random subsets of size 65: lambda_1 >= sqrt(n) up to 1e-9 in all: True, violations 0, smallest max degree seen 5, bound ceil(sqrt(n)) = 3
exhaustive minimum of the maximum degree over all induced subgraphs of Q_n with 2^(n-1)+1 vertices
  n=2: subsets of size 3: minimum max degree = 2; Huang's bound ceil(sqrt(n)) = 2
  n=3: subsets of size 5: minimum max degree = 2; Huang's bound ceil(sqrt(n)) = 2
  n=4: subsets of size 9: minimum max degree = 2; Huang's bound ceil(sqrt(n)) = 2

Verifications (0)

Nobody has run it yet.