Erdős Problem #813

Erdős Problem 813 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

Erdos Problem #813

FORMAL RESTATEMENT.

For $n\in\mathbb{N}$, define $h(n)$ to be the least integer $t$ such that every (simple, undirected) graph $G$ on $n$ vertices with the property \[ (\forall S\subseteq V(G),\ |S|=7)\ \text{the induced subgraph }G[S]\text{ contains a triangle }(K_3) \] must contain a clique of size at least $t$ (i.e. $\omega(G)\ge t$). The problem asks for asymptotics of $h(n)$, in particular whether there exist constants $c_1,c_2>0$ with \[ n^{1/3+c_1} \ll h(n) \ll n^{1/2-c_2}. \]

QUICK LITERATURE/CONTEXT CHECK.

The statement records that Erdős and Hajnal proved $n^{1/3}\ll h(n)\ll n^{1/2}$ and that Bucić and Sudakov proved $h(n)\gg n^{5/12-o(1)}$. I do not use any results not already stated in the problem text.

ATTACK PLAN.

Proof track: try to convert the local "every $7$ vertices span a triangle" condition into a global density/structure statement, then feed it into a clique-finding method.

Disproof track: attempt to construct graphs where all $7$-sets contain a triangle but the maximum clique is as small as possible; for small $n$, search for $K_4$-free examples.

WORK.

Lemma 813.1 (immediate consequence: bounded independence number). If $G$ satisfies the local property that every $7$-vertex set spans a triangle, then $\alpha(G)\le 6$.

Proof. If $G$ had an independent set $I$ of size $7$, then the induced subgraph $G[I]$ would have no edges, hence no triangle, contradicting the defining property. Therefore no independent set has size $7$, i.e. $\alpha(G)\le 6$. $\square$

Lemma 813.2 (a provable but weak lower bound on $h(n)$). Let $t$ be the largest integer such that $\binom{t+5}{6}\le n$. Then every $n$-vertex graph with the local property must contain a clique of size at least $t$. In particular, \[ h(n) \ge \max\{t\in\mathbb{N}: \binom{t+5}{6}\le n\} = \Omega(n^{1/6}). \]

Proof. By Lemma 813.1 such a graph $G$ has no independent set of size $7$. Consider the (off-diagonal) Ramsey number $R(t,7)$: the least $N$ such that every graph on $N$ vertices contains either a $K_t$ or an independent set of size $7$. If $n\ge R(t,7)$, then $G$ must contain a $K_t$ because the alternative (an independent set of size $7$) is forbidden.

It remains to show that $R(t,7)\le \binom{t+5}{6}$. This follows from the standard Erdős--Szekeres recursion for Ramsey numbers: \[ R(a,b) \le R(a-1,b) + R(a,b-1)\quad (a,b\ge2), \] together with the initial values $R(1,b)=1$ and $R(a,1)=1$. Indeed, fix $N=R(a-1,b)+R(a,b-1)$ and any graph $H$ on $N$ vertices. Pick a vertex $v$. Let $N_1$ be the number of neighbours of $v$ in $H$ and $N_0$ the number of non-neighbours; then $N_0+N_1=N-1$. If $N_1\ge R(a-1,b)$, then within the neighbour set either there is a $K_{a-1}$ (which together with $v$ gives a $K_a$) or there is an independent set of size $b$ (which is also independent in $H$). If $N_1< R(a-1,b)$, then $N_0\ge R(a,b-1)$ and applying the same reasoning in the non-neighbour set yields either a $K_a$ (already in the non-neighbour set) or an independent set of size $b-1$ that together with $v$ forms an independent set of size $b$. Thus $R(a,b)\le R(a-1,b)+R(a,b-1)$. Iterating this recursion yields the binomial bound \[ R(a,b) \le \binom{a+b-2}{a-1}. \] Setting $a=t$ and $b=7$ gives $R(t,7)\le \binom{t+5}{t-1}=\binom{t+5}{6}$. Therefore if $n\ge \binom{t+5}{6}$, every $n$-vertex graph with no independent set of size $7$ must contain a $K_t$. $\square$

FAST REALITY CHECK (small $n$ via explicit examples). For $n<7$, the local condition is vacuous (there are no $7$-subsets), so $h(n)=1$ for $1\le n\le 6$. For $n=7$, the condition is "$G$ contains a triangle", hence $h(7)=3$.

