Erdős Problem #1182 — Size-Ramsey extremal functions for triangles versus sparse graphs

About 48 years old · traced to

Let r^(G1,G2)\hat r(G_1,G_2) be the least number of edges in a graph HH such that every red-blue colouring of E(H)E(H) contains a red copy of G1G_1 or a blue copy of G2G_2. Let f(n)f(n) be the largest mm for which some nn-vertex graph GG with mm edges satisfies r^(K3,G)≤2n−1\hat r(K_3,G)≤2n-1, and let F(n)F(n) be the largest mm such that every nn-vertex graph with at most mm edges satisfies this inequality. Determine the orders of growth of f(n)f(n) and F(n)F(n). In particular, do f(n)/F(n)→∞f(n)/F(n)→∞ and F(n)/n→∞F(n)/n→∞?

References

Additional references

P. Erdős, Problems and results in combinatorial analysis and combinatorial number theory, Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (1978), 29–40.

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.