Erdős Problem #665

Erdős Problem 665 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/665

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/665.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/665.tex.

FORMAL RESTATEMENT. Fix the convention $[n]=\{1,2,\dots,n\}$ for integers $n\ge 1$.

Literal statement (as written). Does there exist a constant $c\in\mathbb{R}$ such that for every integer $n\ge 1$ there exist an integer $m\ge 1$ and subsets $A_1,\dots,A_m\subseteq [n]$ satisfying:

1. (size lower bound) $|A_i|>\sqrt{n}-c$ for all $i\in\{1,\dots,m\}$,
2. (small intersections) $|A_i\cap A_j|\le 1$ for all $i\ne j$,
3. (pair covering) for every $1\le x<y\le n$ there exists $i$ with $\{x,y\}\subseteq A_i$.

Ambiguity / likely misstatement. As written, one may take $m=1$ and $A_1=[n]$, which makes $2$ vacuous and $3$ automatic. This makes the question trivial. The surrounding context in the problem statement (pairwise balanced designs, embeddings into projective planes) strongly suggests that some nontriviality condition was intended (for example, that no block equals $[n]$, or that the blocks are all "close to" $\sqrt n$ in both directions). Since the literal statement is still a well-posed sentence, below I: (i) give a complete proof for the literal statement, and (ii) record structural lemmas for the standard "nontrivial" interpretation.

QUICK LITERATURE/CONTEXT CHECK. The supplied problem text attributes this to Erdős--Larson and mentions a conditional negative answer due to Shrikhande--Singhi under a conjecture about projective planes. Per the integrity rule for this project, I do not use any external results beyond what is explicitly written in the problem statement.

ATTACK PLAN.

• Proof track (literal statement): Exhibit an explicit construction for all $n$ with a fixed constant $c$ and verify $1$--$3$.
• Nontrivial track (what the context suggests): Assuming $m\ge 2$ (equivalently no block equals $[n]$), derive the standard "linear space" consequences: each pair lies in exactly one block, pair-counting identities, and basic bounds on $m$ when block sizes are $\gtrsim \sqrt n$.

WORK.

Fast reality check (tiny $n$). For $n=1$ the pair-covering condition is vacuous. The size condition requires $|A_i|>1-c$, so any family with a nonempty block works provided $c>0$. For $n\ge 2$, taking $A_1=[n]$ covers all pairs immediately.

Lemma 665.1 (Trivial construction solves the literal statement). There exists a constant $c$ such that for every $n\ge 1$ there are sets $A_1,\dots,A_m\subseteq [n]$ satisfying $1$--$3$. In particular, one may take $c=1$ and $m=1$ with $A_1=[n]$.

Proof. Fix $c=1$. For each $n\ge 1$, set $m=1$ and $A_1=[n]$. Then $|A_1|=n$. We check the three conditions:

1. Since $n\ge 1$, we have $n>\sqrt{n}-1$ because $\sqrt n\le n$ and subtracting $1$ makes the right-hand side strictly smaller than $n$. Thus $|A_1|=n>\sqrt n-1$.
2. The condition "$|A_i\cap A_j|\le 1$ for all $i\ne j$" is vacuously true because there are no distinct indices when $m=1$.
3. For any pair $1\le x<y\le n$, we have $\{x,y\}\subseteq [n]=A_1$.

Therefore the family $\{A_1\}$ satisfies $1$--$3$ for every $n\ge 1$ with the fixed constant $c=1$. $\square$

The remaining lemmas record structure that becomes relevant only if one excludes the trivial "$m=1$, $A_1=[n]$" solution.

Lemma 665.2 (Uniqueness of the block containing a given pair). Let $n\ge 1$ and let $A_1,\dots,A_m\subseteq [n]$ satisfy the intersection condition $|A_i\cap A_j|\le 1$ for $i\ne j$. Then no pair $\{x,y\}$ with $x\ne y$ can be contained in two distinct blocks. Equivalently: if $\{x,y\}\subseteq A_i$ and $\{x,y\}\subseteq A_j$ with $i\ne j$, then this is impossible.

Proof. Assume for contradiction that $i\ne j$ and $x\ne y$ with $\{x,y\}\subseteq A_i\cap A_j$. Then $A_i\cap A_j$ contains both $x$ and $y$, hence $|A_i\cap A_j|\ge 2$, contradicting $|A_i\cap A_j|\le 1$. $\square$

Lemma 665.3 (Pair counting identity in the nontrivial regime). Assume $A_1,\dots,A_m\subseteq [n]$ satisfy: (i) $|A_i\cap A_j|\le 1$ for $i\ne j$, and (ii) every pair $\{x,y\}$ with $1\le x<y\le n$ is contained in some $A_i$. Then every pair is contained in exactly one block, and \[ \sum_{i=1}^m \binom{|A_i|}{2} \,=\, \binom{n}{2}. \]

Proof. Condition (ii) says each pair $\{x,y\}$ is contained in at least one block. Lemma 665.2 implies it is contained in at most one block. Therefore each pair is contained in exactly one block.