For $n=8$ and $n=9$, I found explicit $K_4$-free graphs satisfying the local property, so $h(8)=h(9)=3$. One such graph on $8$ vertices (labelled $1,\dots,8$) has edge set \[ \{12,15,25,37,46,47,48,56,78\}, \] and one such graph on $9$ vertices has edge set \[ \{14,17,24,26,28,35,38,39,47,56,59,67,68,89\}. \] In each case an exhaustive check over all $7$-subsets confirms the local condition, and an exhaustive check over all $4$-subsets confirms $\omega(G)=3$.

VERIFICATION.

Lemma 813.1: an independent set on $7$ vertices induces an edgeless (hence triangle-free) graph, so it is forbidden. Lemma 813.2: the only nontrivial step is the Ramsey recursion argument; the neighbour/non-neighbour split is checked case-by-case and uses only the definition of $R(a,b)$. For the exhibited $n=8,9$ graphs, both (a) "every $7$-subset contains a triangle" and (b) "no $4$-subset is a clique" are finite checks (done computationally).

FINAL.

UNRESOLVED.

1. (i) Strongest proved partial results here: the local condition implies $\alpha(G)\le6$ (Lemma 813.1), and hence a universal lower bound $h(n)=\Omega(n^{1/6})$ via the elementary binomial Ramsey upper bound (Lemma 813.2). Also, exact small values: $h(n)=1$ for $n\le6$ and $h(7)=h(8)=h(9)=3$ by explicit examples.
2. (ii) First gap: prove a power-type lower bound $h(n)\ge n^{1/3+\varepsilon}$ (for some fixed $\varepsilon>0$) from the local triangle condition alone, without importing external theorems.
3. (iii) Top 3 next moves: $1$ attempt to show the local condition forces a global edge density $e(G)\ge \delta n^2$ with explicit $\delta>0$, then combine with a clique-finding lemma; $2$ strengthen Lemma 813.1 by bounding the size of induced triangle-free subgraphs more sharply than $6$ in terms of other parameters (e.g. by forcing many triangles through each vertex); $3$ computationally search for larger $n$ for which $\omega(G)=3$ is still possible under the local condition, to guide candidate extremal constructions.
4. (iv) A minimal counterexample to any conjectured lower bound $h(n)\ge n^{\beta}$ would be a family of graphs $G_n$ with $|V|=n$, every $7$-set spanning a triangle, but with clique number $\omega(G_n)=o(n^{\beta})$; given Lemma 813.1 these would necessarily have bounded independence number but avoid large cliques, i.e. behave like Ramsey graphs with an additional local triangle-forcing constraint.

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.

Erdos Problem #813

FORMAL RESTATEMENT.

For $n\in\mathbb{N}$, define $h(n)$ to be the least integer $t$ such that every (simple, undirected) graph $G$ on $n$ vertices with the property \[ (\forall S\subseteq V(G),\ |S|=7)\ \text{the induced subgraph }G[S]\text{ contains a triangle }(K_3) \] must contain a clique of size at least $t$ (i.e. $\omega(G)\ge t$). The problem asks for asymptotics of $h(n)$, in particular whether there exist constants $c_1,c_2>0$ with \[ n^{1/3+c_1} \ll h(n) \ll n^{1/2-c_2}. \]

QUICK LITERATURE/CONTEXT CHECK.

The statement records that Erdős and Hajnal proved $n^{1/3}\ll h(n)\ll n^{1/2}$ and that Bucić and Sudakov proved $h(n)\gg n^{5/12-o(1)}$. I do not use any results not already stated in the problem text.

ATTACK PLAN.

Proof track: try to convert the local "every $7$ vertices span a triangle" condition into a global density/structure statement, then feed it into a clique-finding method.

Disproof track: attempt to construct graphs where all $7$-sets contain a triangle but the maximum clique is as small as possible; for small $n$, search for $K_4$-free examples.

WORK.

Lemma 813.1 (immediate consequence: bounded independence number). If $G$ satisfies the local property that every $7$-vertex set spans a triangle, then $\alpha(G)\le 6$.

Proof. If $G$ had an independent set $I$ of size $7$, then the induced subgraph $G[I]$ would have no edges, hence no triangle, contradicting the defining property. Therefore no independent set has size $7$, i.e. $\alpha(G)\le 6$. $\square$

Lemma 813.2 (a provable but weak lower bound on $h(n)$). Let $t$ be the largest integer such that $\binom{t+5}{6}\le n$. Then every $n$-vertex graph with the local property must contain a clique of size at least $t$. In particular, \[ h(n) \ge \max\{t\in\mathbb{N}: \binom{t+5}{6}\le n\} = \Omega(n^{1/6}). \]

Proof. By Lemma 813.1 such a graph $G$ has no independent set of size $7$. Consider the (off-diagonal) Ramsey number $R(t,7)$: the least $N$ such that every graph on $N$ vertices contains either a $K_t$ or an independent set of size $7$. If $n\ge R(t,7)$, then $G$ must contain a $K_t$ because the alternative (an independent set of size $7$) is forbidden.

