← All problems

Erdős Problem #1018 — Small nonplanar subgraphs in moderately dense graphs

55 years old · traced to

For a finite simple graph GG, write e(G)e(G) for its number of edges, and let a subgraph mean an ordinary, not necessarily induced, subgraph. The question is whether, for every real ϵ>0\epsilon>0, there are a constant CϵC_\epsilon and an integer n0(ϵ)n_0(\epsilon) such that for every integer n≥n0(ϵ)n\ge n_0(\epsilon) and every nn-vertex graph GG,

e(G)≥⌊n1+ϵ⌋e(G)\ge \lfloor n^{1+\epsilon}\rfloor

implies that GG contains a nonplanar subgraph HH with ∣V(H)∣≤Cϵ|V(H)|\le C_\epsilon. For simple graphs the substantive range is 0<ϵ<10<\epsilon<1; for ϵ≥1\epsilon\ge1 the edge condition is impossible for all sufficiently large nn. Erdős Problem #1018 Jiang (2011)

Background

Erdős posed the question in 1971. A graph with more than 3n−63n-6 edges cannot itself be planar, but that only gives a nonplanar subgraph whose order may grow with nn. The problem asks whether a modest superlinear edge count forces a witness of bounded order. Erdős also observed that any such bound CϵC_\epsilon must grow without bound as ϵ\epsilon tends to zero. The role of the exponent is natural in light of high-girth constructions: for 0<ϵ<10<\epsilon<1, graphs can have on the order of n1+ϵn^{1+\epsilon} edges while having girth at least 1/ϵ1/\epsilon, which forces subdivisions of complete graphs to use many vertices as ϵ\epsilon decreases. Erdős Problem #1018 Jiang (2011)

References

P. Erdős, Some unsolved problems in graph theory and combinatorial analysis, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press (1971), 97–109.

Source: P. Erdős, Some unsolved problems in graph theory and combinatorial analysis, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press (1971), 97–109.

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.