Erdős Problem #776

Erdős Problem #776

1) ROUND-2 OBJECTIVE

Path (C): obstruction/correction. The round-1 writeup gave a valid but very coarse explicit upper bound. Since February 2026 there is a dedicated paper on this exact Erdős--Trotter problem, so the right Round-2 objective is to replace the crude bound by the current strongest theorem and extract the asymptotic consequence. The problem is still not fully solved, but its first-order growth is now known.

2) Round-1 FOUNDATION USED

I use the following Round-1 facts.

1. For $r>1$, an $r$-multiplicity antichain cannot realize $n-2$ distinct sizes.
2. Round-1 gave an explicit sufficient bound of the form \[ n_0(r)\le 8r+10, \] where $n_0(r)$ is the threshold beyond which $n-3$ distinct sizes are always achievable.

3) NEW INSIGHT / TOOL (ROUND-2)

The new input is the 2026 theorem of He and Tang. Write $g(n,r)$ for the maximum number of distinct set sizes appearing in an $r$-multiplicity antichain on $[n]$, and let $n_0(r)$ be the least integer such that \[ g(n,r)=n-3 \qquad \text{for every } n>n_0(r). \]

Theorem 3.1 (He--Tang, 2026).

1. $n_0(2)=3$ and $n_0(3)=8$.
2. For every integer $r\ge 4$, \[ 2r+2\le n_0(r)\le 2r+2\log_2 r+\log_2\log_2 r+15. \] In particular, \[ n_0(r)=2r+o(r). \]

4) ATTACK PLAN (ROUND-2)

The exact remaining gap after Round-1 was quantitative: Round-1 only showed a coarse explicit upper bound, while the true threshold was unknown. The new plan is:

1. verify that the He--Tang theorem addresses the same threshold $n_0(r)$ as in the original problem;
2. import their current best upper and lower bounds;
3. derive the asymptotic corollary $n_0(r)=2r+o(r)$, which is a genuine first-order resolution of the threshold question.

5) WORK (ROUND-2)

There is one minor convention issue to settle first. The original Erdős--Trotter formulation uses exactly $r$ sets on each occurring level, whereas the Round-1 formulation used at least $r$ sets. These conventions are equivalent for the extremal quantity $g(n,r)$: given an antichain with at least $r$ sets on each occurring level, one may keep an arbitrary subfamily of exactly $r$ sets from each occurring level. The antichain property is preserved and the set of occurring levels is unchanged.

Therefore Theorem 3.1 applies directly to the same threshold parameter in the original problem.

It follows immediately that the current quantitative status is: \[ 2r+2\le n_0(r)\le 2r+2\log_2 r+\log_2\log_2 r+15 \qquad (r\ge 4), \] and also \[ n_0(2)=3,\qquad n_0(3)=8. \]

The most useful derived consequence is the first-order asymptotic.

Corollary 5.1. As $r\to\infty$, \[ \frac{n_0(r)}{r}\to 2. \]

Proof. Divide the bounds of Theorem 3.1 by $r$: \[ 2+\frac{2}{r}\le \frac{n_0(r)}{r}\le 2+\frac{2\log_2 r+\log_2\log_2 r+15}{r}. \] Since $(2\log_2 r+\log_2\log_2 r+15)/r\to 0$, the squeeze theorem gives $n_0(r)/r\to 2$. $\square$

Thus the Round-1 bound $n_0(r)\le 8r+10$ has now been superseded by a near-optimal estimate with the correct leading constant.

6) ADVERSARIAL VERIFICATION

I check the main points where a mismatch could occur.

1. Does Theorem 3.1 use the same notion of multiplicity? Yes, because the exact-$r$ and at-least-$r$ versions are equivalent for $g(n,r)$.

2. Is the asymptotic statement really justified? Yes. The additive error in the upper bound is $2\log_2 r+O(\log_2\log_2 r)=o(r)$.

3. Does this fully solve Problem #776? No. The exact threshold for $r\ge 4$ is still unknown; the remaining gap is logarithmic.

4. Do the small cases fit the threshold definition with the strict inequality $n>n_0(r)$? Yes. The theorem states the exact values of $n_0(2)$ and $n_0(3)$ under that convention.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED)

Problem #776 is not fully closed, but the current state is far stronger than in Round-1: the exact small values are known, \[ n_0(2)=3,\qquad n_0(3)=8, \] and for general $r$ one has \[ n_0(r)=2r+o(r). \] Only a logarithmic gap remains between the best lower and upper bounds.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 85%

9) REFERENCES

[1] T. F. Bloom, Erdős Problem #776, erdosproblems.com/776, accessed 2026-03-07.

