Reused writeup on Math-5931 (gpt pro 5.2)

Erdős Problem 837 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

Let $k\geq 2$ and $A_k\subseteq [0,1]$ be the set of $\alpha$ such that there exists some $\beta(\alpha)>\alpha$ with the property that, if $G_1,G_2,\ldots$ is a sequence of $k$-uniform hypergraphs with\[\liminf \frac{e(G_n)}{\binom{\lvert G_n\rvert}{k}} >\alpha\]then there exist subgraphs $H_n\subseteq G_n$ such that $\lvert H_n\rvert \to \infty$ and\[\liminf \frac{e(H_n)}{\binom{\lvert H_n\rvert}{k}} >\beta,\]and further that this property does not necessarily hold if $>\alpha$ is replaced by $\geq \alpha$. What is $A_3$? A problem of Erdős and Simonovits. It is known that\[A_2 = \left\{ 1-\frac{1}{k} : k\geq 1\right\}.\]

1) FORMAL RESTATEMENT

Fix $k\ge 2$. For a finite $k$-uniform hypergraph $G$ with $v(G):=|V(G)|$ vertices and $e(G):=|E(G)|$ edges, define its edge density \[ d(G):=\frac{e(G)}{\binom{v(G)}{k}}\in[0,1]. \]

Define $A_k\subseteq[0,1]$ as the set of all $\alpha$ for which there exists a constant $\beta(\alpha)$ with \[ \alpha<\beta(\alpha)\le 1 \] such that the following implication holds:

For every sequence $(G_n)_{n\ge 1}$ of $k$-uniform hypergraphs with $v(G_n)\to\infty$ and \[ \liminf_{n\to\infty} d(G_n) > \alpha, \] there exist subhypergraphs $H_n\subseteq G_n$ with $v(H_n)\to\infty$ and \[ \liminf_{n\to\infty} d(H_n) > \beta(\alpha). \]

In addition, $\alpha\in A_k$ requires that the above implication fails if "$>\alpha$" is weakened to "$\ge\alpha$": i.e., there exists a sequence $(G_n)$ with $v(G_n)\to\infty$ and $\liminf d(G_n)\ge \alpha$ for which no choice of $H_n\subseteq G_n$ with $v(H_n)\to\infty$ achieves $\liminf d(H_n)>\beta(\alpha)$.

The question is to determine $A_3$.

Ambiguity note. The last displayed line "$A_2=\{1-1/k:k\ge 1\}$" uses $k$ as a dummy integer parameter unrelated to the uniformity (which is fixed at 2 here). I will treat it as a given fact and not attempt to re-derive it.

2) QUICK LITERATURE/CONTEXT CHECK

I will not invoke any external results beyond what is recorded here. The problem text states that for graphs (uniformity 2) the set $A_2$ is known exactly: \[ A_2 = \left\{ 1-\frac{1}{t} : t\geq 1\right\}. \] For $k=3$ the set $A_3$ is asked and (from the phrasing) appears open in this source.

3) ATTACK PLAN

• Clarify what can be assumed about the subgraphs $H_n$ (e.g. induced on their vertex sets) without loss of generality.
• Do a small-$n$ brute force check for $k=3$ to see what "local density jumps" look like on $n\le 6$ vertices.
• Try to extract any unconditional constraints on $A_3$ from the definition alone (logical negations, monotonicity failures, etc.).

4) WORK

Fast reality check (exact enumeration for $k=3$, $n=6$). There are $\binom{6}{3}=20$ possible 3-edges on 6 vertices, so $2^{20}=1{,}048{,}576$ distinct 3-uniform hypergraphs. By exhaustive enumeration, the following quantity was computed:

For each edge count $e\in\{0,1,\dots,20\}$, let \[ M_{m}(e):=\min\Big\{\max_{|S|=m} d\big(G[S]\big) : G\text{ is a 3-graph on 6 vertices with }e(G)=e\Big\}, \] where $G[S]$ denotes the induced 3-graph on vertex subset $S$. The exact values are:

• For $m=4$ (where $\binom{4}{3}=4$): \[\begin{array}{c|ccccccccccccccccccccc} e &0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\\\hline M_4(e) &0&\tfrac14&\tfrac14&\tfrac14&\tfrac14&\tfrac12&\tfrac12&\tfrac12&\tfrac12&\tfrac12&\tfrac12&\tfrac34&\tfrac34&\tfrac34&\tfrac34&1&1&1&1&1&1 \end{array}\]
• For $m=5$ (where $\binom{5}{3}=10$): \[\begin{array}{c|ccccccccccccccccccccc} e &0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\\\hline M_5(e) &0&0.1&0.1&0.2&0.2&0.3&0.3&0.4&0.4&0.5&0.5&0.6&0.6&0.7&0.7&0.8&0.8&0.9&0.9&1&1 \end{array}\]

