Reused writeup on Math-976 (gpt pro 5.2)

Erdős Problem 901 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

1) FORMAL RESTATEMENT

An $n$-uniform hypergraph $H=(V,E)$ has vertex set $V$ and edge set $E\subseteq\binom{V}{n}$. A 2-coloring of $V$ is proper if no edge is monochromatic. A hypergraph is 2-colorable iff it admits a proper 2-coloring (this is also called Property B).

Let $m(n)$ be the minimum number of edges in an $n$-uniform hypergraph which is not 2-colorable (equivalently, which is 3-chromatic). Estimate $m(n)$ as $n\to\infty$.

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement records known bounds: \[2^n\ll m(n)\ll n^2 2^n\] (Erdős), and improvements of the lower bound up to roughly $\sqrt{n/\log n}\,2^n$. Known exact values recorded are $m(2)=3$, $m(3)=7$, $m(4)=23$.

3) ATTACK PLAN

• Reprove the standard probabilistic-method lower bound $m(n)\ge 2^{n-1}$.
• Give a self-contained probabilistic existence proof of an upper bound of shape $m(n)\le C n^2 2^n$.
• Sanity-check $n=3$ by verifying the Fano plane is not 2-colorable.

4) WORK

PHASE 1 — FAST REALITY CHECK (small cases).

For $n=3$, the classical Fano plane has 7 vertices and 7 edges: \[ E=\{012,034,056,135,146,236,245\}\ \text{(vertices }0,\dots,6\text{).} \] A brute-force check over all $2^7$ 2-colorings finds no proper coloring, so this 3-uniform hypergraph is not 2-colorable. Moreover, removing any one edge makes it 2-colorable (edge-minimal within this 7-vertex structure).

Problem-specific lemmas (Erdős-style exponential lower bound and a matching existence upper bound).

Lemma 901.1 (First-moment lower bound). If an $n$-uniform hypergraph $H$ has $m$ edges and $m<2^{n-1}$, then $H$ is 2-colorable. In particular, \[ m(n)\ge 2^{n-1}. \]

Proof. Color each vertex independently red/blue with probability $1/2$. For a fixed edge $e$ of size $n$, the probability it is monochromatic is \[\mathbb{P}(e\text{ all red})+\mathbb{P}(e\text{ all blue})=2\cdot 2^{-n}=2^{1-n}. \] Let $X$ be the number of monochromatic edges. By linearity of expectation, \[ \mathbb{E}X = m\cdot 2^{1-n}. \] If $m<2^{n-1}$ then $\mathbb{E}X<1$. Since $X$ is a nonnegative integer-valued random variable, there must exist a coloring with $X=0$, i.e. a proper 2-coloring. Thus any non-2-colorable $n$-uniform hypergraph must have $m\ge 2^{n-1}$ edges. $\square$

Lemma 901.2 (Union bound upper bound $m(n)\ll n^2 2^n$). For every $n\ge 2$ there exists an $n$-uniform hypergraph with at most $C\,n^2 2^n$ edges that is not 2-colorable, for an absolute constant $C$. Consequently $m(n)\ll n^2 2^n$.

Proof. Fix $n\ge 2$ and set $v:=n^2$ vertices. Let $\mathcal{U}:=\binom{[v]}{n}$ be the family of all $n$-subsets. Choose $m$ edges uniformly at random without replacement from $\mathcal{U}$.

Fix a 2-coloring of $[v]$ with red class size $r$ and blue class size $v-r$. Let $M(r)$ be the number of monochromatic $n$-sets under this coloring: \[ M(r)=\binom{r}{n}+\binom{v-r}{n}. \]

Step 1: a uniform lower bound on $M(r)$. The function $g(t)=\binom{t}{n}$ (for real $t\ge n-1$) has nonnegative second finite differences in $t$ (discrete convexity), and one checks directly that the sequence $\binom{t}{n}$ is convex in integer $t$. Therefore $M(r)$ is minimized when $r$ is as close to $v/2$ as possible, hence \[ M(r)\ge 2\binom{\lfloor v/2\rfloor}{n} \ge 2\binom{v/2 -1}{n} \quad (v\ge 2n). \] (For $v=n^2\ge 2n$ when $n\ge 2$.)

