Erdős Problem #500

Erdős Problem 500 --- collection record

PROVENANCE AND STATUS

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

REUSED SOURCE 1

1) FORMAL RESTATEMENT

For an integer $n\ge 1$, let $H=(V,E)$ be a $3$-uniform hypergraph on $\lvert V\rvert=n$, meaning $E\subseteq \binom{V}{3}$. Let $K_4^3$ denote the $3$-uniform complete hypergraph on $4$ vertices, i.e. a $4$-vertex set $S\subseteq V$ for which all $\binom{4}{3}=4$ triples in $\binom{S}{3}$ belong to $E$. Define \[ \mathrm{ex}_3(n,K_4^3)\;:=\;\max\{\lvert E\rvert:\; H\text{ is a $3$-uniform hypergraph on $n$ vertices containing no }K_4^3\}. \] The problem asks for $\mathrm{ex}_3(n,K_4^3)$ (exactly, or at least asymptotically as $n\to\infty$).

Edge cases: for $n\le 3$ there is no $4$-set, hence every $3$-graph is $K_4^3$-free and $\mathrm{ex}_3(n,K_4^3)=\binom{n}{3}$.

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement records Turán's construction giving \[\mathrm{ex}_3(n,K_4^3)\ge \left(\frac{5}{9}+o(1)\right)\binom{n}{3},\] and an upper bound $\mathrm{ex}_3(n,K_4^3)\le 0.5611666\binom{n}{3}$ (Razborov, as quoted in the problem file). I do not use any external results beyond what is explicitly stated there.

3) ATTACK PLAN

Proof track: verify Turán's construction is $K_4^3$-free and count its edges (gives a rigorous lower bound). Then sanity-check small $n$ by exhaustive computation.

Disproof track: try to beat density $5/9$ by small-$n$ search and/or by perturbing the 3-part construction; look for a $K_4^3$-free configuration with higher density at small $n$.

4) WORK

Definition (Turán 3-part construction). Fix a partition $V=X_1\sqcup X_2\sqcup X_3$ (indices modulo $3$, so $X_4=X_1$). Define a $3$-graph $T(V)$ with edge set $E(T)$ consisting of all triples $\{a,b,c\}\subseteq V$ of either type:

$1$ $1,1,1$-type: one vertex in each $X_1,X_2,X_3$; or

$2$ cyclic $2,1$-type: two vertices in $X_i$ and one vertex in $X_{i+1}$ for some $i\in\{1,2,3\}$.

Lemma 500.1 (The Turán construction is $K_4^3$-free). For every partition $V=X_1\sqcup X_2\sqcup X_3$, the $3$-graph $T(V)$ contains no copy of $K_4^3$.

Proof. Let $S\subseteq V$ be any $4$-element set. We show that at least one of the four triples in $\binom{S}{3}$ is not an edge of $T(V)$.

Let $(a_1,a_2,a_3)$ be the occupancy numbers where $a_i:=\lvert S\cap X_i\rvert$ so $a_1+a_2+a_3=4$.

Case 1: $(4,0,0)$ up to permutation. Then some part, say $X_1$, contains all four vertices. Every triple in $\binom{S}{3}$ lies entirely in $X_1$, hence is of type $(3,0,0)$ and is not allowed by the definition of $E(T)$ (which allows only types $(1,1,1)$ and $(2,1,0)$ with a cyclic orientation). Therefore $S$ does not span $K_4^3$.

Case 2: $(3,1,0)$ up to permutation. Say $S$ has three vertices in $X_1$ and one in $X_2$. Then the triple consisting of the three vertices in $X_1$ is again of type $(3,0,0)$ and is not an edge. Hence $S$ does not span $K_4^3$.

