Erdős Problem #712

Erdős Problem 712 --- 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/712.tex.

REUSED SOURCE 1

1) “FORMAL RESTATEMENT”

Fix integers $k>r>2$. Let $K_k^r$ denote the complete $r$-uniform hypergraph on $k$ vertices (i.e. every $r$-subset of a fixed $k$-set is an edge).

For each $n\ge k$, let $\mathrm{ex}_r(n,K_k^r)$ be the maximum number of $r$-edges in an $r$-uniform hypergraph on vertex set $[n]:=\{1,\dots,n\}$ that contains no copy of $K_k^r$ as a (not-necessarily-induced) subhypergraph.

The problem asks to determine \[ \lim_{n\to\infty}\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}}\qquad\text{(if the limit exists),} \] for each fixed $k>r>2$.

Stress points: existence of the limit is not automatic; even when it exists, identifying the optimal construction is difficult.

2) “QUICK LITERATURE/CONTEXT CHECK”

Only what is explicitly stated in the problem text:

- For $r=2$ (graphs), Turán proved the limit equals $\frac12\left(1-\frac1{k-1}\right)$.

Per integrity rules, I do not use any other external results.

3) “ATTACK PLAN”

Proof track ideas:

- Lower bounds from explicit constructions (balanced $(k-1)$-partite $r$-graphs, or other structured designs). - Upper bounds by counting missing edges per $k$-set, stability-type arguments, or flag algebra computations (not carried out here).

Disproof/construction track: search small $n$ by brute force to see which constructions appear extremal.

4) “WORK”

FAST REALITY CHECK (small exact computations).

For $r=3$ I computed by brute force the exact values for small $n$:

- For $K_4^3$ (the 3-uniform tetrahedron), \[ \mathrm{ex}_3(4,K_4^3)=3\ (\text{out of }\binom43=4),\quad \mathrm{ex}_3(5,K_4^3)=7\ (\text{out of }10),\quad \mathrm{ex}_3(6,K_4^3)=14\ (\text{out of }20). \]

- For $K_5^3$, \[ \mathrm{ex}_3(5,K_5^3)=9\ (\text{out of }10),\quad \mathrm{ex}_3(6,K_5^3)=18\ (\text{out of }20). \]

These are sanity checks only; small $n$ behavior can differ from the asymptotic density.

Proposition 1 (Explicit lower bound via $(k-1)$-partite construction). Let $k>r\ge 2$ be fixed. Partition $[n]$ into $k-1$ parts $V_1\cup\cdots\cup V_{k-1}$ (as equal as possible), and let $H$ be the complete $(k-1)$-partite $r$-uniform hypergraph: an $r$-set $e$ is an edge iff it meets each $V_i$ in at most one vertex (equivalently, all $r$ vertices lie in distinct parts).

Then $H$ is $K_k^r$-free. Moreover, writing $|V_i|=n_i$ with $\sum_i n_i=n$, \[ |E(H)|=\sum_{1\le i_1<\cdots<i_r\le k-1} n_{i_1}n_{i_2}\cdots n_{i_r}. \] In particular, for balanced parts $n_i\in\{\lfloor n/(k-1)\rfloor,\lceil n/(k-1)\rceil\}$, \[ \frac{|E(H)|}{\binom{n}{r}} \to \frac{r!\binom{k-1}{r}}{(k-1)^r} \qquad (n\to\infty), \] so \[ \liminf_{n\to\infty}\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}}\ge \frac{r!\binom{k-1}{r}}{(k-1)^r}. \]

Proof. First, $H$ is $K_k^r$-free: take any set $S$ of $k$ vertices. Since there are only $k-1$ parts, by the pigeonhole principle two vertices of $S$ lie in the same part, say $V_j$. Choose any other $r-2$ vertices of $S$ (possible since $r\le k-1$). Then the resulting $r$-set contains two vertices from $V_j$, hence is not an edge of $H$. Therefore $S$ does not span all $\binom{k}{r}$ edges, so no copy of $K_k^r$ exists.

Second, to count edges: an edge of $H$ is determined by choosing $r$ distinct parts $V_{i_1},\dots,V_{i_r}$ and then choosing one vertex from each part, giving $n_{i_1}\cdots n_{i_r}$ choices. Summing over $\binom{k-1}{r}$ choices of parts gives the formula.

