Problem 146 — Visual explainer (undergrad)
==========================================

Problem statement
---------------
If $H$ is bipartite and is $r$-degenerate, that is, every induced subgraph of $H$ has minimum degree $\leq r$, then\[\mathrm{ex}(n;H) \ll n^{2-1/r}.\]

Picture
-------
Graph picture:

o---o
|\  |
| \ |
o---o    K4 is the complete graph on 4 vertices (all connections)

Conjecture / Task: what to look at
------------------------
- Restate the problem as: given the constraint, what asymptotic bound or
  structure must follow?
- Use the comments as benchmarks (best known bounds / constructions).

Context
-------
Area hint: infinite graph theory / Ramsey-type decompositions.

Notation (if it appears above)
-----------------------------
- `\ll` / `<<` means "at most a constant times" (for large parameters).

Benchmarks / known results (from comments)
----------------------------------------
- Conjectured by Erd\H{o}s and Simonovits.
- Alon, Krivelevich, and Sudakov have proved\[\mathrm{ex}(n;H) \ll
  n^{2-1/4r}.\]They also prove the full Erd\H{o}s-Simonovits conjectured bound
  if $H$ is bipartite and the maximum degree in one side of the bipartition is
  $r$.