Case 3: $(2,2,0)$ up to permutation. Say $S$ has two vertices in $X_1$ and two in $X_2$. The four triples in $\binom{S}{3}$ consist of: - two triples of type $(2\text{ in }X_1,\;1\text{ in }X_2)$, and - two triples of type $(1\text{ in }X_1,\;2\text{ in }X_2)$. By definition, $E(T)$ includes triples with two vertices in $X_i$ and one in $X_{i+1}$, but excludes triples with two vertices in $X_{i+1}$ and one in $X_i$. Thus, among these four triples, exactly one of the two types can be present (depending on the cyclic direction), and the other type is absent. Hence $S$ does not span $K_4^3$.

Case 4: $(2,1,1)$ up to permutation. Say $S$ has two vertices in $X_1$, one vertex in $X_2$, and one vertex in $X_3$. Label the two vertices in $X_1$ by $u,v$, the vertex in $X_2$ by $w$, and the vertex in $X_3$ by $z$. The four triples in $\binom{S}{3}$ are \[\{u,v,w\},\ \{u,v,z\},\ \{u,w,z\},\ \{v,w,z\}. \] The last two triples $\{u,w,z\}$ and $\{v,w,z\}$ have one vertex in each part, hence are of type $(1,1,1)$ and therefore belong to $E(T)$. Among the first two triples, $\{u,v,w\}$ has type $(2\text{ in }X_1,\;1\text{ in }X_2)$, while $\{u,v,z\}$ has type $(2\text{ in }X_1,\;1\text{ in }X_3)$. Exactly one of $X_2$ or $X_3$ equals $X_{1+1}$ in the cyclic order, so by definition of $E(T)$ exactly one of these two triples is present and the other is absent. Therefore at least one triple among the four is missing, so $S$ does not span $K_4^3$.

These cases exhaust all possibilities for $(a_1,a_2,a_3)$. Hence no $4$-set $S$ spans all four triples, i.e. $T(V)$ is $K_4^3$-free. $\square$

Lemma 500.2 (Edge count; asymptotic density $5/9$ for equal parts). Assume $n=3m$ and $\lvert X_1\rvert=\lvert X_2\rvert=\lvert X_3\rvert=m$. Then \[ \lvert E(T)\rvert = m^3 + 3\binom{m}{2}m = \frac{m^2}{2}(5m-3) = \left(\frac{5}{9}+O\left(\frac{1}{n}\right)\right)\binom{n}{3}. \]

Proof. Count edges by type.

$1$ Edges with one vertex in each part: choose one from each part in $m^3$ ways.

$2$ Cyclic $2,1$-edges: for each $i\in\{1,2,3\}$, choose $2$ vertices from $X_i$ and $1$ vertex from $X_{i+1}$. This gives $\binom{m}{2}\cdot m$ edges for each $i$, hence $3\binom{m}{2}m$ in total.

Summing gives \[ \lvert E(T)\rvert = m^3 + 3\binom{m}{2}m = m^3 + 3\cdot \frac{m(m-1)}{2}\cdot m = \frac{m^2}{2}(5m-3). \] Also $\binom{n}{3}=\binom{3m}{3} = \frac{(3m)(3m-1)(3m-2)}{6} = \frac{9}{2}m^3 + O(m^2)$. Therefore \[ \frac{\lvert E(T)\rvert}{\binom{n}{3}} = \frac{\frac{5}{2}m^3 + O(m^2)}{\frac{9}{2}m^3 + O(m^2)} = \frac{5}{9} + O\left(\frac{1}{m}\right) = \frac{5}{9} + O\left(\frac{1}{n}\right). \] $\square$

FAST REALITY CHECK (exact small $n$). I exhaustively searched all $3$-graphs on $n\le 6$ vertices and found: \[ \mathrm{ex}_3(1,K_4^3)=0,\ \mathrm{ex}_3(2,K_4^3)=0,\ \mathrm{ex}_3(3,K_4^3)=1,\ \mathrm{ex}_3(4,K_4^3)=3,\ \mathrm{ex}_3(5,K_4^3)=7,\ \mathrm{ex}_3(6,K_4^3)=14. \] Moreover, the Turán construction achieves $7$ edges at $n=5$ (parts $2,2,1$) and $14$ edges at $n=6$ (parts $2,2,2$), so it is optimal for these $n$.