Finally, for balanced parts $n_i\sim n/(k-1)$, each summand $n_{i_1}\cdots n_{i_r}\sim (n/(k-1))^r$, so \[ |E(H)|\sim \binom{k-1}{r}\left(\frac{n}{k-1}\right)^r. \] Since $\binom{n}{r}\sim \frac{n^r}{r!}$, dividing gives the stated limiting ratio. $\square$

Proposition 2 (Simple universal upper bound by counting missing edges). For all $n\ge k$, \[ \mathrm{ex}_r(n,K_k^r)\le \left(1-\frac{1}{\binom{k}{r}}\right)\binom{n}{r}. \] Equivalently, \[ \frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}}\le 1-\frac{1}{\binom{k}{r}}. \]

Proof. Let $H$ be any $K_k^r$-free $r$-graph on $[n]$ with edge set $E(H)$. Let $M$ be the set of missing $r$-edges: \[ M:=\binom{[n]}{r}\setminus E(H),\qquad |M|=\binom{n}{r}-|E(H)|. \] Because $H$ is $K_k^r$-free, every $k$-subset $S\in\binom{[n]}{k}$ misses at least one of its $\binom{k}{r}$ $r$-subsets, i.e. there exists at least one $e\in M$ with $e\subseteq S$.

Count pairs $(S,e)$ where $S\in\binom{[n]}{k}$ and $e\in M$ with $e\subseteq S$.

- Lower bound: each $k$-set $S$ contributes at least one such missing $e$, so the number of pairs is at least $\binom{n}{k}$.

- Upper bound: each missing $r$-set $e\in M$ is contained in exactly $\binom{n-r}{k-r}$ different $k$-sets $S$ (choose the remaining $k-r$ vertices from the $n-r$ outside $e$). Thus the number of pairs is at most \[ |M|\binom{n-r}{k-r}. \]

Therefore \[ \binom{n}{k}\le |M|\binom{n-r}{k-r}. \] A direct factorial manipulation gives \[ \frac{\binom{n}{k}}{\binom{n-r}{k-r}} = \frac{\binom{n}{r}}{\binom{k}{r}}. \] (Indeed, both sides equal $\frac{n!}{r!(n-r)!}\cdot\frac{r!(k-r)!}{k!} = \frac{n!(k-r)!}{k!(n-r)!}$.) So \[ |M| \ge \frac{\binom{n}{k}}{\binom{n-r}{k-r}} = \frac{\binom{n}{r}}{\binom{k}{r}}. \] Hence \[ |E(H)| = \binom{n}{r}-|M| \le \binom{n}{r}\left(1-\frac{1}{\binom{k}{r}}\right). \] Taking the maximum over all such $H$ gives the claim. $\square$

5) “VERIFICATION”

- Proposition 1: The $K_k^r$-freeness argument uses only pigeonhole and the explicit definition of $(k-1)$-partite $r$-edges; checked that it indeed produces a missing $r$-subset inside any $k$-set. - Proposition 2: Double counting verified; the identity $\binom{n}{k}/\binom{n-r}{k-r}=\binom{n}{r}/\binom{k}{r}$ was checked algebraically. - Computations: brute force enumerations were run only for small parameters where $2^{\binom{n}{r}}$ is feasible.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result here: explicit lower bound \[ \liminf_{n\to\infty}\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}}\ge \frac{r!\binom{k-1}{r}}{(k-1)^r} \] from the balanced $(k-1)$-partite construction, and a universal upper bound \[ \frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}}\le 1-\frac{1}{\binom{k}{r}}. \]

(ii) First gap (crisp statement): determine the exact value of \[ \pi_r(K_k^r):=\lim_{n\to\infty}\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}} \] (or show the limit exists) for each fixed $k>r>2$.

(iii) Top 3 next moves (concrete targets):

1. Compute $\mathrm{ex}_r(n,K_k^r)$ exactly for the next few $n$ beyond brute force (e.g. via MILP/branch-and-bound) to identify candidate extremal constructions.

2. Prove a stability statement: if an $r$-graph is $K_k^r$-free and has edge density within $o(1)$ of the conjectured optimum, then its vertex set admits an almost $(k-1)$-partite structure.

3. Improve Proposition 2 by weighting $k$-sets and missing edges more carefully (e.g. count how many missing edges each $k$-set forces on average) to get an upper bound closer to known constructions.

(iv) Minimal counterexample structure (if the balanced $(k-1)$-partite density is not optimal): one expects a family of $K_k^r$-free $r$-graphs with density strictly larger than $r!\binom{k-1}{r}/(k-1)^r$ whose local structure is not close to a $(k-1)$-partition, likely involving nontrivial designs where many $k$-sets miss different $r$-edges in a highly non-uniform way.

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”

