Reused writeup on Math-909 (gpt pro 5.2)

Erdős Problem 701 --- collection record

PROVENANCE AND STATUS

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

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/701.tex.

REUSED SOURCE 1

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

Erdős Problem #701

FORMAL RESTATEMENT

Let $[n]:=\{1,2,\dots,n\}$. A family $\mathcal{F}\subseteq 2^{[n]}$ is a down-set (hereditary family) if whenever $A\in\mathcal{F}$ and $B\subseteq A$, then $B\in\mathcal{F}$. A subfamily $\mathcal{F}'\subseteq \mathcal{F}$ is intersecting if every member of $\mathcal{F}'$ is nonempty and for all distinct $A,B\in\mathcal{F}'$ we have $A\cap B\ne\varnothing$.

Conjecture (Chvátal): For every down-set $\mathcal{F}\subseteq 2^{[n]}$ there exists an element $x\in [n]$ such that for every intersecting subfamily $\mathcal{F}'\subseteq\mathcal{F}$, \[|\mathcal{F}'|\le |\{A\in\mathcal{F}: x\in A\}|. \]

QUICK LITERATURE/CONTEXT CHECK

The problem text states Chvátal proved the conjecture under a stronger closure condition, and that special cases have been proved (e.g. covering number $2$). A 2022/2023 paper by Frankl--Kupavskii establishes the covering number $2$ case. I do not see a claim that the general conjecture is fully resolved as of late 2025.

ATTACK PLAN

• Proof track: prove the conjecture in elementary special cases by structural decomposition via maximal elements of the down-set.
• Reality check: brute-force all down-sets on $[n]$ for small $n$ and verify the conjecture by maximum-clique computation in the intersection graph.

WORK

Lemma 701.1 (unique maximal set case). Suppose $\mathcal{F}\subseteq 2^{[n]}$ is a down-set with a unique maximal element (under inclusion) $M\in\mathcal{F}$. Then the conjecture holds, and in fact for any $x\in M$ and any intersecting $\mathcal{F}'\subseteq\mathcal{F}$ one has \[|\mathcal{F}'|\le 2^{|M|-1}=|\{A\in\mathcal{F}: x\in A\}|. \]

Proof. First we show $\mathcal{F}=2^{M}$. Let $A\in\mathcal{F}$. If $A\nsubseteq M$, then $A$ contains some element outside $M$. Any superset $B\supseteq A$ would also contain that element and hence cannot be a subset of $M$. But $M$ is the unique maximal element of $\mathcal{F}$, so $A$ must have a chain of strict supersets in $\mathcal{F}$ ending at $M$, which is impossible if $A\nsubseteq M$. Therefore every $A\in\mathcal{F}$ satisfies $A\subseteq M$. Since $\mathcal{F}$ is a down-set and $M\in\mathcal{F}$, it contains all subsets of $M$, hence $\mathcal{F}=2^{M}$.

Now let $\mathcal{F}'\subseteq 2^{M}$ be intersecting (in particular, all members are nonempty). For each subset $A\subseteq M$ let $\overline{A}:=M\setminus A$. The map $A\mapsto \overline{A}$ is a fixed-point-free involution on $2^{M}$, pairing each $A$ with its complement. In an intersecting family, one cannot contain both $A$ and $\overline{A}$, because $A\cap \overline{A}=\varnothing$. Therefore at most one set from each complementary pair can lie in $\mathcal{F}'$, so $|\mathcal{F}'|\le 2^{|M|-1}$. Finally, for any fixed $x\in M$, exactly half of the subsets of $M$ contain $x$, so $|\{A\subseteq M: x\in A\}|=2^{|M|-1}$. This is exactly the required bound. $\square$

Lemma 701.2 (pairwise disjoint maximal sets case). Let $\mathcal{F}\subseteq 2^{[n]}$ be a down-set, and let $\mathcal{G}$ be the set of maximal elements of $\mathcal{F}$. Assume that the members of $\mathcal{G}$ are pairwise disjoint. Then the conjecture holds.