5) VERIFICATION

Quantifiers/edge cases: For $n\le 3$, the definition of $K_4^3$ makes the forbidden configuration impossible, so $\mathrm{ex}_3(n,K_4^3)=\binom{n}{3}$; this matches the computed values $0,0,1$.

Lemma checks: Lemma 500.1 enumerates all possible $4$-vertex distributions among three parts; in each case, an explicit missing triple is identified.

Computation check: Exhaustive enumeration for $n=6$ checks $2^{\binom{6}{3}}=2^{20}=1{,}048{,}576$ hypergraphs, feasible and exact.

6) FINAL UNRESOLVED

(i) Strongest proved partial result here: Turán's 3-part construction is $K_4^3$-free and has edge density $\frac{5}{9}+O(1/n)$ (Lemmas 500.1--500.2). Exact values for $n\le 6$ are computed and match this construction.

(ii) First gap (crisp): Prove that every $K_4^3$-free $3$-graph on $n$ vertices satisfies $\lvert E\rvert \le \left(\frac{5}{9}+o(1)\right)\binom{n}{3}$, i.e. the Turán construction is asymptotically optimal.

(iii) Top 3 next moves: 1. Compute $\mathrm{ex}_3(n,K_4^3)$ for $7\le n\le 10$ via ILP/branch-and-bound to test stability and see whether extremals resemble the 3-part construction. 2. Prove a stability statement: if a $K_4^3$-free $3$-graph has density $\ge 5/9-\varepsilon$, then its vertex set admits a near-balanced 3-partition with most edges of the Turán types. 3. Derive a clean analytic inequality bounding edge density in terms of the densities of the three parts (a first step toward a purely combinatorial upper bound).

(iv) Minimal counterexample structure (if $5/9$ is not optimal): a $K_4^3$-free $3$-graph with density $>5/9$ would likely require a structured partition into three (or more) parts with a modified allowed-type rule, while still avoiding the $(2,1,1)$ obstruction that forced a missing triple in Lemma 500.1.

COMPLETION ESTIMATE

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

1) FORMAL RESTATEMENT

For an integer $n\ge 1$, let $H=(V,E)$ be a $3$-uniform hypergraph on $\lvert V\rvert=n$, meaning $E\subseteq \binom{V}{3}$. Let $K_4^3$ denote the $3$-uniform complete hypergraph on $4$ vertices, i.e. a $4$-vertex set $S\subseteq V$ for which all $\binom{4}{3}=4$ triples in $\binom{S}{3}$ belong to $E$. Define \[ \mathrm{ex}_3(n,K_4^3)\;:=\;\max\{\lvert E\rvert:\; H\text{ is a $3$-uniform hypergraph on $n$ vertices containing no }K_4^3\}. \] The problem asks for $\mathrm{ex}_3(n,K_4^3)$ (exactly, or at least asymptotically as $n\to\infty$).

Edge cases: for $n\le 3$ there is no $4$-set, hence every $3$-graph is $K_4^3$-free and $\mathrm{ex}_3(n,K_4^3)=\binom{n}{3}$.

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement records Turán's construction giving \[\mathrm{ex}_3(n,K_4^3)\ge \left(\frac{5}{9}+o(1)\right)\binom{n}{3},\] and an upper bound $\mathrm{ex}_3(n,K_4^3)\le 0.5611666\binom{n}{3}$ (Razborov, as quoted in the problem file). I do not use any external results beyond what is explicitly stated there.

3) ATTACK PLAN

Proof track: verify Turán's construction is $K_4^3$-free and count its edges (gives a rigorous lower bound). Then sanity-check small $n$ by exhaustive computation.

Disproof track: try to beat density $5/9$ by small-$n$ search and/or by perturbing the 3-part construction; look for a $K_4^3$-free configuration with higher density at small $n$.

4) WORK