Now count unordered pairs of points in two ways. The total number of unordered pairs from $[n]$ is $\binom n2$. On the other hand, block $A_i$ contains exactly $\binom{|A_i|}{2}$ unordered pairs. Since each pair lies in exactly one block, summing over blocks counts each of the $\binom n2$ pairs exactly once, giving the stated identity. $\square$

Lemma 665.4 (Local incidence identity at a point). Under the hypotheses of Lemma 665.3, for each point $v\in[n]$ we have \[ \sum_{i: v\in A_i} (|A_i|-1) \,=\, n-1. \]

Proof. Fix $v\in[n]$. Consider the set of ordered pairs $(v,u)$ with $u\in[n]\setminus\{v\}$; there are exactly $n-1$ such ordered pairs. By Lemma 665.2 and the pair-covering property, for each $u\ne v$ there is a unique block $A_i$ containing $\{v,u\}$. In that block, $u$ is one of the $|A_i|-1$ other points besides $v$. Therefore, as $i$ ranges over blocks containing $v$, the quantity $(|A_i|-1)$ counts exactly the number of choices of $u$ paired with $v$ that are realized inside $A_i$. Summing over all blocks containing $v$ counts each ordered pair $(v,u)$ exactly once, hence the sum equals $n-1$. $\square$

Lemma 665.5 (Crude bounds on the number of blocks from the size constraint). Assume the hypotheses of Lemma 665.3 and additionally that every block has size at least $k\ge 2$. Then \[ m \le \frac{\binom n2}{\binom k2}. \]

Proof. By Lemma 665.3, $\sum_{i=1}^m \binom{|A_i|}{2} = \binom n2$. Since $|A_i|\ge k$ for all $i$ and $t\mapsto \binom t2$ is increasing for $t\ge 2$, we have $\binom{|A_i|}{2}\ge \binom k2$ for all $i$. Therefore \[ \binom n2 = \sum_{i=1}^m \binom{|A_i|}{2} \ge \sum_{i=1}^m \binom k2 = m\binom k2, \] which rearranges to the claimed bound. $\square$

VERIFICATION.

• Quantifiers: Lemma 665.1 produces a single constant $c=1$ that works for all $n\ge 1$.
• Boundary case $n=1$: With $c=1$ and $A_1=[1]$, the size condition is $1>1-1=0$ which holds; the pair-covering condition is vacuous.
• Intersection condition: With $m=1$ it is vacuous; no hidden requirement is used.
• Ambiguity check: The proof indeed exploits the absence of any requirement excluding $m=1$ or excluding $A_1=[n]$.

FINAL. FULL SOLUTION FULL PROOF.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT. Fix the convention $[n]=\{1,2,\dots,n\}$ for integers $n\ge 1$.

Literal statement (as written). Does there exist a constant $c\in\mathbb{R}$ such that for every integer $n\ge 1$ there exist an integer $m\ge 1$ and subsets $A_1,\dots,A_m\subseteq [n]$ satisfying:

1. (size lower bound) $|A_i|>\sqrt{n}-c$ for all $i\in\{1,\dots,m\}$,
2. (small intersections) $|A_i\cap A_j|\le 1$ for all $i\ne j$,
3. (pair covering) for every $1\le x<y\le n$ there exists $i$ with $\{x,y\}\subseteq A_i$.

Ambiguity / likely misstatement. As written, one may take $m=1$ and $A_1=[n]$, which makes $2$ vacuous and $3$ automatic. This makes the question trivial. The surrounding context in the problem statement (pairwise balanced designs, embeddings into projective planes) strongly suggests that some nontriviality condition was intended (for example, that no block equals $[n]$, or that the blocks are all "close to" $\sqrt n$ in both directions). Since the literal statement is still a well-posed sentence, below I: (i) give a complete proof for the literal statement, and (ii) record structural lemmas for the standard "nontrivial" interpretation.

QUICK LITERATURE/CONTEXT CHECK. The supplied problem text attributes this to Erdős--Larson and mentions a conditional negative answer due to Shrikhande--Singhi under a conjecture about projective planes. Per the integrity rule for this project, I do not use any external results beyond what is explicitly written in the problem statement.

ATTACK PLAN.

• Proof track (literal statement): Exhibit an explicit construction for all $n$ with a fixed constant $c$ and verify $1$--$3$.
• Nontrivial track (what the context suggests): Assuming $m\ge 2$ (equivalently no block equals $[n]$), derive the standard "linear space" consequences: each pair lies in exactly one block, pair-counting identities, and basic bounds on $m$ when block sizes are $\gtrsim \sqrt n$.

WORK.

Fast reality check (tiny $n$). For $n=1$ the pair-covering condition is vacuous. The size condition requires $|A_i|>1-c$, so any family with a nonempty block works provided $c>0$. For $n\ge 2$, taking $A_1=[n]$ covers all pairs immediately.

Lemma 665.1 (Trivial construction solves the literal statement). There exists a constant $c$ such that for every $n\ge 1$ there are sets $A_1,\dots,A_m\subseteq [n]$ satisfying $1$--$3$. In particular, one may take $c=1$ and $m=1$ with $A_1=[n]$.