[2] Y. He and Q. Tang, An Erdős--Trotter problem on antichains with multiplicity $r$ on each occurring level, arXiv:2602.09803, 2026.

Erdős Problem #776: independent continuation

Date: 23 September 2026. Source versions read in full: 776.tex in gpt_pro_5.4.

1) OBJECTIVE AND VERIFIED BACKGROUND

The problem asks for the threshold beyond which an antichain can occupy $n-3$ levels with $r$ sets on each level. He--Tang's revised primary paper confirms $n_0(2)=3$, $n_0(3)=8$, and $n_0(r)=2r+o(r)$. These are existing results. Below is a self-contained structural explanation for the leading linear obstruction, weaker than their sharp lower bound.

2) EXTREME LEVELS FORCE STARS

Suppose $r\ge5$, $n\ge r+1$, and an antichain occupies $n-3$ levels with exactly $r$ sets on each. If it includes $r$ singletons, every larger member avoids their $r$ elements, so all occupied ranks are at most $n-r$. It then occupies at most $n-r<n-3$ ranks, a contradiction. Complementation excludes rank $n-1$ as well. Empty and full sets cannot occur with multiplicity $r>1$. Hence the occupied ranks are exactly $2,\ldots,n-2$. Let $E$ be the family of its $r$ two-element sets and $F$ the complements of its $r$ sets of size $n-2$. Incomparability says every $e\in E$ meets every $f\in F$. If $E$ contains two disjoint edges, there are only four two-element sets meeting both, contrary to $|F|\ge5$. Thus $E$ is pairwise intersecting. A pairwise-intersecting family of at least four edges is a star: two edges $\{c,u\},\{c,v\}$ force an edge missing $c$ to be $\{u,v\}$, after which no fourth edge is possible. Similarly $F$ is a star. Their centres must coincide. If their centres were $c\ne d$, take an edge of the first star not containing $d$; only two edges of the star at $d$ can meet it, contradicting $r\ge5$.

3) A SELF-CONTAINED NECESSARY SIZE BOUND

Write $E=\{\{c,u\}:u\in U\}$ and $F=\{\{c,v\}:v\in V\}$, with $|U|=|V|=r$. Any intermediate member containing $c$ avoids all of $U$; any member missing $c$ contains all of $V$. In particular every member of rank $r-1$ contains $c$ and avoids $U$, so there are at most \[ \binom{n-r-1}{r-2} \] such members. For $r+1\le n\le2r$, this is at most $r-1$, whereas rank $r-1$ must contain $r$ members. Hence necessarily $n\ge2r+1$. This is weaker than the established threshold lower bound, but identifies the cross-intersecting-star structure responsible for the coefficient two.

7) FINAL

UNRESOLVED. No exact threshold for general $r$ is obtained. The source's asymptotic conclusion remains an attributed result, and the argument here is a separate elementary partial analysis. Primary source checked: He and Tang, version 2 (21 March 2026), https://arxiv.org/abs/2602.09803v2.

8) COMPLETION ESTIMATE

COMPLETION: 15% This is a subjective estimate of progress toward the entire stated problem, not a probability that the conjecture or an unverified proof is correct.

Problem 776: many sizes in an antichain with multiplicities

1) Formal restatement

Let $\mathcal{F}\subseteq 2^{[n]}$ be an antichain. Fix $r\in\mathbb{N}$ and assume that for every size $k$ occurring in $\mathcal{F}$, there are at least $r$ sets in $\mathcal{F}$ of size $k$. How large can $|\{|A|:A\in\mathcal{F}\}|$ be? For $r=1$ the maximum is $n-2$. For $r>1$ it is stated that $n-2$ is impossible but $n-3$ is achievable for large $n$. Question: determine/estimate how large $n$ must be (as a function of $r$) to guarantee an example with $n-3$ distinct sizes.

2) Quick literature/context check (no more than 8 lines)

• For $r=1$, there are explicit constructions with $n-2$ distinct sizes.
• For $r>1$, one loses at least one additional size (so $n-2$ is impossible).
• The quantitative threshold $n(r)$ for achieving $n-3$ sizes is the open part.

3) Attack plan

• Prove $n-2$ distinct sizes are impossible when $r>1$ by showing sizes $1$ and $n-1$ cannot coexist.
• Give an explicit construction achieving sizes $2,3,\dots,n-2$ (i.e. $n-3$ sizes) once $n$ is sufficiently large in terms of $r$; this yields an explicit upper bound $n(r)\le Cr+O(1)$.

4) Work

Impossibility of $n-2$ sizes for $r>1$.