Definition (Turán 3-part construction). Fix a partition $V=X_1\sqcup X_2\sqcup X_3$ (indices modulo $3$, so $X_4=X_1$). Define a $3$-graph $T(V)$ with edge set $E(T)$ consisting of all triples $\{a,b,c\}\subseteq V$ of either type:

$1$ $1,1,1$-type: one vertex in each $X_1,X_2,X_3$; or

$2$ cyclic $2,1$-type: two vertices in $X_i$ and one vertex in $X_{i+1}$ for some $i\in\{1,2,3\}$.

Lemma 500.1 (The Turán construction is $K_4^3$-free). For every partition $V=X_1\sqcup X_2\sqcup X_3$, the $3$-graph $T(V)$ contains no copy of $K_4^3$.

Proof. Let $S\subseteq V$ be any $4$-element set. We show that at least one of the four triples in $\binom{S}{3}$ is not an edge of $T(V)$.

Let $(a_1,a_2,a_3)$ be the occupancy numbers where $a_i:=\lvert S\cap X_i\rvert$ so $a_1+a_2+a_3=4$.

Case 1: $(4,0,0)$ up to permutation. Then some part, say $X_1$, contains all four vertices. Every triple in $\binom{S}{3}$ lies entirely in $X_1$, hence is of type $(3,0,0)$ and is not allowed by the definition of $E(T)$ (which allows only types $(1,1,1)$ and $(2,1,0)$ with a cyclic orientation). Therefore $S$ does not span $K_4^3$.

Case 2: $(3,1,0)$ up to permutation. Say $S$ has three vertices in $X_1$ and one in $X_2$. Then the triple consisting of the three vertices in $X_1$ is again of type $(3,0,0)$ and is not an edge. Hence $S$ does not span $K_4^3$.

Case 3: $(2,2,0)$ up to permutation. Say $S$ has two vertices in $X_1$ and two in $X_2$. The four triples in $\binom{S}{3}$ consist of: - two triples of type $(2\text{ in }X_1,\;1\text{ in }X_2)$, and - two triples of type $(1\text{ in }X_1,\;2\text{ in }X_2)$. By definition, $E(T)$ includes triples with two vertices in $X_i$ and one in $X_{i+1}$, but excludes triples with two vertices in $X_{i+1}$ and one in $X_i$. Thus, among these four triples, exactly one of the two types can be present (depending on the cyclic direction), and the other type is absent. Hence $S$ does not span $K_4^3$.

Case 4: $(2,1,1)$ up to permutation. Say $S$ has two vertices in $X_1$, one vertex in $X_2$, and one vertex in $X_3$. Label the two vertices in $X_1$ by $u,v$, the vertex in $X_2$ by $w$, and the vertex in $X_3$ by $z$. The four triples in $\binom{S}{3}$ are \[\{u,v,w\},\ \{u,v,z\},\ \{u,w,z\},\ \{v,w,z\}. \] The last two triples $\{u,w,z\}$ and $\{v,w,z\}$ have one vertex in each part, hence are of type $(1,1,1)$ and therefore belong to $E(T)$. Among the first two triples, $\{u,v,w\}$ has type $(2\text{ in }X_1,\;1\text{ in }X_2)$, while $\{u,v,z\}$ has type $(2\text{ in }X_1,\;1\text{ in }X_3)$. Exactly one of $X_2$ or $X_3$ equals $X_{1+1}$ in the cyclic order, so by definition of $E(T)$ exactly one of these two triples is present and the other is absent. Therefore at least one triple among the four is missing, so $S$ does not span $K_4^3$.

These cases exhaust all possibilities for $(a_1,a_2,a_3)$. Hence no $4$-set $S$ spans all four triples, i.e. $T(V)$ is $K_4^3$-free. $\square$

Lemma 500.2 (Edge count; asymptotic density $5/9$ for equal parts). Assume $n=3m$ and $\lvert X_1\rvert=\lvert X_2\rvert=\lvert X_3\rvert=m$. Then \[ \lvert E(T)\rvert = m^3 + 3\binom{m}{2}m = \frac{m^2}{2}(5m-3) = \left(\frac{5}{9}+O\left(\frac{1}{n}\right)\right)\binom{n}{3}. \]

