# OK to post homework
# Robert Dougherty-Bliss
# 2021-04-11
# Assignment 21

# I have read Knuth's adaptation of Huang's proof - it is quite amazing how
# simple it is!

# The gist of the argument:

#   1. Construct a matrix A such that abs(A) is the adjacency matrix of your
#      graph with N vertices, and let H be a set of s vertices.

#   2. Cleverly construct another matrix B with > N - s columns such that
#               AB = cB
#      for some desired constant c.

# And that's it! Once you have these matrices, then it follows from Knuth's
# argument that some element of H has >= c neighbors in H.

# I tried to replicate this idea for the {0, 1, 2}-cube, but the identites
# become more complicated. Here was my attempt:

(*

    Take

                [A(n - 1);  I(n - 1);     0   ]
        A(n) =  [I(n - 1); -A(n - 1); I(n - 1)]
                [    0   ;  I(n - 1); A(n - 1)].

    I believe that abs(A(n)) is the adjacency matrix for the {0, 1, 2} cube in
    n-dimensions.

    A(n)^2 satisfies a niceish identity, so this is part 1.

    What should we do for part 2? That has me stumped.

*)

# 2.

IntegerToVec := proc(k, n)
    local bits,x:
    bits := []:

    x := k - 1:
    while x >= 1 do
        if x mod 2 = 1 then
            bits := [1, op(bits)]:
            x := x - 1:
        else
            bits := [0, op(bits)]:
        fi:

        x := x / 2:
    od:

    [0 $ (n - nops(bits)), op(bits)]:
end:

VecToInteger := proc(v, n)
    1 + add(2^(n - k) * v[k], k=1..n):
end:

# 3.

read "C20.txt":
read "C21.txt":
FindAlpha := proc(H, n)
    y := Findy(n, H):

    maxes := []:
    max := -infinity:

    for k from 1 to nops(y) do
        val := y[k]:
        if evalf(abs(val)) > evalf(max) then
            max := abs(val):
            maxes := [k]:
        elif abs(val) = max then
            maxes := [op(maxes), k]:
        fi:
    od:

    # (I don't think that Knuth's argument shows that the neighbors of alpha
    # will ONLY be in H, just that at least sqrt(n) of them will be.)

    Hv := {seq(IntegerToVec(v, n), v in H)}:
    elemsv := {seq(IntegerToVec(v, n), v in maxes)}:
    if ormap(v -> Nei(H, v) < evalf(sqrt(n)), elemsv) then
        return FAIL:
    fi:

    maxes:
end:

# These functions are a little confusing because it isn't easy to see what the
# neighbors of an arbitrary integer should be.

for k from 1 to 10 do
    H := randcomb([seq(1..2^5)], 2^4 + 1);
    FindAlpha(H, 5);
od;