Erdős Problem #1079 — A dense neighborhood at the Turán threshold

About 51 years old · traced to

For r≥4r≥4, let fr(n)f_r(n) be the least number of edges forcing a KrK_r in every nn-vertex graph. Is there a constant cr>0c_r>0 such that every nn-vertex graph with fr(n)f_r(n) edges has a vertex of degree m>crnm>c_rn whose neighborhood spans at least fr−1(m)f_{r-1}(m) edges?

References

Additional references

P. Erdős, Some recent progress on extremal problems in graph theory, Congressus Numerantium 14 (1975), 3–14.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.