Documentation

FormalConjectures.ErdosProblems.«566»

Erdős Problem 566 #

Let $G$ be such that any subgraph on $k$ vertices has at most $2k-3$ edges. Is it true that, if $H$ has $m$ edges and no isolated vertices, then $$ \hat{r}(G,H) \ll m? $$

In other words, is $G$ Ramsey size linear?

Reference: erdosproblems.com/566

[EFRS93] Erdős, Faudree, Rousseau and Schelp, Ramsey size linear graphs. Combin. Probab. Comput. (1993), 389-399.

theorem Erdos566.erdos_566 :
sorry ∀ (p : ) (G : SimpleGraph (Fin p)), (∀ (S : Finset (Fin p)), 2 S.card(SimpleGraph.induce (↑S) G).edgeSet.ncard 2 * S.card - 3)c > 0, ∀ (n : ) (H : SimpleGraph (Fin n)) [inst : DecidableRel H.Adj], (∀ (v : Fin n), 0 < H.degree v)(G.sizeRamsey H) c * H.edgeSet.ncard

Erdős Problem 566

Let $G$ be such that any subgraph on $k$ vertices has at most $2k-3$ edges. Is it true that, if $H$ has $m$ edges and no isolated vertices, then $\hat{r}(G,H) \ll m$?

In other words: if $G$ is sparse (every induced subgraph on $k$ vertices has $≤ 2k-3$ edges), is $G$ Ramsey size linear?