PPL 045 / 177 permanent IDsPrize Problem Ledger · PPLChecked 2026.07.26
Prize Problem LedgerPPL · Open reward indexAll 177 problems
Prize Problem LedgerErdősPPL 045Erdős Problem #146

Permanent problem IDPPL 045

Verified openErdősconjecture

Graph theory

Erdős Problem #146

If H is bipartite and is r-degenerate, that is, every induced subgraph of H has minimum degree ≤ r, then ex(n;H) ≪ n^(2-1/r).

graph theoryturan number
01

The problem

If H is bipartite and is r-degenerate, that is, every induced subgraph of H has minimum degree ≤ r, then ex(n;H) ≪ n^(2-1/r).

Open since1984exact
Last checked2026.07.26Catalog verification
02

Reward offers

Offer 01$500Paul Erdős / Combinatorics Foundation
Documented

A solution must appear in a reputable journal, with documentation that Erdős offered the displayed amount. Claims are administered by the Combinatorics Foundation; erdosproblems.com does not pay awards.

Award source ↗Rules ↗
03

Sources & reading

2 unique reference linksCanonical problem page Claim or award rules
04

Related open targets

Graph theoryKrenn-Gu conjecturePPL 109 · €3,000 · 8 years openGraph theoryErdős Problem #625PPL 068 · $1000 · 37 years openGraph theoryErdős Problem #500PPL 059 · $500 · 65 years open