Proof. For each $M\in\mathcal{G}$, let $\mathcal{F}_M:=2^{M}$. Because $\mathcal{F}$ is a down-set, every set in $\mathcal{F}$ is a subset of some maximal element, so \[\mathcal{F}=\bigcup_{M\in\mathcal{G}} \mathcal{F}_M. \] Moreover, if $M\ne M'$ are distinct maximal sets, then $M\cap M'=\varnothing$ by hypothesis, hence any $A\subseteq M$ and $B\subseteq M'$ are disjoint. Therefore any intersecting subfamily $\mathcal{F}'\subseteq\mathcal{F}$ can involve sets from at most one block $\mathcal{F}_M$: if it contained both some $A\subseteq M$ and some $B\subseteq M'$ with $M\ne M'$, we would have $A\cap B=\varnothing$, contradicting intersecting. Thus there is some $M\in\mathcal{G}$ such that $\mathcal{F}'\subseteq 2^{M}$. Pick any $x\in M$. Then by Lemma 701.1 applied to the down-set $2^{M}$, we have $|\mathcal{F}'|\le 2^{|M|-1}$. On the other hand, within the whole family $\mathcal{F}$, the star at $x$ consists precisely of the subsets of $M$ containing $x$ (no other maximal block contains $x$), so $|\{A\in\mathcal{F}: x\in A\}|=2^{|M|-1}$. Hence $|\mathcal{F}'|\le |\{A\in\mathcal{F}: x\in A\}|$, proving the conjecture in this case. $\square$

FAST REALITY CHECK (computation). For $n\le 5$ I enumerated all down-sets $\mathcal{F}\subseteq 2^{[n]}$ (equivalently all antichains of maximal elements; there are $3,6,20,168,7581$ of them for $n=1,2,3,4,5$) and for each:

• computed $\alpha(\mathcal{F})=$ the maximum size of an intersecting subfamily (using a maximum-clique algorithm on the intersection graph of nonempty members), and
• computed $\max_{x\in[n]} |\{A\in\mathcal{F}: x\in A\}|$.

In every case for $n\le 5$ I found $\alpha(\mathcal{F})\le \max_x |\{A\in\mathcal{F}: x\in A\}|$, i.e. the conjecture holds for all down-sets on ground sets of size at most $5$.

VERIFICATION

• Definition check: I excluded the empty set from intersecting subfamilies (otherwise the family $\{\varnothing\}$ would create a degenerate obstruction).
• Lemma 701.1: checked the argument that unique maximal element forces $\mathcal{F}=2^M$.
• Computation: verified enumeration count for antichains on $[5]$ equals $7581$ and ensured the clique search only used nonempty sets.

FINAL

UNRESOLVED.

1. (i) Strongest proved partial results here:
   • Conjecture holds when $\mathcal{F}$ has a unique maximal set (Lemma 701.1).
   • Conjecture holds when maximal sets are pairwise disjoint (Lemma 701.2).
   • Exhaustive verification for all down-sets on $[n]$ for $n\le 5$.
2. (ii) First gap: extend the argument beyond these decomposable cases, i.e. handle overlapping maximal sets without additional structural assumptions.
3. (iii) Top 3 next moves:
   1. Try to prove the conjecture for down-sets with exactly two maximal elements with nontrivial overlap by an explicit injection/compression argument.
   2. Develop an induction on $n$ using links/deletions: relate $\mathcal{F}$ to the down-sets $\{A\in\mathcal{F}: x\notin A\}$ and $\{A\setminus\{x\}: x\in A\in\mathcal{F}\}$.
   3. Search for a minimal counterexample by computation for $n=6$ restricted to families with small numbers of maximal elements (since enumerating all down-sets is infeasible at $n=6$).
4. (iv) Minimal counterexample structure: a smallest counterexample would likely be a down-set on small $n$ with several overlapping maximal sets arranged so that every star is significantly smaller than a carefully constructed intersecting subfamily; overlaps must be rich enough to allow a large intersecting family but balanced enough to keep all stars small.

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.