Fix integers $k>r>2$. Let $K_k^r$ denote the complete $r$-uniform hypergraph on $k$ vertices (i.e. every $r$-subset of a fixed $k$-set is an edge).

For each $n\ge k$, let $\mathrm{ex}_r(n,K_k^r)$ be the maximum number of $r$-edges in an $r$-uniform hypergraph on vertex set $[n]:=\{1,\dots,n\}$ that contains no copy of $K_k^r$ as a (not-necessarily-induced) subhypergraph.

The problem asks to determine \[ \lim_{n\to\infty}\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}}\qquad\text{(if the limit exists),} \] for each fixed $k>r>2$.

Stress points: existence of the limit is not automatic; even when it exists, identifying the optimal construction is difficult.

2) “QUICK LITERATURE/CONTEXT CHECK”

Only what is explicitly stated in the problem text:

- For $r=2$ (graphs), Turán proved the limit equals $\frac12\left(1-\frac1{k-1}\right)$.

Per integrity rules, I do not use any other external results.

3) “ATTACK PLAN”

Proof track ideas:

- Lower bounds from explicit constructions (balanced $(k-1)$-partite $r$-graphs, or other structured designs). - Upper bounds by counting missing edges per $k$-set, stability-type arguments, or flag algebra computations (not carried out here).

Disproof/construction track: search small $n$ by brute force to see which constructions appear extremal.

4) “WORK”

FAST REALITY CHECK (small exact computations).

For $r=3$ I computed by brute force the exact values for small $n$:

- For $K_4^3$ (the 3-uniform tetrahedron), \[ \mathrm{ex}_3(4,K_4^3)=3\ (\text{out of }\binom43=4),\quad \mathrm{ex}_3(5,K_4^3)=7\ (\text{out of }10),\quad \mathrm{ex}_3(6,K_4^3)=14\ (\text{out of }20). \]

- For $K_5^3$, \[ \mathrm{ex}_3(5,K_5^3)=9\ (\text{out of }10),\quad \mathrm{ex}_3(6,K_5^3)=18\ (\text{out of }20). \]

These are sanity checks only; small $n$ behavior can differ from the asymptotic density.

Proposition 1 (Explicit lower bound via $(k-1)$-partite construction). Let $k>r\ge 2$ be fixed. Partition $[n]$ into $k-1$ parts $V_1\cup\cdots\cup V_{k-1}$ (as equal as possible), and let $H$ be the complete $(k-1)$-partite $r$-uniform hypergraph: an $r$-set $e$ is an edge iff it meets each $V_i$ in at most one vertex (equivalently, all $r$ vertices lie in distinct parts).

Then $H$ is $K_k^r$-free. Moreover, writing $|V_i|=n_i$ with $\sum_i n_i=n$, \[ |E(H)|=\sum_{1\le i_1<\cdots<i_r\le k-1} n_{i_1}n_{i_2}\cdots n_{i_r}. \] In particular, for balanced parts $n_i\in\{\lfloor n/(k-1)\rfloor,\lceil n/(k-1)\rceil\}$, \[ \frac{|E(H)|}{\binom{n}{r}} \to \frac{r!\binom{k-1}{r}}{(k-1)^r} \qquad (n\to\infty), \] so \[ \liminf_{n\to\infty}\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}}\ge \frac{r!\binom{k-1}{r}}{(k-1)^r}. \]

Proof. First, $H$ is $K_k^r$-free: take any set $S$ of $k$ vertices. Since there are only $k-1$ parts, by the pigeonhole principle two vertices of $S$ lie in the same part, say $V_j$. Choose any other $r-2$ vertices of $S$ (possible since $r\le k-1$). Then the resulting $r$-set contains two vertices from $V_j$, hence is not an edge of $H$. Therefore $S$ does not span all $\binom{k}{r}$ edges, so no copy of $K_k^r$ exists.

Second, to count edges: an edge of $H$ is determined by choosing $r$ distinct parts $V_{i_1},\dots,V_{i_r}$ and then choosing one vertex from each part, giving $n_{i_1}\cdots n_{i_r}$ choices. Summing over $\binom{k-1}{r}$ choices of parts gives the formula.

Finally, for balanced parts $n_i\sim n/(k-1)$, each summand $n_{i_1}\cdots n_{i_r}\sim (n/(k-1))^r$, so \[ |E(H)|\sim \binom{k-1}{r}\left(\frac{n}{k-1}\right)^r. \] Since $\binom{n}{r}\sim \frac{n^r}{r!}$, dividing gives the stated limiting ratio. $\square$

