The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A324018 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
 0, 62, 182596118 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS 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? 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). LINKS Jerome Barkley, Improved lower bound on an Euclidean Ramsey problem, arXiv:0811.1055 [math.CO], 2008. Jacob Fox and Ray Li, On edge-ordered Ramsey numbers, arXiv:1906.08234 [math.CO], 2019. R. L. Graham and B. L. Rothschild, Ramsey's Theorem for n-Parameter Sets,Transactions of the American Mathematical Society, 159 (1971), 257-292. Mikhail Lavrov, Mitchell Lee, and John Mackey,Improved upper and lower bounds on a geometric Ramsey problem, European Journal of Combinatorics, 42 (2014), 135-144. EXAMPLE a(1) = 0 because there are no relevant 1-dimensional K4 subgraphs. PROG (PARI) A324018(n)={ 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, 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)); 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)~); 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]))); 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)} CROSSREFS Sequence in context: A159374 A115460 A116270 * A102241 A255915 A351341 Adjacent sequences:  A324015 A324016 A324017 * A324019 A324020 A324021 KEYWORD nonn,bref,hard,more AUTHOR Davis Smith, Aug 20 2019 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 9 05:51 EDT 2022. Contains 356016 sequences. (Running on oeis4.)