In any antichain with more than one set, sizes $0$ and $n$ are absent (since $\varnothing\subseteq A\subseteq [n]$ for all $A$). Thus achieving $n-2$ sizes would force all but one of the sizes $1,2,\dots,n-1$ to occur, in particular both sizes $1$ and $n-1$.

If $r>1$, the presence of size $1$ means $\mathcal{F}$ contains two distinct singletons $\{a\}$ and $\{b\}$. Any $(n-1)$-set omits exactly one element, hence contains at least one of $a,b$. So any $(n-1)$-set $X\in\mathcal{F}$ would contain $\{a\}$ or $\{b\}$, contradicting antichain-ness. Therefore sizes $1$ and $n-1$ cannot both occur, and $n-2$ distinct sizes are impossible for $r>1$.

A linear-in-$r$ construction achieving $n-3$ sizes.

We construct an antichain $\mathcal{F}\subseteq 2^{[n]}$ with at least $r$ sets of each size $2,3,\dots,n-2$, provided $n\ge 8r+10$. Set $t=\lfloor n/2\rfloor$.

Step 1: build an intersecting antichain $\mathcal{G}$ with sizes $2,3,\dots,t$. Use a common element $1$. Let \[ A=\{2,3,\dots,r+1\},\qquad C=\{r+2,\dots,r+t-1\}, \] and let $B=\{r+t,\dots,n\}$ be the remaining elements. Then $|C|=t-2$ and $|B|=b=n-r-t+1$.

Define $r$ size-2 sets: \[ G_{2,i}=\{1,i+1\}\qquad(i=1,\dots,r). \] For each $s\in\{3,\dots,t\}$, let $F_s=\{r+2,\dots,r+s-2\}\subseteq C$ (so $|F_s|=s-3$). Assign to each pair $(s,i)$ (with $3\le s\le t$ and $1\le i\le r$) a distinct label $P_{s,i}\in\binom{B}{2}$, and set \[ G_{s,i}=\{1\}\cup P_{s,i}\cup F_s. \] Let $\mathcal{G}=\{G_{s,i}:2\le s\le t,\ 1\le i\le r\}$.

Step 2: $\mathcal{G}$ is an intersecting antichain. All sets contain $1$, so $\mathcal{G}$ is intersecting. No size-2 set $G_{2,i}$ is contained in any $G_{s,i'}$ with $s\ge 3$, because $i+1\in A$ and all $G_{s,i'}$ (for $s\ge 3$) use only $\{1\}\cup B\cup C$, avoiding $A\setminus\{1\}$. If $s,s'\ge 3$ and $G_{s,i}\subseteq G_{s',i'}$, then their intersections with $B$ satisfy $P_{s,i}\subseteq P_{s',i'}$, forcing $P_{s,i}=P_{s',i'}$, contradicting distinctness. Hence $\mathcal{G}$ is an antichain.

Step 3: add complements. Let \[ \mathcal{F}=\mathcal{G}\ \cup\ \{[n]\setminus G: G\in\mathcal{G}\}. \] Because $\mathcal{G}$ is intersecting, no $G\in\mathcal{G}$ is contained in the complement of another member, so $\mathcal{F}$ is still an antichain. The sizes appearing in $\mathcal{F}$ are exactly $2,3,\dots,n-2$, i.e. $n-3$ distinct sizes, and each such size occurs at least $r$ times (from $\mathcal{G}$ or from complements).

Step 4: enough labels. We need $\binom{b}{2}\ge r(t-2)$ to assign distinct pairs $P_{s,i}$. For $n\ge 8r+10$ one checks that $b=n-r-t+1\ge 3r+6$ and $\binom{b}{2}$ dominates $r(t-2)$, so the labeling is feasible. Thus $n(r)\le 8r+10$ is an explicit sufficient bound.

5) Verification

• The $n-2$ impossibility uses only $r>1$: two singletons force containment into any $(n-1)$-set.
• The construction is checked by separating (i) size-2 sets using reserved elements, and (ii) larger sets distinguished by unique 2-element labels in $B$.
• Intersecting $\mathcal{G}$ guarantees no cross-containment when adding complements.

6) Final (exactly one label and one sub-label)

LABEL: UNRESOLVED.
SUBLABEL: Proved $n-2$ sizes impossible for $r>1$; gave an explicit construction showing $n(r)\le 8r+10$ suffices for $n-3$ sizes.

7) Completion estimate

Determining the true threshold $n(r)$ would require either improved constructions (reducing the constant $8$) or nontrivial lower bounds showing $n$ must grow at least linearly (or faster) in $r$.