login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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

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 A234692

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 23 07:22 EDT 2020. Contains 337295 sequences. (Running on oeis4.)