Reused writeup on Math-5751 (gpt pro 5.2)

Erdős Problem 584 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

FORMAL RESTATEMENT.

The statement in the problem uses asymptotic notation ($\gg$) and does not fully specify dependencies when $\delta=\delta(n)$. The minimal conventional restatement consistent with the text is:

For each $n\ge 1$ and each real $\delta\in(0,1/2]$, let $G$ be a simple graph on $n$ vertices with at least $\delta n^2$ edges. Is there an absolute constant $c>0$ such that one can always find subgraphs $H_1,H_2\subseteq G$ satisfying:

$1$ $e(H_1)\ge c\,\delta^3 n^2$, and for every two edges $e,f\in E(H_1)$ there exists a (simple) cycle in $H_1$ of length at most $6$ containing both $e$ and $f$; moreover if $e$ and $f$ share a vertex then there is a $4$-cycle in $H_1$ containing both.

$2$ $e(H_2)\ge c\,\delta^2 n^2$, and for every two edges $e,f\in E(H_2)$ there exists a (simple) cycle in $H_2$ of length at most $8$ containing both $e$ and $f$.

Here $e(H)$ denotes the number of edges.

QUICK LITERATURE/CONTEXT CHECK.

I will not use any literature beyond what is explicitly quoted in the problem statement (Duke--Erdős, Duke--Erdős--Rödl, Fox--Sudakov).

ATTACK PLAN.

Proof-track ideas. $1$ Prune to a subgraph of linear minimum degree $\Omega(\delta n)$, then use common-neighbor arguments to force many short cycles and attempt to extract a large "cycle-connected" edge set. $2$ Use a dependent-random-choice style selection of a vertex subset with large common neighborhoods to build many $4$- and $6$-cycles.

Disproof-track ideas. $1$ Try sparse pseudorandom graphs with few short cycles, or bipartite graphs with large girth, as potential obstructions when $\delta=n^{-c}$. $2$ For small $n$, brute force search for graphs where no subgraph of the required size has the stated cycle connectivity.

In this write-up I only obtain trivial regimes (very dense graphs) and structural lemmas.

WORK.

Lemma 584.1 (dense subgraph with linear minimum degree). Let $G$ be a graph on $n$ vertices with $e(G)\ge \delta n^2$. Then $G$ contains a subgraph $H\subseteq G$ with \[ e(H)\ge \frac{\delta n^2}{2} \qquad\text{and}\qquad \delta(H)\ge \frac{\delta n}{2}, \] where $\delta(H)$ denotes the minimum degree of $H$.

Proof. Start with $H:=G$. While there exists a vertex $v$ of current degree $<\delta n/2$, delete $v$ and all incident edges from $H$. This process terminates after deleting some set of vertices. When a vertex is deleted, fewer than $\delta n/2$ edges are removed. If $t$ vertices are deleted in total, then fewer than $t\cdot(\delta n/2)$ edges are deleted. Since $t\le n$, fewer than $(\delta n^2)/2$ edges are deleted overall. Thus the final graph $H$ has \[ e(H)\ge e(G)-\frac{\delta n^2}{2}\ge \frac{\delta n^2}{2}. \] By construction, every remaining vertex has degree at least $\delta n/2$ in $H$, so $\delta(H)\ge \delta n/2$. $\square$

Lemma 584.2 (adjacent edges in a $4$-cycle under degree $>n/2$). Let $H$ be a graph on $n$ vertices with minimum degree $\delta(H)>\frac n2$. Then for any two edges $uv$ and $vw$ sharing a vertex $v$, there exists a $4$-cycle in $H$ containing both edges.

Proof. Fix adjacent edges $uv$ and $vw$. We seek a vertex $x\notin\{u,v,w\}$ adjacent to both $u$ and $w$. Since $\deg(u)>n/2$ and $\deg(w)>n/2$, we have \[ |N(u)|+|N(w)|>n, \] so by the pigeonhole principle $N(u)\cap N(w)\neq\varnothing$. Also, $v\in N(u)\cap N(w)$, but we need a vertex distinct from $v$. Because degrees are integers, $\deg(u)\ge\lfloor n/2\rfloor+1$ and $\deg(w)\ge\lfloor n/2\rfloor+1$, hence \[\deg(u)+\deg(w)\ge 2\left(\lfloor n/2\rfloor+1\right)\ge n+1.\] Using $N(u)\cup N(w)\subseteq V\setminus\{u,w\}$ (which has size $n-2$), we get \[ |N(u)\cap N(w)|\ge |N(u)|+|N(w)|-(n-2)\ge 3, \] so there exists $x\in N(u)\cap N(w)$ with $x\ne v$. Then $u-v-w-x-u$ is a $4$-cycle containing both $uv$ and $vw$. $\square$

Lemma 584.3 (any two edges in a $\le 6$-cycle under degree $\ge\lceil 2n/3\rceil$, $n\ge 10$). Let $H$ be a graph on $n\ge 10$ vertices with minimum degree $\delta(H)\ge \lceil 2n/3\rceil$. Then every pair of edges of $H$ is contained in a simple cycle of length at most $6$. Moreover, if the two edges share a vertex then they are contained in a $4$-cycle.

Proof. If the two edges share a vertex, the $4$-cycle claim follows from Lemma 584.2 because $\lceil 2n/3\rceil>n/2$ for all $n\ge 2$. So assume the edges are disjoint: $e_1=ab$ and $e_2=cd$ with $a,b,c,d$ all distinct.

