Erdős Problems

Browse all problems

↑ ↓ to move↵ to openesc to close

Loading problem…

Status

On this page

Status

Topics

Terms Privacy info@plasma.ai

Problem 642 — Erdős Problems

Problem 642

Let $f(n)$ be the maximal number of edges in a graph on $n$ vertices such that all cycles have more vertices than chords. Is it true that $f(n)\ll n$ ?

Source: erdosproblems.com/642

Graph theory
Cycles

Wiki page

Status

Open

No claim settles this problem.

CES96: Chen, Guantao and Erdős, Paul and Staton, William, Proof of a conjecture of Bollobás on nested cycles. J. Combin. Theory Ser. B (1996), 38-43.
DMMS24: Draganić, Nemanja and Methuku, Abhishek and Munhá Correia, David and Sudakov, Benny, Cycles with many chords. Random Structures Algorithms 65 (2024), no. 1, 3-16, doi:10.1002/rsa.21207.

Proof claims

Loading proof claims…

Discussion

Loading discussion…

PreviousProblem 641 NextProblem 643

On this page

Statement
Status
References
Proof claims
Discussion

Status: Open
Topics: Graph theory
Cycles
In the wiki: Wiki page