This is only a small-$n$ sanity check (it does not settle anything asymptotic), but it shows that even on 6 vertices there are discrete "jumps" in the guaranteed maximum induced density at sizes 4 and 5.

Lemma 1 (Induced subgraphs suffice). In the definition of $A_k$, we may assume each $H_n$ is the induced subhypergraph of $G_n$ on its vertex set.

Proof. Let $H\subseteq G$ be any $k$-uniform subhypergraph. Let $S:=V(H)\subseteq V(G)$. Consider the induced subhypergraph $G[S]$ whose edge set consists of all edges of $G$ contained in $S$. Since every edge of $H$ is an edge of $G$ contained in $S$, we have $E(H)\subseteq E(G[S])$, hence $e(G[S])\ge e(H)$ and $v(G[S])=v(H)$. Therefore \[ d(G[S])=\frac{e(G[S])}{\binom{v(H)}{k}}\ge \frac{e(H)}{\binom{v(H)}{k}}=d(H). \] So replacing $H$ by the induced $G[S]$ weakly increases density and preserves vertex count. Applying this to each $H_n$ yields the claim. $\Box$

Lemma 2 (Logical negation of membership). Fix $k\ge 2$ and $\alpha\in[0,1]$. Then $\alpha\notin A_k$ if and only if for every $\beta>\alpha$ there exists a sequence $(G_n)$ of $k$-graphs with $v(G_n)\to\infty$ and $\liminf d(G_n)>\alpha$ such that for every choice of subgraphs $H_n\subseteq G_n$ with $v(H_n)\to\infty$ we have \[ \liminf d(H_n)\le \beta. \]

Proof. This is the direct logical negation of the defining implication for $\alpha\in A_k$. The forward direction: if $\alpha\notin A_k$, then no single $\beta>\alpha$ works universally, so for each candidate $\beta$ we can choose a witnessing bad sequence. The reverse direction: if the displayed bad sequence exists for every $\beta>\alpha$, then in particular there is no $\beta(\alpha)>\alpha$ satisfying the implication in the definition, hence $\alpha\notin A_k$. $\Box$

Lemma 3 (Subsequence normalization). Given any sequence $(G_n)$ with $v(G_n)\to\infty$ and $\liminf d(G_n)>\alpha$, there is a subsequence $(G_{n_j})$ such that:

1. $v(G_{n_j})$ is strictly increasing in $j$;
2. $d(G_{n_j})$ converges to some limit $p\in(\alpha,1]$.

Proof. Since $v(G_n)\to\infty$, there exists a subsequence with strictly increasing vertex counts. Since each density $d(G_n)$ lies in the compact interval $[0,1]$, the subsequence has a further subsequence along which $d(G_n)$ converges (Bolzano--Weierstrass). Finally, $\liminf d(G_n)>\alpha$ implies every tail has infimum $>\alpha$, so any subsequential limit satisfies $p\ge \liminf d(G_n)>\alpha$. $\Box$

5) VERIFICATION

• Lemma 1 only uses the fact that induced subgraphs include all edges present on a chosen vertex set, so it does not depend on any special structure.
• Lemma 2 is purely logical; the only subtlety is quantifier order ("for every $\beta$ there exists a sequence such that for every choice of $H_n$...").
• The brute-force enumeration is exact for $n=6$; however, it has no direct asymptotic consequence without additional arguments.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. Structural simplifications: one may assume $H_n$ are induced (Lemma 1) and pass to subsequences with convergent densities (Lemma 3). Additionally, exact $n=6$ computations for $k=3$ show discrete guaranteed increases of maximum induced density on 4- and 5-vertex subsets as a function of the total edge count.

(ii) First gap (crisp). Determine the set $A_3\subseteq[0,1]$: characterize exactly which $\alpha$ admit a universal density increment $\beta(\alpha)>\alpha$ in the sense of the definition.

(iii) Top 3 next moves.

1. Compute (by brute force) analogous tables to the $n=6$ one above for $n=7,8$ (where feasible), to guess candidate "jump" values for 3-graphs and see if patterns stabilize.
2. Try to derive nontrivial inclusions/exclusions for $A_3$ by constructing explicit extremal sequences $(G_n)$ whose induced subgraph densities can be controlled (e.g., via partite constructions) and proving upper bounds on all induced densities.
3. Attempt to prove that certain natural densities (coming from explicit structured families) are or are not jumps by proving a supersaturation-type lemma specialized to those families.

(iv) What a minimal counterexample would likely look like. To show a given $\alpha$ is not in $A_3$, one needs a sequence of 3-graphs with density bounded away from $\alpha$ but such that every induced subgraph on $m\to\infty$ vertices has density at most $\alpha+o(1)$ (or at most a target $\beta$). Such a sequence would have to suppress the emergence of very dense induced subgraphs of growing size.

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.