It remains to show that $R(t,7)\le \binom{t+5}{6}$. This follows from the standard Erdős--Szekeres recursion for Ramsey numbers: \[ R(a,b) \le R(a-1,b) + R(a,b-1)\quad (a,b\ge2), \] together with the initial values $R(1,b)=1$ and $R(a,1)=1$. Indeed, fix $N=R(a-1,b)+R(a,b-1)$ and any graph $H$ on $N$ vertices. Pick a vertex $v$. Let $N_1$ be the number of neighbours of $v$ in $H$ and $N_0$ the number of non-neighbours; then $N_0+N_1=N-1$. If $N_1\ge R(a-1,b)$, then within the neighbour set either there is a $K_{a-1}$ (which together with $v$ gives a $K_a$) or there is an independent set of size $b$ (which is also independent in $H$). If $N_1< R(a-1,b)$, then $N_0\ge R(a,b-1)$ and applying the same reasoning in the non-neighbour set yields either a $K_a$ (already in the non-neighbour set) or an independent set of size $b-1$ that together with $v$ forms an independent set of size $b$. Thus $R(a,b)\le R(a-1,b)+R(a,b-1)$. Iterating this recursion yields the binomial bound \[ R(a,b) \le \binom{a+b-2}{a-1}. \] Setting $a=t$ and $b=7$ gives $R(t,7)\le \binom{t+5}{t-1}=\binom{t+5}{6}$. Therefore if $n\ge \binom{t+5}{6}$, every $n$-vertex graph with no independent set of size $7$ must contain a $K_t$. $\square$

FAST REALITY CHECK (small $n$ via explicit examples). For $n<7$, the local condition is vacuous (there are no $7$-subsets), so $h(n)=1$ for $1\le n\le 6$. For $n=7$, the condition is "$G$ contains a triangle", hence $h(7)=3$.

For $n=8$ and $n=9$, I found explicit $K_4$-free graphs satisfying the local property, so $h(8)=h(9)=3$. One such graph on $8$ vertices (labelled $1,\dots,8$) has edge set \[ \{12,15,25,37,46,47,48,56,78\}, \] and one such graph on $9$ vertices has edge set \[ \{14,17,24,26,28,35,38,39,47,56,59,67,68,89\}. \] In each case an exhaustive check over all $7$-subsets confirms the local condition, and an exhaustive check over all $4$-subsets confirms $\omega(G)=3$.

VERIFICATION.

Lemma 813.1: an independent set on $7$ vertices induces an edgeless (hence triangle-free) graph, so it is forbidden. Lemma 813.2: the only nontrivial step is the Ramsey recursion argument; the neighbour/non-neighbour split is checked case-by-case and uses only the definition of $R(a,b)$. For the exhibited $n=8,9$ graphs, both (a) "every $7$-subset contains a triangle" and (b) "no $4$-subset is a clique" are finite checks (done computationally).

FINAL.

UNRESOLVED.

1. (i) Strongest proved partial results here: the local condition implies $\alpha(G)\le6$ (Lemma 813.1), and hence a universal lower bound $h(n)=\Omega(n^{1/6})$ via the elementary binomial Ramsey upper bound (Lemma 813.2). Also, exact small values: $h(n)=1$ for $n\le6$ and $h(7)=h(8)=h(9)=3$ by explicit examples.
2. (ii) First gap: prove a power-type lower bound $h(n)\ge n^{1/3+\varepsilon}$ (for some fixed $\varepsilon>0$) from the local triangle condition alone, without importing external theorems.
3. (iii) Top 3 next moves: $1$ attempt to show the local condition forces a global edge density $e(G)\ge \delta n^2$ with explicit $\delta>0$, then combine with a clique-finding lemma; $2$ strengthen Lemma 813.1 by bounding the size of induced triangle-free subgraphs more sharply than $6$ in terms of other parameters (e.g. by forcing many triangles through each vertex); $3$ computationally search for larger $n$ for which $\omega(G)=3$ is still possible under the local condition, to guide candidate extremal constructions.
4. (iv) A minimal counterexample to any conjectured lower bound $h(n)\ge n^{\beta}$ would be a family of graphs $G_n$ with $|V|=n$, every $7$-set spanning a triangle, but with clique number $\omega(G_n)=o(n^{\beta})$; given Lemma 813.1 these would necessarily have bounded independence number but avoid large cliques, i.e. behave like Ramsey graphs with an additional local triangle-forcing constraint.