\documentclass[11pt,leqno]{amsart} \usepackage[letterpaper,margin=1in]{geometry} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage{amsmath,amssymb,mathtools} \usepackage{microtype} \usepackage{enumitem} \usepackage[hidelinks]{hyperref} \hypersetup{ pdftitle={A locally sparse graph with superlinear Ramsey growth}, pdfauthor={Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer}, pdfsubject={A counterexample to Erdos problem 566}, pdfkeywords={Ramsey theory, locally sparse graphs, entropy, Hamming cube} } \numberwithin{equation}{section} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \DeclareMathOperator{\Var}{Var} \DeclareMathOperator{\supp}{supp} \newcommand{\E}{\mathbb E} \newcommand{\Prob}{\mathbb P} \newcommand{\F}{\mathbb F} \newcommand{\one}{\mathbf 1} \newcommand{\HH}{\mathrm H} \newcommand{\dist}{\mathrm d} \newcommand{\eps}{\varepsilon} \newcommand{\set}[1]{\{#1\}} \newcommand{\abs}[1]{\lvert#1\rvert} \newcommand{\norm}[1]{\lVert#1\rVert} \newcommand{\floor}[1]{\lfloor#1\rfloor} \newcommand{\ceil}[1]{\lceil#1\rceil} \newcommand{\bin}[2]{\binom{#1}{#2}} \newcommand{\R}{\mathbb R} \setlist[enumerate]{leftmargin=2em,itemsep=2pt,topsep=5pt} \setlength{\emergencystretch}{1.5em} \allowdisplaybreaks[2] \title[Locally sparse graphs and Ramsey growth]{A locally sparse graph with superlinear Ramsey growth} \author[Howe, Huffman, Kohlmeyer, and Kruer]{Will Howe, Grant Huffman, Jensen Kohlmeyer, and Liam Kruer} \date{November 11, 2026} \subjclass[2020]{05C55, 05D40} \keywords{Ramsey numbers, locally sparse graphs, entropy, Hamming cube, Krawtchouk polynomials} \thanks{Electronic addresses are \href{mailto:howew@purdue.edu}{\nolinkurl{howew@purdue.edu}} (W. Howe), \href{mailto:huffma97@purdue.edu}{\nolinkurl{huffma97@purdue.edu}} (G. Huffman), \href{mailto:jenwin@purdue.edu}{\nolinkurl{jenwin@purdue.edu}} (J. Kohlmeyer), and \href{mailto:kruerl@purdue.edu}{\nolinkurl{kruerl@purdue.edu}} (L. Kruer).} \begin{document} \begin{abstract} We construct a fixed finite bipartite graph $G$ such that every set of at least two vertices spans at most twice its cardinality minus three edges, while the ratio $R(G,H)/e(H)$ is unbounded as $H$ ranges over graphs without isolated vertices. For all sufficiently large $m$, \[ R\bigl(G,K_{2^{570m}}\bigr)>2^{1144m-1}. \] This gives a negative answer to Erd\H{o}s problem 566. The construction uses a layered two-parent graph and a random subset of a Hamming cube. A conditional-entropy inequality excludes the fixed graph, and a bound on the negative Krawtchouk spectrum, followed by an independent-set encoding, excludes large independent sets. We give the complete argument, including the finite scalar estimates. \end{abstract} \maketitle \section{Introduction} For finite simple graphs $G$ and $H$, let $R(G,H)$ be the least integer $n$ such that every red-blue coloring of the edges of $K_n$ contains a red copy of $G$ or a blue copy of $H$. Copies are subgraphs. Write $e(H)$ for the number of edges of $H$. Erd\H{o}s, Faudree, Rousseau, and Schelp \cite{EFRS} call a graph $G$ \emph{Ramsey size-linear} if there is a constant $C_G$ such that \begin{equation}\label{eq:size-linear} R(G,H)\le C_G e(H) \end{equation} for every finite simple graph $H$ without isolated vertices. They asked whether the local condition \begin{equation}\label{eq:local-condition} e(G[W])\le 2\abs{W}-3 \qquad\text{for every }W\subseteq V(G)\text{ with }\abs{W}\ge2 \end{equation} implies \eqref{eq:size-linear}. This question is recorded as Erd\H{o}s problem 566 \cite{Bloom}. The formulation using all subgraphs is equivalent to \eqref{eq:local-condition}, because each subgraph is contained in the induced subgraph on its vertex set. \begin{theorem}\label{thm:main} There is a fixed finite bipartite, $2$-degenerate graph $G$ satisfying \eqref{eq:local-condition} such that, for every sufficiently large positive integer $m$, \begin{equation}\label{eq:main-bound} R\bigl(G,K_{2^{570m}}\bigr)>2^{1144m-1}. \end{equation} In particular, \begin{equation}\label{eq:main-ratio} \frac{R\bigl(G,K_{2^{570m}}\bigr)}{e\bigl(K_{2^{570m}}\bigr)}>2^{4m}. \end{equation} \end{theorem} The graph $G$ has finitely many layers. Each vertex after the first layer represents a pair of vertices in the preceding layer and is joined to those two vertices. The layered construction, the entropy-potential approach, and the use of profiles to count child arrays originate in Chapter 10 of OpenAI \cite{OpenAI}. We use a different entropy parameter and apply the construction inside a single randomly sampled cube. The independent-set encoding used later is the Kleitman--Winston method, for which \cite[Section 3]{BTW} gives an account. The specific estimates required here are proved below. We prove that one random vertex set simultaneously supports a $G$-free short-distance graph and has small independence number. Coloring its complement blue then yields \eqref{eq:main-bound}. \section{Entropy estimates} All entropies and logarithms denoted by $\log_2$ use base two. Natural logarithms are denoted by $\ln$. Set \begin{equation}\label{eq:constants} \tau=\frac{43}{100},\qquad \beta=\frac{4857}{5000},\qquad w=\frac9{16},\qquad \sigma=-\log_2 w. \end{equation} The binary entropy function is \[ h(x)=-x\log_2 x-(1-x)\log_2(1-x),\qquad 0\le x\le1, \] with the endpoint values defined by continuity. We shall use \begin{equation}\label{eq:scalar-bounds} \begin{aligned} .94268&1. \end{equation} \end{lemma} \begin{proof} We have $0<\sigma<1$. For $0.9714-.97135-.00002=.00003. \] Multiplying by $2t=40000$ proves \eqref{eq:depth-margin}. \end{proof} \section{Excluding the fixed graph in a sampled cube} From now on, $N$ tends to infinity through positive multiples of $40000$. Let \begin{equation}\label{eq:cube-parameters} U_N=\{0,1\}^N,\qquad Q=2^N,\qquad k=\tau N,\qquad p=2^{-\beta N}. \end{equation} Then $k$ is an even integer. The graph $B_N$ on $U_N$ joins two distinct words when their Hamming distance is at most $k$. Each word is retained independently with probability $p$ to form a random set $S$. We shall prove that $B_N[S]$ is $G$-free with probability tending to one. \subsection{Counting child arrays} Consider a single transition with $L$ parents and $M=\binom L2$ children. Fix an ordered parent array $u=(u_1,\ldots,u_L)\in U_N^L$. A child array $z\in U_N^M$ assigns a word to each unordered pair of parent indices. For coordinate $j$, choose a child index uniformly and orient its two parents by a fair coin. Denote the parent bits by $X_j,Y_j$ and the child bit by $Z_j$. Define \begin{equation}\label{eq:profile-entropy} E(u,z)=\frac1N\sum_{j=1}^N\HH(Z_j\mid X_j,Y_j). \end{equation} \begin{lemma}\label{lem:array-count} For a fixed parent array $u$, the number of child arrays satisfying $E(u,z)\le\beta-\delta$ is at most \begin{equation}\label{eq:array-count} (M+1)^{3N}2^{NM(\beta-\delta)}. \end{equation} \end{lemma} \begin{proof} At each coordinate, split the child indices into the three groups corresponding to unordered parent types $00$, $01$, and $11$. Let their sizes be $M_{00},M_{01},M_{11}$, and let $a_{00},a_{01},a_{11}$ count the child bits equal to one in these groups. The three counts have at most $(M+1)^3$ possibilities. For a specified triple, the number of child-bit assignments is \[ \prod_{g\in\{00,01,11\}}\binom{M_g}{a_g} \le 2^{\sum_g M_g h(a_g/M_g)}, \] by \eqref{eq:binomial-entropy}, with an empty group contributing zero to the exponent. The fair orientation of a mixed parent pair gives the same conditional child distribution for parent types $01$ and $10$. Hence the exponent is exactly $M\HH(Z_j\mid X_j,Y_j)$. Specify such a triple at every coordinate. There are at most $(M+1)^{3N}$ resulting profiles, and for each profile the total number of arrays is at most $2^{NM E(u,z)}$. Summing over the profiles with $E(u,z)\le\beta-\delta$ proves the lemma. \end{proof} \subsection{The entropy potential across layers} \begin{proposition}\label{prop:red-free} For the fixed graph $G$ of Section~3, \begin{equation}\label{eq:red-failure} \Prob\bigl(G\subseteq B_N[S]\bigr)\le t2^{-N}. \end{equation} \end{proposition} \begin{proof} For a transition with $L$ parents and $M$ children, call a child array distinct if its $M$ words are pairwise distinct. Every particular distinct child array is contained in $S$ with probability $p^M$. There are $Q^L$ possible parent arrays. Lemmas~\ref{lem:array-count} and \ref{lem:fixed-margins}, followed by the union bound, show that the probability of a parent array and a distinct surviving child array with $E(u,z)\le\beta-\delta$ is at most \begin{align*} Q^L(M+1)^{3N}2^{NM(\beta-\delta)}p^M &=2^{N[L+3\log_2(M+1)-\delta M]}\\ &\le2^{-N}. \end{align*} This calculation counts all parent arrays, regardless of whether their words survive. Taking a union bound over the $t$ transitions gives an event of probability at least $1-t2^{-N}$ on which every distinct surviving child array at every transition has entropy greater than $\beta-\delta$. Suppose this event holds and there is an injective copy of $G$ in $B_N[S]$. For coordinate $j$, let $q_{i,j}$ be the proportion of ones among the images of the vertices in layer $V_i$, and put \[ \Phi_i=\frac1N\sum_{j=1}^N h(q_{i,j}). \] We have $0\le\Phi_i\le1$. For the transition from $V_{i-1}$ to $V_i$, let $E_i$ be the quantity \eqref{eq:profile-entropy}. The child images are distinct and survive, so $E_i>\beta-\delta$. Let $d_{i,j}$ be the average of the two parent-child disagreement probabilities at coordinate $j$. Every parent-child edge of the copy has Hamming distance at most $k$. Averaging over all $2L_i$ parent-child edges therefore gives \[ \frac1N\sum_{j=1}^N d_{i,j}\le\frac{k}{N}=\tau. \] At each coordinate the oriented parent pair is a uniformly sampled pair of distinct indices from the parent layer. Apply Lemma~\ref{lem:without-replacement} and average over coordinates. By \eqref{eq:theta-identity}, \[ E_i\le\theta+\frac{\Phi_i-\Phi_{i-1}}2+\eta(L_{i-1}) <\theta+\frac{\Phi_i-\Phi_{i-1}}2+\delta. \] Thus \[ \Phi_i-\Phi_{i-1}>2(\beta-\theta-2\delta). \] Summing for $1\le i\le t$ and using \eqref{eq:depth-margin} yields $\Phi_t-\Phi_0>1$, contradicting $0\le\Phi_0,\Phi_t\le1$. Therefore the event under consideration is $G$-free, which proves \eqref{eq:red-failure}. \end{proof} \section{The spectrum of the Hamming ball} We next control independent sets of $B_N$. Let $T$ be the real symmetric matrix indexed by $U_N$ with \[ T(x,y)=\one_{\dist(x,y)\le k}. \] Its diagonal entries are one and its constant row sum is \begin{equation}\label{eq:degree} D=\sum_{j=0}^k\binom Nj. \end{equation} By \eqref{eq:binomial-entropy} and the monotonicity of $h$ on $[0,1/2]$, \begin{equation}\label{eq:D-bounds} \frac{2^{Nh(\tau)}}{N+1}\le D\le(N+1)2^{Nh(\tau)}. \end{equation} In particular $D=2^{(h(\tau)+o(1))N}$. \subsection{Characters and Krawtchouk polynomials} Identify $U_N$ with $\F_2^N$ and write $\abs x$ for the Hamming weight of a word $x$. For $b\in\F_2^N$, define \[ \chi_b(x)=(-1)^{b\cdot x}. \] The characters are orthogonal under summation over $U_N$, each with squared norm $Q$. As $T(x,y)$ depends only on $x+y$, each character is an eigenvector. Define $K_j^{(n)}(v)$ by \begin{equation}\label{eq:K-generating} (1-z)^v(1+z)^{n-v}=\sum_{j=0}^n K_j^{(n)}(v)z^j. \end{equation} Equivalently, \[ K_j^{(n)}(v)=\sum_{a=0}^j(-1)^a\binom va\binom{n-v}{j-a}. \] Using the polynomial definition of the binomial coefficients extends $K_j^{(n)}$ to a polynomial in the real variable $v$. If $\abs{b}=i$, summing $\chi_b$ over words of a given weight shows that its eigenvalue is \[ \lambda_i=\sum_{j=0}^k K_j^{(N)}(i). \] We have $\lambda_0=D$. For $1\le i\le N$, coefficient extraction gives \begin{equation}\label{eq:partial-sum} \lambda_i=[z^k]\frac{(1-z)^i(1+z)^{N-i}}{1-z} =K_k^{(N-1)}(i-1). \end{equation} \begin{lemma}\label{lem:root-location} Let $1\le k\le(n+1)/2$ be even. If $K_k^{(n)}(v)<0$ for an integer $0\le v\le n$, then \begin{equation}\label{eq:root-location} \abs{n-2v}<2\sqrt{k(n-k+1)}. \end{equation} \end{lemma} \begin{proof} Put $x=n-2v$. Differentiating \eqref{eq:K-generating} and comparing coefficients gives \[ (j+1)K_{j+1}=xK_j-(n-j+1)K_{j-1}. \] Thus the monic polynomials $P_j(x)=j!K_j^{(n)}((n-x)/2)$ satisfy \begin{equation}\label{eq:monic-recurrence} P_0=1,\qquad P_1=x,\qquad P_{j+1}=xP_j-j(n-j+1)P_{j-1}. \end{equation} The determinant recurrence identifies $P_k$ with the characteristic polynomial of the real symmetric $k\times k$ tridiagonal matrix having zero diagonal and off-diagonal entries \[ \sqrt{j(n-j+1)},\qquad 1\le j\le k-1. \] All roots are real. Each eigenvalue has absolute value at most the maximal absolute row sum, which is at most $2\sqrt{k(n-k+1)}$. Here $j(n-j+1)$ is increasing for $0\le j\le(n+1)/2$. The monic polynomial $P_k$ is positive to the right of its largest root. Recurrence \eqref{eq:monic-recurrence} also gives $P_k(-x)=(-1)^kP_k(x)$. Since $k$ is even, $P_k$ is positive on both exterior intervals beyond the indicated root bound, and is nonnegative at the endpoints. A negative value must satisfy \eqref{eq:root-location}. \end{proof} \begin{lemma}\label{lem:K-parseval} For $0\le k\le n$, \begin{equation}\label{eq:K-parseval} \sum_{v=0}^n\binom nv K_k^{(n)}(v)^2=2^n\binom nk. \end{equation} \end{lemma} \begin{proof} On $\F_2^n$, let $f(x)=\one_{\abs{x}=k}$ and define the unnormalized Fourier coefficient $\widehat f(b)=\sum_x f(x)\chi_b(x)$. If $\abs b=v$, then \eqref{eq:K-generating} gives $\widehat f(b)=K_k^{(n)}(v)$. Orthogonality gives \[ \sum_b\widehat f(b)^2 =\sum_{x,y}f(x)f(y)\sum_b\chi_b(x+y) =2^n\sum_x f(x)^2 =2^n\binom nk. \] Grouping $b$ by its weight proves \eqref{eq:K-parseval}. \end{proof} \subsection{A bound on the negative eigenvalues} \begin{proposition}\label{prop:negative-spectrum} For all sufficiently large admissible $N$, every eigenvalue of $T$ is at least $-\Lambda$, where \begin{equation}\label{eq:spectral-decay} \frac{\Lambda}{D}\le2^{-.0152N}. \end{equation} \end{proposition} \begin{proof} Set $n=N-1$. Since $k=\tau N$ is even and $k\le(n+1)/2$, Lemma~\ref{lem:root-location} applies. If the eigenvalue in \eqref{eq:partial-sum} is negative, with $v=i-1$, then \[ \frac12-\frac{\sqrt{k(n-k+1)}}n <\frac vn< \frac12+\frac{\sqrt{k(n-k+1)}}n. \] Now \[ \frac{\sqrt{k(n-k+1)}}n =\frac{N}{N-1}\sqrt{\tau(1-\tau)}. \] The exact inequality $.4951^2=.24512401>.2451=\tau(1-\tau)$ implies \[ \frac12-\sqrt{\tau(1-\tau)}>.0049. \] Consequently every negative eigenvalue has $v/n\in[.0049,.9951]$ for all sufficiently large $N$. By Lemmas~\ref{lem:elementary-entropy} and \ref{lem:K-parseval}, \begin{align*} \abs{K_k^{(n)}(v)}^2 &\le \frac{2^n\binom nk}{\binom nv}\\ &\le(n+1)\,2^{n[1+h(k/n)-h(v/n)]}\\ &\le(n+1)\,2^{n[1+h(k/n)-h(.0049)]}. \end{align*} In the last step we use the symmetry and monotonicity of binary entropy. Since $k/n\to\tau$, this bounds the magnitude of every negative eigenvalue by \[ 2^{\left(\frac{1+h(\tau)-h(.0049)}2+o(1)\right)N}. \] After division by the lower bound in \eqref{eq:D-bounds}, the exponent becomes \[ -\frac{h(\tau)+h(.0049)-1}{2}+o(1). \] The estimates \eqref{eq:scalar-bounds} give \[ \frac{h(\tau)+h(.0049)-1}{2}>.015225>.0152. \] Taking $\Lambda$ to be the larger of zero and the magnitude of the most negative eigenvalue proves \eqref{eq:spectral-decay}. \end{proof} \section{Independent-set containers and random thinning} Put \begin{equation}\label{eq:container-parameters} M_N=\ceil{2^{.985N}},\qquad b_N=2^{.01425N}. \end{equation} For admissible $N=40000m$, we have $b_N=2^{570m}$. \subsection{Supersaturation} \begin{lemma}\label{lem:supersaturation} For all sufficiently large admissible $N$, every $W\subseteq U_N$ with $\abs W\ge M_N$ contains a vertex whose degree in $B_N[W]$ is at least \begin{equation}\label{eq:large-degree} \frac{D\abs W}{4Q}. \end{equation} \end{lemma} \begin{proof} Decompose $\one_W=(\abs W/Q)\one+f$, where $f$ is orthogonal to the constant vector. Proposition~\ref{prop:negative-spectrum} and $\norm f^2=\abs W-\abs W^2/Q\le\abs W$ give \[ \one_W^{\mathsf T}T\one_W \ge \frac{D\abs W^2}{Q}-\Lambda\abs W. \] Since $\abs W/Q\ge2^{-.015N}$ and $\Lambda/D\le2^{-.0152N}$, for large $N$ the second term is at most half the first. Hence \[ \one_W^{\mathsf T}T\one_W\ge\frac{D\abs W^2}{2Q}. \] There is one diagonal entry for each vertex, so \[ \frac{2e(B_N[W])}{\abs W} =\frac{\one_W^{\mathsf T}T\one_W-\abs W}{\abs W} \ge\frac{D\abs W}{2Q}-1. \] By \eqref{eq:D-bounds}, $DM_N/Q\to\infty$. The last expression is therefore at least $D\abs W/(4Q)$, uniformly for $\abs W\ge M_N$. Some vertex has at least the average degree. \end{proof} \subsection{A deterministic encoding} Fix a total order of $U_N$ to resolve ties between vertices of the same degree. Given an independent set $I$ of $B_N$, start with $W=U_N$ and an empty set $F$. While $\abs W\ge M_N$, take a vertex $x$ of maximum degree in $B_N[W]$ and do the following. \begin{enumerate} \item If $x\notin I$, delete $x$ from $W$. \item If $x\in I$, add $x$ to $F$ and delete $x$ and all its current neighbors from $W$. \end{enumerate} Write $W_F$ for the set remaining when the procedure stops. Independence implies \begin{equation}\label{eq:container-cover} I\subseteq F\cup W_F,\qquad \abs{W_F}\abs S\ge\frac12 2^{(1-\beta)N}. \] Taking $N=40000m$ gives \[ b_N=2^{570m},\qquad (1-\beta)N=1144m, \] and proves \eqref{eq:main-bound}. For these cliques, \[ e\bigl(K_{2^{570m}}\bigr) =\frac{2^{570m}(2^{570m}-1)}2<2^{1140m-1}. \] Division proves \eqref{eq:main-ratio}. The cliques have no isolated vertices. Their ratios tend to infinity while $G$ remains fixed, which disproves \eqref{eq:size-linear} for a graph satisfying the full local hypothesis \eqref{eq:local-condition}. \end{proof} \appendix \section{Exact scalar inequalities}\label{app:scalars} This appendix gives rational certificates for \eqref{eq:scalar-bounds}. For $1\le y\le2$, set \[ s(y)=2\sum_{j=0}^{15}\frac{1}{2j+1} \left(\frac{y-1}{y+1}\right)^{2j+1}, \qquad \rho=\frac{3}{44\cdot3^{33}}. \] The expansion $\ln y=2\operatorname{artanh}((y-1)/(y+1))$ has nonnegative terms. Since $(y-1)/(y+1)\le1/3$, its omitted tail satisfies \[ 0\le\ln y-s(y) \le\frac{2(1/3)^{33}}{33(1-1/9)}=\rho<10^{-16}. \] Thus \begin{equation}\label{eq:log-enclosure} s(y)\le\ln y\le s(y)+\rho. \end{equation} Let $\ell=s(2)$. For a rational $x=2^e y\in(0,1)$ with $1\le y\le2$ and $e<0$, define \[ L_x=s(y)+e(\ell+\rho),\qquad U_x=s(y)+\rho+e\ell. \] Equation \eqref{eq:log-enclosure} implies $L_x\le\ln x\le U_x$. Define the rational numbers \[ A_x=-xU_x-(1-x)U_{1-x},\qquad B_x=-xL_x-(1-x)L_{1-x}. \] For the three arguments below, $A_x>0$, and therefore \begin{equation}\label{eq:entropy-enclosure} \frac{A_x}{\ell+\rho}\le h(x)\le\frac{B_x}{\ell}. \end{equation} The required power-of-two reductions are \[ \begin{array}{c|cc|cc} x&e&y&e'&y'\\ \hline 9/25&-2&36/25&-1&32/25\\ 43/100&-2&43/25&-1&57/50\\ 49/10000&-8&784/625&-1&9951/5000 \end{array} \] where $x=2^e y$ and $1-x=2^{e'}y'$. To make the final comparisons explicit, take \[ \begin{array}{c|cc} x&a_x&b_x\\ \hline 9/25&94268/100000&94270/100000\\ 43/100&98581/100000&98582/100000\\ 49/10000&4464/100000&4465/100000. \end{array} \] Substitution in the finite rational sums gives, in all three rows, \begin{equation}\label{eq:rational-certificates} A_x-a_x(\ell+\rho)>\frac1{10^7},\qquad b_x\ell-B_x>\frac1{10^7}. \end{equation} These inequalities involve rational numbers alone and follow by clearing their positive denominators. They imply $A_x>0$ and, together with \eqref{eq:entropy-enclosure}, prove $a_x\frac{43\cdot57}{10000}, \] and the direct consequences \[ \frac{h(.43)+h(.0049)-1}{2}>.015225, \qquad 1-h(.43)<.01419. \] All decimal constants in the proof are terminating decimals and hence denote exact rational numbers. \section*{Acknowledgment} The authors acknowledge assistance from OpenAI's ChatGPT in developing and checking the argument and in preparing the exposition. \begin{thebibliography}{9} \bibitem{BTW} J. Balogh, A. Treglown, and A. Z. Wagner, \emph{Applications of graph containers in the Boolean lattice}, Random Structures Algorithms \textbf{49} (2016), no. 4, 845--872. \href{https://doi.org/10.1002/rsa.20666}{doi:10.1002/rsa.20666}. \bibitem{Bloom} T. F. Bloom, \emph{Erd\H{o}s problems, Problem 566}, \url{https://www.erdosproblems.com/566}, accessed November 11, 2026. \bibitem{EFRS} P. Erd\H{o}s, R. J. Faudree, C. C. Rousseau, and R. H. Schelp, \emph{Ramsey size linear graphs}, Combin. Probab. Comput. \textbf{2} (1993), no. 4, 389--399. \href{https://doi.org/10.1017/S096354830000078X}{doi:10.1017/S096354830000078X}. \bibitem{OpenAI} OpenAI, \emph{Ten advances in mathematics and theoretical computer science}, preprint, updated August 6, 2026, Chapter 10, pp. 236--248. \url{https://cdn.openai.com/pdf/ten-proofs-oai.pdf}. \end{thebibliography} \end{document}