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.

0, 62, 182596118

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

Table of n, a(n) for n=1..3.

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