/-
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 FormalConjecturesUtilErdős Problem 665
References:
[Er97f] Erdős, Paul, Some unsolved problems. Combinatorics, geometry and probability (Cambridge, 1993) (1997), 1-10.
[ErLa82] Erdős, P. and Larson, J., On pairwise balanced block designs with the sizes of blocks as uniform as possible. Annals of Discrete Mathematics (1982), 129-134.
[ShSi85] S. S. Shrikhande and N. M. Singhi, On a problem of Erdős and Larson. Combinatorica (1985), 351-358.
@[expose] public sectionnamespace Erdos665open Filter AsymptoticsA pairwise balanced design for ${1,\ldots,n}$ is a collection of sets $A_1,\ldots,A_m\subseteq {1,\ldots,n}$ such that $2\leq \lvert A_i\rvert <n$ and every pair of distinct elements $x,y\in {1,\ldots,n}$ is contained in exactly one $A_i$. Is there a constant $C>0$ and, for all large $n$, a pairwise balanced design such that $$\lvert A_i\rvert > n^{1/2}-C$$ for all $1\leq i\leq m$?
@[category research open, question, AMS 5]
theorem erdos_665 :
∃ C : ℝ, 0 < C ∧ ∀ᶠ n : ℕ in atTop,
∃ H : Finset (Finset (Fin n)), H.IsPairwiseBalancedDesign ∧
∀ e ∈ H, e.card < n ∧ Real.sqrt n - C < e.card := ⊢ ∃ C, 0 < C ∧ ∀ᶠ (n : ℕ) in atTop, ∃ H, H.IsPairwiseBalancedDesign ∧ ∀ e ∈ H, e.card < n ∧ √↑n - C < ↑e.card
All goals completed! 🐙end Erdos665