Proposition 2 (Simple universal upper bound by counting missing edges). For all $n\ge k$, \[ \mathrm{ex}_r(n,K_k^r)\le \left(1-\frac{1}{\binom{k}{r}}\right)\binom{n}{r}. \] Equivalently, \[ \frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}}\le 1-\frac{1}{\binom{k}{r}}. \]

Proof. Let $H$ be any $K_k^r$-free $r$-graph on $[n]$ with edge set $E(H)$. Let $M$ be the set of missing $r$-edges: \[ M:=\binom{[n]}{r}\setminus E(H),\qquad |M|=\binom{n}{r}-|E(H)|. \] Because $H$ is $K_k^r$-free, every $k$-subset $S\in\binom{[n]}{k}$ misses at least one of its $\binom{k}{r}$ $r$-subsets, i.e. there exists at least one $e\in M$ with $e\subseteq S$.

Count pairs $(S,e)$ where $S\in\binom{[n]}{k}$ and $e\in M$ with $e\subseteq S$.

- Lower bound: each $k$-set $S$ contributes at least one such missing $e$, so the number of pairs is at least $\binom{n}{k}$.

- Upper bound: each missing $r$-set $e\in M$ is contained in exactly $\binom{n-r}{k-r}$ different $k$-sets $S$ (choose the remaining $k-r$ vertices from the $n-r$ outside $e$). Thus the number of pairs is at most \[ |M|\binom{n-r}{k-r}. \]

Therefore \[ \binom{n}{k}\le |M|\binom{n-r}{k-r}. \] A direct factorial manipulation gives \[ \frac{\binom{n}{k}}{\binom{n-r}{k-r}} = \frac{\binom{n}{r}}{\binom{k}{r}}. \] (Indeed, both sides equal $\frac{n!}{r!(n-r)!}\cdot\frac{r!(k-r)!}{k!} = \frac{n!(k-r)!}{k!(n-r)!}$.) So \[ |M| \ge \frac{\binom{n}{k}}{\binom{n-r}{k-r}} = \frac{\binom{n}{r}}{\binom{k}{r}}. \] Hence \[ |E(H)| = \binom{n}{r}-|M| \le \binom{n}{r}\left(1-\frac{1}{\binom{k}{r}}\right). \] Taking the maximum over all such $H$ gives the claim. $\square$

5) “VERIFICATION”

- Proposition 1: The $K_k^r$-freeness argument uses only pigeonhole and the explicit definition of $(k-1)$-partite $r$-edges; checked that it indeed produces a missing $r$-subset inside any $k$-set. - Proposition 2: Double counting verified; the identity $\binom{n}{k}/\binom{n-r}{k-r}=\binom{n}{r}/\binom{k}{r}$ was checked algebraically. - Computations: brute force enumerations were run only for small parameters where $2^{\binom{n}{r}}$ is feasible.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result here: explicit lower bound \[ \liminf_{n\to\infty}\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}}\ge \frac{r!\binom{k-1}{r}}{(k-1)^r} \] from the balanced $(k-1)$-partite construction, and a universal upper bound \[ \frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}}\le 1-\frac{1}{\binom{k}{r}}. \]

(ii) First gap (crisp statement): determine the exact value of \[ \pi_r(K_k^r):=\lim_{n\to\infty}\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}} \] (or show the limit exists) for each fixed $k>r>2$.

(iii) Top 3 next moves (concrete targets):

1. Compute $\mathrm{ex}_r(n,K_k^r)$ exactly for the next few $n$ beyond brute force (e.g. via MILP/branch-and-bound) to identify candidate extremal constructions.

2. Prove a stability statement: if an $r$-graph is $K_k^r$-free and has edge density within $o(1)$ of the conjectured optimum, then its vertex set admits an almost $(k-1)$-partite structure.

3. Improve Proposition 2 by weighting $k$-sets and missing edges more carefully (e.g. count how many missing edges each $k$-set forces on average) to get an upper bound closer to known constructions.

(iv) Minimal counterexample structure (if the balanced $(k-1)$-partite density is not optimal): one expects a family of $K_k^r$-free $r$-graphs with density strictly larger than $r!\binom{k-1}{r}/(k-1)^r$ whose local structure is not close to a $(k-1)$-partition, likely involving nontrivial designs where many $k$-sets miss different $r$-edges in a highly non-uniform way.