gpt pro 5.2 attempt on Math-5836

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.