We will build a $6$-cycle $a-b-x-c-d-y-a$. It suffices to find vertices $x,y$ such that \[ x\in N(b)\cap N(c)\setminus\{a,b,c,d\},\qquad y\in N(a)\cap N(d)\setminus\{a,b,c,d,x\}, \] and such that $x\ne y$.

First note that for any two vertices $u,v$ we have \[ |N(u)\cap N(v)|\ge \deg(u)+\deg(v)-(n-2), \] because $N(u)\cup N(v)\subseteq V\setminus\{u,v\}$ has size at most $n-2$. Applying this with $u=b,v=c$ and using $\deg(b),\deg(c)\ge\lceil 2n/3\rceil$ gives \[ |N(b)\cap N(c)|\ge 2\lceil 2n/3\rceil-(n-2). \] For $n\ge 10$, the right-hand side is at least $6$. Indeed, write $n=3q+r$ with $r\in\{0,1,2\}$. Then $\lceil 2n/3\rceil=2q$ if $r=0$, $2q+1$ if $r=1$, and $2q+2$ if $r=2$, so \[ 2\lceil 2n/3\rceil-(n-2)=\begin{cases} q+2,&r=0,\\ q+3,&r=1,\\ q+4,&r=2. \end{cases} \] When $n\ge 10$, we have $q\ge 3$, and in each case the displayed value is $\ge 6$. Therefore there exists some $x\in N(b)\cap N(c)$ avoiding the at most four forbidden vertices $\{a,b,c,d\}$. So we can choose $x\in N(b)\cap N(c)\setminus\{a,b,c,d\}$.

Similarly, \[ |N(a)\cap N(d)|\ge 2\lceil 2n/3\rceil-(n-2)\ge 6. \] We must avoid the forbidden set $\{a,b,c,d,x\}$ of size $5$, so we can choose \[y\in N(a)\cap N(d)\setminus\{a,b,c,d,x\}. \]

With these choices, the vertices $a,b,x,c,d,y$ are all distinct and all required adjacencies hold: $ab, bx, xc, cd, dy, ya$ are edges of $H$. Therefore $a-b-x-c-d-y-a$ is a simple cycle of length $6$ containing both $ab$ and $cd$. $\square$

Consequences (very dense regime). If $G$ has minimum degree at least $\lceil 2n/3\rceil$ (and in particular for all large $n\ge 10$), then taking $H_1=H_2=G$ satisfies the cycle-connectivity conditions (with cycle length $\le 6$), and $e(G)=\delta n^2$ automatically dominates $\delta^3 n^2$ and $\delta^2 n^2$ when $\delta$ is a fixed constant. This does not address the hard regime $\delta=n^{-c}$.

Fast reality check (sanity script for Lemma 584.3).

For each $n\in\{6,7,8,9,10\}$ I generated random graphs and searched for one with minimum degree at least $\lceil 2n/3\rceil$. For each such graph found, I exhaustively checked that every pair of edges lies on a cycle of length at most $6$. A witness graph was found for each $n$ and passed the check.

VERIFICATION.

Checking Lemma 584.3 details. The key step is choosing $x\in N(b)\cap N(c)$ avoiding four forbidden vertices and then choosing $y\in N(a)\cap N(d)$ avoiding five forbidden vertices. The explicit lower bound $|N(u)\cap N(v)|\ge 2\lceil 2n/3\rceil-(n-2)$ is evaluated by a $n\bmod 3$ computation to guarantee at least $6$ common neighbors for $n\ge 10$, giving the required slack. The accompanying script provides an additional sanity check for small $n$.

Quantifiers. The main open difficulty in the original problem is when $\delta$ depends on $n$ and is small; the lemmas above only address the "high minimum degree" and "linear minimum degree" preprocessing.

FINAL.

UNRESOLVED

(i) Strongest proved partial result: any graph with $e(G)\ge\delta n^2$ contains a subgraph with $\ge \delta n^2/2$ edges and minimum degree $\ge \delta n/2$ (Lemma 584.1). In the very dense regime $\delta(H)\ge\lceil 2n/3\rceil$, the whole graph is already "$C_{\le 6}$-edge-connected" in the sense that every two edges lie on a cycle of length $\le 6$ and adjacent edges lie on a $4$-cycle (Lemmas 584.2--584.3).

(ii) First gap (crisp): starting from a graph of density $\delta$ (especially $\delta=n^{-c}$), extract a subgraph $H_1$ with $\Omega(\delta^3 n^2)$ edges in which every pair of edges lies in a common cycle of length at most $6$ (and adjacent pairs in a $4$-cycle), and similarly extract $H_2$ with $\Omega(\delta^2 n^2)$ edges with cycle length bound $8$.

(iii) Top 3 next moves: 1. From Lemma 584.1, try to find a large vertex subset $U$ such that every pair of vertices in $U$ has many common neighbors (dependent random choice), then define $H_1$ by keeping edges inside $U$ (or between $U$ and a common-neighborhood set) to force many short cycles. 2. Prove a robust local-to-global statement: if every edge lies in many $4$-cycles and $6$-cycles, then there is a large subgraph where every pair of edges is cycle-connected. 3. For potential obstructions, compute extremal examples for small $n$ at densities $\delta\approx n^{-c}$ and look for graphs where all short-cycle-rich subgraphs are too small.

(iv) Minimal counterexample structure: likely a moderately sparse graph (e.g. bipartite-like or pseudorandom) where common neighborhoods are small, so $4$- and $6$-cycles are scarce and any attempt to enforce "every pair of edges on a short cycle" forces a drastic edge loss. In the hard regime $\delta=n^{-c}$, one expects any counterexample to have large girth or at least few short cycles relative to its edge count.

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.