Proof. Count edges by type.

$1$ Edges with one vertex in each part: choose one from each part in $m^3$ ways.

$2$ Cyclic $2,1$-edges: for each $i\in\{1,2,3\}$, choose $2$ vertices from $X_i$ and $1$ vertex from $X_{i+1}$. This gives $\binom{m}{2}\cdot m$ edges for each $i$, hence $3\binom{m}{2}m$ in total.

Summing gives \[ \lvert E(T)\rvert = m^3 + 3\binom{m}{2}m = m^3 + 3\cdot \frac{m(m-1)}{2}\cdot m = \frac{m^2}{2}(5m-3). \] Also $\binom{n}{3}=\binom{3m}{3} = \frac{(3m)(3m-1)(3m-2)}{6} = \frac{9}{2}m^3 + O(m^2)$. Therefore \[ \frac{\lvert E(T)\rvert}{\binom{n}{3}} = \frac{\frac{5}{2}m^3 + O(m^2)}{\frac{9}{2}m^3 + O(m^2)} = \frac{5}{9} + O\left(\frac{1}{m}\right) = \frac{5}{9} + O\left(\frac{1}{n}\right). \] $\square$

FAST REALITY CHECK (exact small $n$). I exhaustively searched all $3$-graphs on $n\le 6$ vertices and found: \[ \mathrm{ex}_3(1,K_4^3)=0,\ \mathrm{ex}_3(2,K_4^3)=0,\ \mathrm{ex}_3(3,K_4^3)=1,\ \mathrm{ex}_3(4,K_4^3)=3,\ \mathrm{ex}_3(5,K_4^3)=7,\ \mathrm{ex}_3(6,K_4^3)=14. \] Moreover, the Turán construction achieves $7$ edges at $n=5$ (parts $2,2,1$) and $14$ edges at $n=6$ (parts $2,2,2$), so it is optimal for these $n$.

5) VERIFICATION

Quantifiers/edge cases: For $n\le 3$, the definition of $K_4^3$ makes the forbidden configuration impossible, so $\mathrm{ex}_3(n,K_4^3)=\binom{n}{3}$; this matches the computed values $0,0,1$.

Lemma checks: Lemma 500.1 enumerates all possible $4$-vertex distributions among three parts; in each case, an explicit missing triple is identified.

Computation check: Exhaustive enumeration for $n=6$ checks $2^{\binom{6}{3}}=2^{20}=1{,}048{,}576$ hypergraphs, feasible and exact.

6) FINAL UNRESOLVED

(i) Strongest proved partial result here: Turán's 3-part construction is $K_4^3$-free and has edge density $\frac{5}{9}+O(1/n)$ (Lemmas 500.1--500.2). Exact values for $n\le 6$ are computed and match this construction.

(ii) First gap (crisp): Prove that every $K_4^3$-free $3$-graph on $n$ vertices satisfies $\lvert E\rvert \le \left(\frac{5}{9}+o(1)\right)\binom{n}{3}$, i.e. the Turán construction is asymptotically optimal.

(iii) Top 3 next moves: 1. Compute $\mathrm{ex}_3(n,K_4^3)$ for $7\le n\le 10$ via ILP/branch-and-bound to test stability and see whether extremals resemble the 3-part construction. 2. Prove a stability statement: if a $K_4^3$-free $3$-graph has density $\ge 5/9-\varepsilon$, then its vertex set admits a near-balanced 3-partition with most edges of the Turán types. 3. Derive a clean analytic inequality bounding edge density in terms of the densities of the three parts (a first step toward a purely combinatorial upper bound).

(iv) Minimal counterexample structure (if $5/9$ is not optimal): a $K_4^3$-free $3$-graph with density $>5/9$ would likely require a structured partition into three (or more) parts with a modified allowed-type rule, while still avoiding the $(2,1,1)$ obstruction that forced a missing triple in Lemma 500.1.