ABSTRACT
Erdõs liked to tell the story of how he almost discovered extremal graph theory but somehow (perhaps, as he said, because his brain wasn't open at that particular time) missed it. This near miss was in connection with one of his classic number theory problems in his 1938 paper:3
How many integers can one choose between 1 and n, say, 1 so that
Let us denote the largest possible value of r by 6(n). What Erdõs did was the following:
Letting A = {x : 1 < x < n 2 / 3 } , P = {p prime : n 2 / 3 < p < n}, and B = A U P , Erdõs first observed that every m e [1, n] can be written as m = a(m)b(m) where we can assume without loss of generality that a(m) < 6(m), a(m) € A and b(m) e B. Next, he formed a bipartite graph G with vertex sets A and JB, and with all edges (a(m), b(m)) for all me [1, ri\. He then observed that if our original set of a¿'s has distinct pair products then G can contain no 4-cycle C4. Otherwise, if aba'b' is a 4-cycle in G then all of ab,ba!,a!b', and b'a will be in our set which would then imply (ab)(a'b') = (6a/)(6'a), a contradiction.
