login
Consider the complete graph of an n-cube. a(n) is the number of 2-color colorings of the edges such that they do not contain a monochromatic planar K4 subgraph.
1

%I #18 Aug 22 2019 05:00:52

%S 0,62,182596118

%N Consider the complete graph of an n-cube. a(n) is the number of 2-color colorings of the edges such that they do not contain a monochromatic planar K4 subgraph.

%C The lowest value of n > 1 such that a(n) = 0 is the answer to the following Euclidean Ramsey problem: Connect all 2^m vertices of an m-dimensional hypercube. Color each of those connections one of 2 colors. What is the smallest value of m such that every coloring of the m-cube contains at least 1 complete monochromatic planar subgraph on 4 vertices?

%C For n > 1, a(n) <= 31*2^(binomial(2^n,2) - 5). (Conjecture) For n >= 3, a(n) < 31*(2^(binomial(2^n,2) - 5) - 2^(binomial(2^n,2) - 10).

%H Jerome Barkley, <a href="https://arxiv.org/abs/0811.1055">Improved lower bound on an Euclidean Ramsey problem</a>, arXiv:0811.1055 [math.CO], 2008.

%H Jacob Fox and Ray Li, <a href="https://arxiv.org/abs/1906.08234">On edge-ordered Ramsey numbers</a>, arXiv:1906.08234 [math.CO], 2019.

%H R. L. Graham and B. L. Rothschild, <a href="https://doi.org/10.1090/S0002-9947-1971-0284352-8">Ramsey's Theorem for n-Parameter Sets</a>,Transactions of the American Mathematical Society, 159 (1971), 257-292.

%H Mikhail Lavrov, Mitchell Lee, and John Mackey,<a href="https://doi.org/10.1016/j.ejc.2014.06.003">Improved upper and lower bounds on a geometric Ramsey problem</a>, European Journal of Combinatorics, 42 (2014), 135-144.

%e a(1) = 0 because there are no relevant 1-dimensional K4 subgraphs.

%o (PARI) A324018(n)={

%o numedge=binomial(2^n,2);lowercolor=shift(1,numedge-1);uppercolor=bitneg(0,numedge)-shift(1,numedge-6);maximumvalue=shift(31,numedge-5);count=0;offset=(n>2);if(n<=1,0,

%o edges=vector(n,b,A=List();forvec(a=vector(2*0^(b-1)+2,i,[1,2^if(b-1,b,n)]),listput(A,a),2);Vec(A));

%o e=matconcat(vecsort(apply(cvert->vecsort(apply(cedge->for(d=2,n,if(vecsearch(edges[d],cedge),return(vecsearch(edges[d],cedge)-1),vecsearch(edges[d+1],cedge)&&vecsearch(edges[d+1],cedge)<=#edges[d],return(vecsearch(edges[d+1],edges[d][vecsearch(edges[d+1],cedge)])-1))),apply(edge->vecextract(cvert,edge),edges[2]))),select(vertex->(matrank(matrix(n,#vertex-1,q,p,bittest(vertex[p]-1,q-1)-bittest(vertex[#vertex]-1,q-1)))<=2),edges[1])),,4)~);

%o edgebits=matrix(6,#e[,1]-offset,q,p,e[p+offset,q]);coplanar=#edgebits[1,];checker=vector(coplanar,i,sum(b=1,6,shift(1,edgebits[b,i])));

%o forstep(coloring=uppercolor,lowercolor,-1, for(m=1,coplanar,if(bitand(checker[m],coloring)==checker[m],count=count+shift(2,edgebits[1,m]);coloring=coloring-bitneg(0,edgebits[1,m]);break(),bitand(checker[m],coloring),,count=count+shift(2,edgebits[1,m]);coloring=coloring-bitneg(0,edgebits[1,m]);break())));maximumvalue-count)}

%K nonn,bref,hard,more

%O 1,2

%A _Davis Smith_, Aug 20 2019