Step 2: convert to a monochromatic-edge fraction. Let \[ \delta := \frac{2\binom{v/2 -1}{n}}{\binom{v}{n}}. \] Then for every coloring, at least a $\delta$ fraction of all $n$-sets are monochromatic. We lower bound $\delta$. Write falling factorials $(x)_n=x(x-1)\cdots(x-n+1)$. Then \[ \frac{\binom{v/2 -1}{n}}{\binom{v}{n}} =\frac{(v/2-1)_n}{(v)_n} =\prod_{i=0}^{n-1}\frac{v/2-1-i}{v-i}. \] Since $v=n^2$ and $0\le i\le n-1$, we have $v-i\le v$ and $v/2-1-i \ge v/2 - n$. Thus each factor is at least \[ \frac{v/2-n}{v}=\frac12-\frac{n}{v}=\frac12-\frac1n. \] For $n\ge 2$, $\frac12-\frac1n\ge \frac14$, so \[ \frac{\binom{v/2 -1}{n}}{\binom{v}{n}} \ge \left(\frac14\right)^n = 2^{-2n}. \] Hence $\delta\ge 2\cdot 2^{-2n}=2^{1-2n}$.

Step 3: union bound over all colorings. For a fixed coloring, the probability that none of the $m$ chosen edges is monochromatic is at most \[ \left(1-\delta\right)^m \le \exp(-\delta m). \] There are $2^v$ colorings, so by the union bound the probability the random hypergraph is 2-colorable is at most \[ 2^v\exp(-\delta m). \] Choose \[ m:= \left\lceil \frac{(v+1)\log 2}{\delta}\right\rceil. \] Then $2^v\exp(-\delta m)\le e^{-\log 2}<1$, so with positive probability the random hypergraph is not 2-colorable. Therefore there exists a non-2-colorable $n$-uniform hypergraph on $v=n^2$ vertices with at most $m$ edges.

Finally, using $\delta\ge 2^{1-2n}$ and $v=n^2$, \[ m \le \frac{(n^2+1)\log 2}{2^{1-2n}} +1 \le C\, n^2 2^{2n} \] for an absolute constant $C$. This is weaker than the stated $n^2 2^n$ bound, but it is a fully self-contained probabilistic existence bound of the same qualitative form “polynomial times exponential”. $\square$

Remark. The bound obtained above is $\ll n^2 4^n$ due to a crude estimate for $\delta$; sharpening the ratio $\binom{v/2}{n}/\binom{v}{n}\approx 2^{-n}$ recovers the classical $\ll n^2 2^n$ scale.

5) VERIFICATION

• Lemma 901.1: expectation computation uses only independence and the exact probability a size-$n$ edge is monochromatic under a random 2-coloring.
• Lemma 901.2: the convexity/minimization of $\binom{r}{n}+\binom{v-r}{n}$ at $r\approx v/2$ is standard; the product bound for $\delta$ is crude but valid for $v=n^2$.
• Constants: the final bound derived is $\ll n^2 4^n$ (not $n^2 2^n$) because of the crude $\delta\ge 2^{1-2n}$ estimate. This is honestly weaker than the problem statement’s quoted upper bound.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. A fully self-contained lower bound is $m(n)\ge 2^{n-1}$ (Lemma 901.1). A self-contained existence upper bound via a crude union bound gives $m(n)\ll n^2 4^n$ (Lemma 901.2).

(ii) First gap (crisp). Close the exponential gap: prove $m(n)=\Theta(n\,2^n)$ (as speculated in the statement) or determine the correct polynomial factor multiplying $2^n$.

(iii) Top 3 next moves.

1. Sharpen Lemma 901.2 by optimizing the vertex count $v$ and using the sharp estimate $\binom{v/2}{n}/\binom{v}{n}\approx 2^{-n}$ to recover an explicit $\ll n^2 2^n$ upper bound with full constants.
2. Investigate extremal/algorithmic approaches (e.g. entropy compression) producing non-2-colorable hypergraphs with $\sim n2^n$ edges.
3. Computational: verify small $n$ values by exhaustive search (or SAT) to better guess the correct asymptotic constant and the right polynomial factor.

(iv) Minimal counterexample structure (if $m(n)$ is not $\Theta(n2^n)$). If $m(n)$ were significantly smaller than $n2^n$, one would expect a highly structured hypergraph with very few edges but still forcing a monochromatic edge in every 2-coloring; such a structure would likely resemble a sparse “design-like” configuration where every balanced coloring is hit many times.

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.