Proof. Fix $c=1$. For each $n\ge 1$, set $m=1$ and $A_1=[n]$. Then $|A_1|=n$. We check the three conditions:

1. Since $n\ge 1$, we have $n>\sqrt{n}-1$ because $\sqrt n\le n$ and subtracting $1$ makes the right-hand side strictly smaller than $n$. Thus $|A_1|=n>\sqrt n-1$.
2. The condition "$|A_i\cap A_j|\le 1$ for all $i\ne j$" is vacuously true because there are no distinct indices when $m=1$.
3. For any pair $1\le x<y\le n$, we have $\{x,y\}\subseteq [n]=A_1$.

Therefore the family $\{A_1\}$ satisfies $1$--$3$ for every $n\ge 1$ with the fixed constant $c=1$. $\square$

The remaining lemmas record structure that becomes relevant only if one excludes the trivial "$m=1$, $A_1=[n]$" solution.

Lemma 665.2 (Uniqueness of the block containing a given pair). Let $n\ge 1$ and let $A_1,\dots,A_m\subseteq [n]$ satisfy the intersection condition $|A_i\cap A_j|\le 1$ for $i\ne j$. Then no pair $\{x,y\}$ with $x\ne y$ can be contained in two distinct blocks. Equivalently: if $\{x,y\}\subseteq A_i$ and $\{x,y\}\subseteq A_j$ with $i\ne j$, then this is impossible.

Proof. Assume for contradiction that $i\ne j$ and $x\ne y$ with $\{x,y\}\subseteq A_i\cap A_j$. Then $A_i\cap A_j$ contains both $x$ and $y$, hence $|A_i\cap A_j|\ge 2$, contradicting $|A_i\cap A_j|\le 1$. $\square$

Lemma 665.3 (Pair counting identity in the nontrivial regime). Assume $A_1,\dots,A_m\subseteq [n]$ satisfy: (i) $|A_i\cap A_j|\le 1$ for $i\ne j$, and (ii) every pair $\{x,y\}$ with $1\le x<y\le n$ is contained in some $A_i$. Then every pair is contained in exactly one block, and \[ \sum_{i=1}^m \binom{|A_i|}{2} \,=\, \binom{n}{2}. \]

Proof. Condition (ii) says each pair $\{x,y\}$ is contained in at least one block. Lemma 665.2 implies it is contained in at most one block. Therefore each pair is contained in exactly one block.

Now count unordered pairs of points in two ways. The total number of unordered pairs from $[n]$ is $\binom n2$. On the other hand, block $A_i$ contains exactly $\binom{|A_i|}{2}$ unordered pairs. Since each pair lies in exactly one block, summing over blocks counts each of the $\binom n2$ pairs exactly once, giving the stated identity. $\square$

Lemma 665.4 (Local incidence identity at a point). Under the hypotheses of Lemma 665.3, for each point $v\in[n]$ we have \[ \sum_{i: v\in A_i} (|A_i|-1) \,=\, n-1. \]

Proof. Fix $v\in[n]$. Consider the set of ordered pairs $(v,u)$ with $u\in[n]\setminus\{v\}$; there are exactly $n-1$ such ordered pairs. By Lemma 665.2 and the pair-covering property, for each $u\ne v$ there is a unique block $A_i$ containing $\{v,u\}$. In that block, $u$ is one of the $|A_i|-1$ other points besides $v$. Therefore, as $i$ ranges over blocks containing $v$, the quantity $(|A_i|-1)$ counts exactly the number of choices of $u$ paired with $v$ that are realized inside $A_i$. Summing over all blocks containing $v$ counts each ordered pair $(v,u)$ exactly once, hence the sum equals $n-1$. $\square$

Lemma 665.5 (Crude bounds on the number of blocks from the size constraint). Assume the hypotheses of Lemma 665.3 and additionally that every block has size at least $k\ge 2$. Then \[ m \le \frac{\binom n2}{\binom k2}. \]

Proof. By Lemma 665.3, $\sum_{i=1}^m \binom{|A_i|}{2} = \binom n2$. Since $|A_i|\ge k$ for all $i$ and $t\mapsto \binom t2$ is increasing for $t\ge 2$, we have $\binom{|A_i|}{2}\ge \binom k2$ for all $i$. Therefore \[ \binom n2 = \sum_{i=1}^m \binom{|A_i|}{2} \ge \sum_{i=1}^m \binom k2 = m\binom k2, \] which rearranges to the claimed bound. $\square$

VERIFICATION.

• Quantifiers: Lemma 665.1 produces a single constant $c=1$ that works for all $n\ge 1$.
• Boundary case $n=1$: With $c=1$ and $A_1=[1]$, the size condition is $1>1-1=0$ which holds; the pair-covering condition is vacuous.
• Intersection condition: With $m=1$ it is vacuous; no hidden requirement is used.
• Ambiguity check: The proof indeed exploits the absence of any requirement excluding $m=1$ or excluding $A_1=[n]$.

FINAL. FULL SOLUTION FULL PROOF.