# OK to post homework # Aurora Hiveley, 2/27/25, Assignment 11 Help := proc(): print(`IndNu(G), UpperBoundMinMaxNN(G,r,K)`): end: with(combinat): with(linalg): # verify that indeed An*Bn=sqrt(n)*Bn for small n. # How far were you able to go with in a reasonable amount of time? # n := 3: # A := An(n): B := Bn(n): # evalb(Mul(A,B) = expand(sqrt(n)*B)); # made it up to n = 9 with computation times under 1 minute. # n=10 was longer, time() reported that it took 182 seconds (3 mins) # IndNu(G): finds the independence number of a graph G=[n,E] # the independence number of G is the largest r such that MinMaxNN(G,r) is 0 # uses MinMaxNNpablo(G,r) IndNu := proc(G) local n,r: n := G[1]: r := n: while r > 0 do if MinMaxNNpablo(G,r) = 0 then RETURN(r): fi: r--: od: 0: end: # [seq(IndNu(Gnd(n,2)), n=3..15)]; # output: [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5] # n = 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14,15 # [seq(IndNu(Gnd(n,3)), n=4..15)]; # can't use n=3 for a 3 regular graph! # output: [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3] # n = 4, 5, 6, 7, 8, 9, 10,11,12,13,14,15 # Conjecture: alpha(Gnd) = floor(n/(d+1)) # (recall that Gnd is 2d regular. each vertex has d neighbors to the left and d to the right) # Proof: # Pick an arbitrary vertex v_1 for your independent set. Then lose d neighbors to the right of that vertex # which are no longer eligible for the independent set. To maximize our independent set, we take the # (d+1)-th vertex to the right of v_1. Call it v_2, and put it in our independent set. # We then lose another d vertices to the right of v_2. # Repeat this process iteratively until you reach the last d vertices of the graph/cycle. # Note that these vertices are adjacent to v_1, so we cannot take any of them to be in our independent set. # Then for each vertex that we select, there are (d+1) vertices taken out of the running, and one from each subset # of size (d+1) is included in the independent set. So alpha(G) <= n/(d+1) depending on whether the vertices can # be cleanly partitioned into subsets of size (d+1). Since we aim to maximize the number of vertices # in the independent set, we have that alpha(G) = floor(n/(d+1)) # UpperBoundMinMaxNN(G,r,K): uses combinat[randcomb]({seq(i,i=1..n)},r) K times and finds the minimum # of MaxNN(G,H) for K random r-element subsets of the set of vertices {1,..,n}. UpperBoundMinMaxNN := proc(G,r,K) local n,m,M,H,i: n := G[1]: m := n: # initialize a value for the minimum for i from 1 to K do H := randcomb({seq(i,i=1..n)},r): M := MaxNN(G,H): if M < m then m := M: # update minimum fi: od: m: end: # What did you get for UpperBoundMinMaxNN(Ck(8),129,5000)? # output: 6 # How far is it from the actual minimum of 3 (according to the sensitivity theorem)? # sensitivity theorem: |H| = 2^(n-1)+1 implies alpha(G) >= sqrt(n) # |H| = 129 = 128 + 1 = 2^7 + 1 = 2^(8-1) + 1, so we are within the hypotheses of the theorem # then alpha(G) >= sqrt(8) = 2.(something), so alpha(G) = 3. # so the calculated value of 6 is twice the theorem's value of 3. weird!! ### copied from C11.txt #C11.txt, Feb. 27, 2025, the sensitivity conjecture of Hao Hunag (according to Knuth) Help11:=proc(): print(` NeiList(G), MaxNN(G,H) , MinMaxNN(G,r) , MinMaxNNpablo(G,r), An(n), Bn(n), Mul(A,B)`):end: with(combinat): with(linalg): #Mul(A,B): the product of matrix A and B (assuming that it exists) Mul:=proc(A,B) local i,j,k,n: [seq([seq(add(A[i][k]*B[k][j],k=1..nops(A[i])),j=1..nops(B[1]))],i=1..nops(A))]: end: #NeiList(G): inputs a graph G=[n,E] and outputs a list of length n #whose i-th entry is the set of neighbors of vertex i NeiList:=proc(G) local n, E,e,T,i: n:=G[1]: E:=G[2]: for i from 1 to n do T[i]:={}: od: for e in E do T[e[1]]:=T[e[1]] union {e[2]}: T[e[2]]:=T[e[2]] union {e[1]}: od: [seq(T[i],i=1..n)]: end: #MaxNN(G,H): inputs a graph G=[n,E] and a subset H of {1, ..., n} outputs the #maximum number of neigbors a member that belong to H over all members of H MaxNN:=proc(G,H) local L,i: L:=NeiList(G): max(seq(nops(L[i] intersect H), i in H)): end: #MinMaxNN(G,r): minimum of MaxNN(G,H) over all subsets H of {1, ..., n} with cardinality r #Note: the Hao Huang famous sensitivity conjecture says that #MinMaxNN(Ck(n),2^(n-1)+1)>=sqrt(n) MinMaxNN:=proc(G,r) local n,i,S,s: n:=G[1]: S:=choose({seq(i,i=1..n)},r): min(seq(MaxNN(G,s), s in S)): end: # MinMaxNNpablo(G,r): minimum of MaxNN(G,H) over all subsets H of [n] with size r. more memory-efficient way #suggested by Pablo Blacno (after discussions with Auora Hiveley) MinMaxNNpablo:=proc(G,r) local n,i,c,mini,curr: n:=G[1]: c:=firstcomb(n,r): mini:=MaxNN(G,c): # check {1,..,r} first while nextcomb(c,n)<>FAIL do: # check all other r-subsets of [n] and update the minimum if they are better c:=nextcomb(c,n): curr:=MaxNN(G,c): if curr < mini then: mini:=curr: fi: od: mini: end: #An(n): the 2^n by 2^n matrix (given as a list of lists) in Knuth's writeup of Huang's proof An:=proc(n) local A,i: option remember: if n=0 then RETURN([[0]]): fi: A:=An(n-1): [ seq([op(A[i]),0$(i-1),1,0$(nops(A[i])-i)],i=1..nops(A)), seq ([0$(i-1),1,0$(nops(A[i])-i), op(-A[i])],i=1..nops(A)) ]: end: #Bn(n): the 2^(n-1) by 2^n matrix in the paper Bn:=proc(n) local A,i: A:=An(n-1): [ seq(A[i]+ [0$(i-1),sqrt(n),0$(nops(A[i])-i)],i=1..nops(A)), seq([0$(i-1),1,0$(nops(A[i])-i)],i=1..nops(A)) ]: end: #old stuff #C2.txt: Jan. 27, 2025 Help2:=proc(): print(`LC(p), RG(n,p), Cliques(G,k) `):end: with(combinat): #LC(p): inputs a rational number between 0 and 1 and outputs true with prob. p LC:=proc(p) local a,b,ra: if not (type(p,fraction) and p>=0 and p<=1) then RETURN(FAIL): fi: a:=numer(p): b:=denom(p): ra:=rand(1..b)(): if ra<=a then true: else false: fi: end: RG:=proc(n,p) local E,i,j: E:={}: for i from 1 to n do for j from i+1 to n do if LC(p) then E:=E union {{i,j}}: fi: od: od: [n,E]: end: #Cliques(G,k): inputs a graph G and a pos. integer k outputs the set of #k-cliques Cliques:=proc(G,k) local n, E,S,i,c,C: n:=G[1]: E:=G[2]: S:={}: C:=choose({seq(i,i=1..n)},k): for c in C do if choose(c,2) minus E={} then S:=S union {c}: fi: od: S: end: ###From C1 #C1.txt: Jan. 23, 2025 Exp Math (Dr. Z.) Help1:=proc(): print(`Graphs(n), Tri(G) , TotTri(G) `): end: #An undirected graph is a set of vertices V and a set of edges #[V,E] and edge e={i,j} where i and j belong to V #Our vertices are labeled {1,2,...,n} #Our data structure is [n,E] where E is the set of edges [3,{{1,2},{1,3},{2,3}}]; #If there are n vertices how many (undirected) graphs there #Graphs(n): inputs a non-neg. integer and outputs the set of ALL #graphs on {1,...,n} Graphs:=proc(n) local i,j,S,E,s: E:={seq(seq({i,j},j=i+1..n), i=1..n)}; S:=powerset(E): {seq([n,s],s in S)}: end: #Tri(G): inputs a graph [n,E] and outputs the set of all triples {i,j,k} #such {{i,j},{i,k},{j,k}} is a subset of E Tri:=proc(G) local n,S,E,i,j,k: n:=G[1]: E:=G[2]: #S is the set of love triangles S:={}: for i from 1 to n do for j from i+1 to n do for k from j+1 to n do #if member({i,j},E) and member({i,k},E), and member({j,k},E) then if {{i,j},{i,k},{j,k}} minus E={} then S:=S union {{i,j,k}}: fi: od: od: od: S: end: #Comp(G): the complement of G=[n,E] Comp:=proc(G) local n,i,j,E: n:=G[1]: E:=G[2]: [n,{seq(seq({i,j},j=i+1..n), i=1..n)} minus E]: end: #Tot(G): the total number of love triangles and hate triangles TotTri:=proc(G) nops(Tri(G))+nops(Tri(Comp(G))): end: #C9.txt: Feb. 20,2025 Help9:=proc(): print(` Gnd(n,d), AM(G) ,lam2(G), Vk(k), HD1(v) , Ck(k) `):end: with(linalg): #Gnd(n,d): the graph whose vertices are {0,...,n-1} and edges {i, i+j mod n} j=1..d Gnd:=proc(n,d) local i,j,E: E:={ seq(seq({ i,i+j mod n},j=1..d),i=0..n-1)}: [n,subs({seq(i=i+1,i=0..n-1)},E)]: end: #AM(G): the adjacency matrix of the graph G (the stupid way) AM:=proc(G) local n,E,i,j,e,A: n:=G[1]: E:=G[2]: for i from 1 to n do for j from 1 to n do A[i,j]:=0: od: od: for e in E do A[e[1],e[2]]:=1: A[e[2],e[1]]:=1: od: [seq([seq(A[i,j],j=1..n)],i=1..n)]: end: #lam2(G): inputs a graph and returns FAIL if it is not regular, otherwise it recurns #[degree, Lambda_2] (Lambda_2 is the second largestg eigenvalue of the adjacency matrix) lam2:=proc(G) local A,x,d,S,i: A:=AM(G): S:={seq(add(A[i]),i=1..nops(A))}: if nops(S)<>1 then RETURN(FAIL): fi: d:=S[1]: [d,fsolve(charpoly(A,x))[-2]]: end: #Vk(k): The list of all 0-1 vectors of length k in lex order Vk:=proc(k) local S,i: option remember: if k=0 then RETURN([[]]): fi: S:=Vk(k-1): [seq([0, op(S[i])], i=1..nops(S)),seq([1, op(S[i])], i=1..nops(S))]: end: #HD1(v): inputs a 0-1 vector and outputs all the vectors where exactly one bit is changed HD1:=proc(v) local k,i: k:=nops(v): if {op(v)} minus {0,1}<>{} then RETURN(FAIL): fi: {seq([op(1..i-1,v), 1-v[i] , op(i+1..k,v)], i=1..k)}: end: #Ck(k): the k-dim unit cube as a graph in our format Ck:=proc(k) local V,E,i,v: V:=Vk(k): #E is the set of edges {v,n} where n is a member of HD1(v) E:={seq(seq({V[i],v},v in HD1(V[i])),i=1..nops(V))}: E:=subs({seq(V[i]=i,i=1..nops(V))},E): [nops(V),E]: end: