/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Erdős Problem 211

References:

    erdosproblems.com/211

    [Be83] Beck, József, On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry. Combinatorica (1983), 281-297.

    [SzTr83] Szemerédi, Endre and Trotter, Jr., William T., Extremal problems in discrete geometry. Combinatorica (1983), 381-392.

    [Er84] Erdős, P., Research problems. Period. Math. Hungar. (1984), 101-103.

    [BGS74] Burr, Stefan A. and Grünbaum, Branko and Sloane, N. J. A., The orchard problem. Geometriae Dedicata (1974), 397-424.

    [FuPa84] Füredi, Z. and Palásti, I., Arrangements of lines with a large number of triangles. Proc. Amer. Math. Soc. (1984), 561-566.

@[expose] public sectionnamespace Erdos211open EuclideanGeometry Filteropen scoped Classical in

Distinct lines containing two distinct points of the configuration.

noncomputable def determinedLines (s : Finset ℝ²) : Finset (AffineSubspace ℝ ℝ²) := s.offDiag.image fun p => line[ℝ, p.1, p.2]open scoped Classical in

The uniform Erdős–Beck lower bound.

def MainBound : Prop := ∃ c : ℝ, 0 < c ∧ ∀ (n k : ℕ), 1 ≤ k → k < n → ∀ s : Finset ℝ², s.card = n → (∀ L : AffineSubspace ℝ ℝ², IsLine L → (s.filter fun p => p ∈ L).card ≤ n - k) → c * (k : ℝ) * (n : ℝ) ≤ ((determinedLines s).card : ℝ)open scoped Classical in

The quadratic lower bound for configurations with at most half the points on a line.

def QuadraticBound : Prop := ∃ c : ℝ, 0 < c ∧ ∀ n : ℕ, 1 ≤ n → ∀ s : Finset ℝ², s.card = 2 * n → (∀ L : AffineSubspace ℝ ℝ², IsLine L → (s.filter fun p => p ∈ L).card ≤ n) → c * (n : ℝ) ^ 2 ≤ ((determinedLines s).card : ℝ)open scoped Classical in

Erdős speculates that there are at least $(1+o(1))kn/6$ determined lines [Er84]. The asymptotic bound is uniform over $1 \leq k < n$.

@[category research open, AMS 5 52] theorem erdos_211.variants.one_sixth : ∀ ε : ℝ, 0 < ε → ∃ N : ℕ, ∀ (n k : ℕ), N ≤ n → 1 ≤ k → k < n → ∀ s : Finset ℝ², s.card = n → (∀ L : AffineSubspace ℝ ℝ², IsLine L → (s.filter fun p => p ∈ L).card ≤ n - k) → (1 - ε) / 6 * (k : ℝ) * (n : ℝ) ≤ ((determinedLines s).card : ℝ) := ⊢ ∀ (ε : ℝ), 0 < ε → ∃ N, ∀ (n k : ℕ), N ≤ n → 1 ≤ k → k < n → ∀ (s : Finset ℝ²), s.card = n → (∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n - k) → (1 - ε) / 6 * ↑k * ↑n ≤ ↑(determinedLines s).card All goals completed! 🐙open scoped Classical in

There are arbitrarily large configurations with no four collinear points and $\sim n^2/6$ three-point lines, constructed by Burr, Grünbaum, and Sloane [BGS74] and Füredi and Palásti [FuPa84]. The index need not equal the number of points.

@[category research solved, AMS 5 52] theorem erdos_211.variants.sharpness : ∃ s : ℕ → Finset ℝ², Tendsto (fun i => (s i).card) atTop atTop ∧ (∀ (i : ℕ) (L : AffineSubspace ℝ ℝ²), IsLine L → ((s i).filter fun p => p ∈ L).card ≤ 3) ∧ Tendsto (fun i => (((determinedLines (s i)).filter fun L => ((s i).filter fun p => p ∈ L).card = 3).card : ℝ) / ((s i).card : ℝ) ^ 2) atTop (nhds (1 / 6 : ℝ)) := ⊢ ∃ s, Tendsto (fun i ↦ (s i).card) atTop atTop ∧ (∀ (i : ℕ) (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s i | p ∈ L}.card ≤ 3) ∧ Tendsto (fun i ↦ ↑{L ∈ determinedLines (s i) | {p ∈ s i | p ∈ L}.card = 3}.card / ↑(s i).card ^ 2) atTop (nhds (1 / 6)) All goals completed! 🐙

Membership means that two distinct points of the configuration generate the line.

@[category API, AMS 5 52] theorem mem_determinedLines {s : Finset ℝ²} {L : AffineSubspace ℝ ℝ²} : L ∈ determinedLines s ↔ ∃ a ∈ s, ∃ b ∈ s, a ≠ b ∧ line[ℝ, a, b] = L := s:Finset ℝ²L:AffineSubspace ℝ ℝ²⊢ L ∈ determinedLines s ↔ ∃ a ∈ s, ∃ b ∈ s, a ≠ b ∧ line[ℝ, a, b] = L classical s:Finset ℝ²L:AffineSubspace ℝ ℝ²⊢ (∃ a, (a.1 ∈ s ∧ a.2 ∈ s ∧ a.1 ≠ a.2) ∧ line[ℝ, a.1, a.2] = L) ↔ ∃ a ∈ s, ∃ b ∈ s, a ≠ b ∧ line[ℝ, a, b] = L All goals completed! 🐙

A span of two distinct points is a geometric line.

a:ℝ²b:ℝ²hab:a ≠ b⊢ Module.finrank ℝ ↥(ℝ ∙ (a -ᵥ b)) = 1 All goals completed! 🐙

Two distinct points on a geometric line span the whole line.

@[category API, AMS 5 52] theorem line_pair_eq {a b : ℝ²} {L : AffineSubspace ℝ ℝ²} (hL : IsLine L) (ha : a ∈ L) (hb : b ∈ L) (hab : a ≠ b) : line[ℝ, a, b] = L := a:ℝ²b:ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lha:a ∈ Lhb:b ∈ Lhab:a ≠ b⊢ line[ℝ, a, b] = L a:ℝ²b:ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lha:a ∈ Lhb:b ∈ Lhab:a ≠ b⊢ line[ℝ, a, b].direction = L.direction a:ℝ²b:ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lha:a ∈ Lhb:b ∈ Lhab:a ≠ b⊢ line[ℝ, a, b].direction ≤ L.directiona:ℝ²b:ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lha:a ∈ Lhb:b ∈ Lhab:a ≠ b⊢ Module.finrank ℝ ↥line[ℝ, a, b].direction = Module.finrank ℝ ↥L.direction a:ℝ²b:ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lha:a ∈ Lhb:b ∈ Lhab:a ≠ b⊢ line[ℝ, a, b].direction ≤ L.direction All goals completed! 🐙 a:ℝ²b:ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lha:a ∈ Lhb:b ∈ Lhab:a ≠ b⊢ Module.finrank ℝ ↥line[ℝ, a, b].direction = Module.finrank ℝ ↥L.direction All goals completed! 🐙

Every determined line is one-dimensional.

@[category API, AMS 5 52] theorem isLine_of_mem_determinedLines {s : Finset ℝ²} {L : AffineSubspace ℝ ℝ²} (hL : L ∈ determinedLines s) : IsLine L := s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines s⊢ IsLine L s:Finset ℝ²a:ℝ²left✝¹:a ∈ sb:ℝ²left✝:b ∈ shab:a ≠ bhL:line[ℝ, a, b] ∈ determinedLines s⊢ IsLine line[ℝ, a, b] All goals completed! 🐙

The finite image counts precisely all geometric lines containing at least two points.

s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ L ∈ determinedLines s ↔ IsLine L ∧ 2 ≤ {p ∈ s | p ∈ L}.card s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ L ∈ determinedLines s → IsLine L ∧ 2 ≤ {p ∈ s | p ∈ L}.cards:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ IsLine L ∧ 2 ≤ {p ∈ s | p ∈ L}.card → L ∈ determinedLines s s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ L ∈ determinedLines s → IsLine L ∧ 2 ≤ {p ∈ s | p ∈ L}.card s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.cardh:L ∈ determinedLines s⊢ IsLine L ∧ 2 ≤ {p ∈ s | p ∈ L}.card s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.cardh:L ∈ determinedLines sa:ℝ²ha:a ∈ sb:ℝ²hb:b ∈ shab:a ≠ bheq:line[ℝ, a, b] = L⊢ IsLine L ∧ 2 ≤ {p ∈ s | p ∈ L}.card s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.cardh:L ∈ determinedLines sa:ℝ²ha:a ∈ sb:ℝ²hb:b ∈ shab:a ≠ bheq:line[ℝ, a, b] = L⊢ 2 ≤ {p ∈ s | p ∈ L}.card s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.cardh:L ∈ determinedLines sa:ℝ²ha:a ∈ sb:ℝ²hb:b ∈ shab:a ≠ bheq:line[ℝ, a, b] = L⊢ 1 < {p ∈ s | p ∈ L}.card s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.cardh:L ∈ determinedLines sa:ℝ²ha:a ∈ sb:ℝ²hb:b ∈ shab:a ≠ bheq:line[ℝ, a, b] = L⊢ ∃ a ∈ {p ∈ s | p ∈ L}, ∃ b ∈ {p ∈ s | p ∈ L}, a ≠ b All goals completed! 🐙 s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ IsLine L ∧ 2 ≤ {p ∈ s | p ∈ L}.card → L ∈ determinedLines s s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard✝:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.cardhL:IsLine Lhcard:2 ≤ {p ∈ s | p ∈ L}.card⊢ L ∈ determinedLines s s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard✝:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.cardhL:IsLine Lhcard:2 ≤ {p ∈ s | p ∈ L}.carda:ℝ²ha:a ∈ {p ∈ s | p ∈ L}b:ℝ²hb:b ∈ {p ∈ s | p ∈ L}hab:a ≠ b⊢ L ∈ determinedLines s All goals completed! 🐙open scoped Classical in

The fiber over a geometric line consists of the ordered pairs of distinct incident points.

@[category API, AMS 5 52] theorem pair_fiber_eq {s : Finset ℝ²} {L : AffineSubspace ℝ ℝ²} (hL : IsLine L) : (s.offDiag.filter fun p => line[ℝ, p.1, p.2] = L) = (s.filter fun p => p ∈ L).offDiag := s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine L⊢ {p ∈ s.offDiag | line[ℝ, p.1, p.2] = L} = {p ∈ s | p ∈ L}.offDiag classical s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lp:ℝ² × ℝ²⊢ p ∈ {p ∈ s.offDiag | line[ℝ, p.1, p.2] = L} ↔ p ∈ {p ∈ s | p ∈ L}.offDiag s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lp:ℝ² × ℝ²⊢ (p.1 ∈ s ∧ p.2 ∈ s ∧ p.1 ≠ p.2) ∧ line[ℝ, p.1, p.2] = L ↔ (p.1 ∈ s ∧ p.1 ∈ L) ∧ (p.2 ∈ s ∧ p.2 ∈ L) ∧ p.1 ≠ p.2 s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lp:ℝ² × ℝ²⊢ (p.1 ∈ s ∧ p.2 ∈ s ∧ p.1 ≠ p.2) ∧ line[ℝ, p.1, p.2] = L → (p.1 ∈ s ∧ p.1 ∈ L) ∧ (p.2 ∈ s ∧ p.2 ∈ L) ∧ p.1 ≠ p.2s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lp:ℝ² × ℝ²⊢ (p.1 ∈ s ∧ p.1 ∈ L) ∧ (p.2 ∈ s ∧ p.2 ∈ L) ∧ p.1 ≠ p.2 → (p.1 ∈ s ∧ p.2 ∈ s ∧ p.1 ≠ p.2) ∧ line[ℝ, p.1, p.2] = L s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lp:ℝ² × ℝ²⊢ (p.1 ∈ s ∧ p.2 ∈ s ∧ p.1 ≠ p.2) ∧ line[ℝ, p.1, p.2] = L → (p.1 ∈ s ∧ p.1 ∈ L) ∧ (p.2 ∈ s ∧ p.2 ∈ L) ∧ p.1 ≠ p.2 s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lp:ℝ² × ℝ²heq:line[ℝ, p.1, p.2] = Lha:p.1 ∈ shb:p.2 ∈ shab:p.1 ≠ p.2⊢ (p.1 ∈ s ∧ p.1 ∈ L) ∧ (p.2 ∈ s ∧ p.2 ∈ L) ∧ p.1 ≠ p.2 All goals completed! 🐙 s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lp:ℝ² × ℝ²⊢ (p.1 ∈ s ∧ p.1 ∈ L) ∧ (p.2 ∈ s ∧ p.2 ∈ L) ∧ p.1 ≠ p.2 → (p.1 ∈ s ∧ p.2 ∈ s ∧ p.1 ≠ p.2) ∧ line[ℝ, p.1, p.2] = L s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lp:ℝ² × ℝ²ha:p.1 ∈ shaL:p.1 ∈ Lhab:p.1 ≠ p.2hb:p.2 ∈ shbL:p.2 ∈ L⊢ (p.1 ∈ s ∧ p.2 ∈ s ∧ p.1 ≠ p.2) ∧ line[ℝ, p.1, p.2] = L All goals completed! 🐙open scoped Classical in

Exact double counting: each ordered pair belongs to its unique determined line.

All goals completed! 🐙open scoped Classical in

Elementary bound when no line contains more than $r$ points. This is weaker than the Erdős–Beck bound and is not a proof of erdos_211.

s:Finset ℝ²r:ℕhr:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ r⊢ ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) ≤ (determinedLines s).card * (r * (r - 1)) calc _ ≤ ∑ _L ∈ determinedLines s, r * (r - 1) := s:Finset ℝ²r:ℕhr:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ r⊢ ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) ≤ ∑ _L ∈ determinedLines s, r * (r - 1) s:Finset ℝ²r:ℕhr:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ r⊢ ∀ i ∈ determinedLines s, {p ∈ s | p ∈ i}.card * ({p ∈ s | p ∈ i}.card - 1) ≤ r * (r - 1) s:Finset ℝ²r:ℕhr:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ rL:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines s⊢ {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) ≤ r * (r - 1) s:Finset ℝ²r:ℕhr:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ rL:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines sh:{p ∈ s | p ∈ L}.card ≤ r⊢ {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) ≤ r * (r - 1) All goals completed! 🐙 _ = _ := s:Finset ℝ²r:ℕhr:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ r⊢ ∑ _L ∈ determinedLines s, r * (r - 1) = (determinedLines s).card * (r * (r - 1)) All goals completed! 🐙open scoped Classical in

In a configuration with no three collinear points, every unordered pair gives a line.

s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines shlo:2 ≤ {p ∈ s | p ∈ L}.cardhc:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = 2 s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines shlo:2 ≤ {p ∈ s | p ∈ L}.cardhc:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.cardheq:{p ∈ s | p ∈ L}.card = 2⊢ {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = 2 All goals completed! 🐙 _ = _ := s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2⊢ ∑ _L ∈ determinedLines s, 2 = 2 * (determinedLines s).card All goals completed! 🐙open scoped Classical in

With at most three points on each line, double counting gives the sharp leading coefficient $1/6$ in a quadratic lower bound.

@[category API, AMS 5 52] theorem six_mul_lines_no_four {s : Finset ℝ²} (hs : ∀ L : AffineSubspace ℝ ℝ², IsLine L → (s.filter fun p => p ∈ L).card ≤ 3) : s.card * (s.card - 1) ≤ 6 * (determinedLines s).card := s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 3⊢ s.card * (s.card - 1) ≤ 6 * (determinedLines s).card All goals completed! 🐙open scoped Classical in

The real-valued form of the preceding bound, including empty configurations.

s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 3h:s.card * (s.card - 1) ≤ 6 * (determinedLines s).cardhzero:¬s.card = 0hone:1 ≤ s.cardhreal:↑s.card * (↑s.card - 1) ≤ 6 * ↑(determinedLines s).card⊢ ↑s.card * (↑s.card - 1) / 6 ≤ ↑(determinedLines s).card All goals completed! 🐙

The quadratic special case follows with twice the constant in the main bound.

c:ℝhc:0 < ch:∀ (n k : ℕ), 1 ≤ k → k < n → ∀ (s : Finset ℝ²), s.card = n → (∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n - k) → c * ↑k * ↑n ≤ ↑(determinedLines s).cardn:ℕhn:1 ≤ ns:Finset ℝ²hs:s.card = 2 * nhcap:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ nhkn:n < 2 * nhb:c * ↑n * ↑(2 * n) ≤ ↑(determinedLines s).card⊢ 2 * c * ↑n ^ 2 ≤ ↑(determinedLines s).card c:ℝhc:0 < ch:∀ (n k : ℕ), 1 ≤ k → k < n → ∀ (s : Finset ℝ²), s.card = n → (∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n - k) → c * ↑k * ↑n ≤ ↑(determinedLines s).cardn:ℕhn:1 ≤ ns:Finset ℝ²hs:s.card = 2 * nhcap:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ nhkn:n < 2 * nhb:c * ↑n * (2 * ↑n) ≤ ↑(determinedLines s).card⊢ 2 * c * ↑n ^ 2 ≤ ↑(determinedLines s).card All goals completed! 🐙

Let $1\leq k<n$. Given $n$ points in $\mathbb{R}^2$, at most $n-k$ on any line, there are $\gg kn$ many lines which contain at least two points. Solved by Beck [Be83] and Szemerédi and Trotter [SzTr83].

@[category research solved, AMS 5 52, formal_proof using lean4 at "https://github.com/plby/lean-proofs/blob/8822f7ddef30fadbd92e1c6ab4ed897af356af5e/src/latest/ErdosProblems/Erdos211.lean#L900"] theorem erdos_211 : MainBound := ⊢ MainBound All goals completed! 🐙

Given any $2n$ points with at most $n$ on a line there are $\gg n^2$ many lines formed by the points. Solved by Beck [Be83] and Szemerédi and Trotter [SzTr83].

@[category research solved, AMS 5 52] theorem erdos_211.variants.quadratic : QuadraticBound := quadratic_of_erdos_211 erdos_211end Erdos211