Erdős Problem #165

Erdős Problem 165: the asymptotic constant in $R(3,k)$

Statement and outcome

The current problem asks for an asymptotic formula for $R(3,k)$, the least $n$ such that every graph on $n$ vertices contains a triangle or an independent $k$-set. This is not the sparse-ruler question appearing in the old local file with this number.

We reconstruct Shearer's upper bound \[ R(3,k)\le(1+o(1))\frac{k^2}{\log k}, \tag{1} \] including the scalar estimates needed in its induction. We also give an elementary lower bound of order $(k/\log k)^{3/2}$. The latter is substantially weaker than the published $(1/2+o(1))k^2/\log k$ lower bound of Hefty--Horn--King--Pfender. Their construction is not reproduced or used as a proved-here result.

The scalar weights

Define $f(0)=1$ and, for integers $d\ge1$, \[ f(d)=\frac{1+(d^2-d)f(d-1)}{d^2+1}, \qquad b_d=f(d-1)-f(d). \tag{2} \] We need that $f$ decreases and that $b_d$ is nonnegative and nonincreasing. Induction gives $f(d)\ge1/(d+1)$: the recurrence applied to $f(d-1)\ge1/d$ gives $f(d)\ge d/(d^2+1)\ge1/(d+1)$. Then $b_d=((d+1)f(d-1)-1)/(d^2+1)\ge0$.

For convexity, put $g_d=(3d+2)/(2d^2+6d+2)$. We have $f(0)=g_0$. Substituting $g_{d-1}$ into $2$ gives $(3d-2)/(2d^2+2d-2)\ge g_d$, the cross-multiplied difference being $4d(d-1)\ge0$. Hence $f(d)\ge g_d$. For $d\ge2$, direct subtraction gives \[ b_d-b_{d+1} =\frac{2(d^2+3d+1)f(d)-(3d+2)} {d(d-1)(d^2+2d+2)}\ge0. \] The remaining comparison is $b_1=1/2\ge b_2=1/10$.

There is also the exact identity \[ d f(d)-(d-1)f(d-1) =\frac1d-\frac{1+d(d-1)f(d-1)}{d(d^2+1)}. \tag{3} \] It first implies $d f(d)\le H_d$. For $d\ge2$, the subtracted term is at most $d^{-3}+H_{d-1}/d^2$, a summable sequence. Summing $3$ proves \[ d f(d)=\log d+O(1). \tag{4} \] This uses a summable $O(\log d/d^2)$ error; an error strictly below $1/d^2$ is neither needed nor generally valid.

Shearer's graph induction

For a triangle-free graph $G$, write $d_v=\deg(v)$ and $S(G)=\sum_v f(d_v)$. We prove $\alpha(G)\ge S(G)$ by induction on its order. Delete $i$ and its neighbours, leaving $H_i$. For a vertex $k$ at distance two from $i$, let $n_i(k)=|N(k)\cap N(i)|$. The gain available from choosing $i$ and then an independent set in $H_i$ is \[ L_i=1-f(d_i)-\sum_{j\in N(i)}f(d_j) +\sum_{\operatorname{dist}(i,k)=2} [f(d_k-n_i(k))-f(d_k)]. \] It suffices that some $L_i\ge0$. Convexity of the scalar sequence gives $f(d_k-n_i(k))-f(d_k)\ge n_i(k)b_{d_k}$. Triangle-freeness ensures that all relevant two-edge paths end at distance two, so changing the order of summation yields \[ \sum_i\sum_{\operatorname{dist}(i,k)=2} [f(d_k-n_i(k))-f(d_k)] \ge\sum_k b_{d_k}\sum_{j\in N(k)}(d_j-1) \ge\sum_k d_k(d_k-1)b_{d_k}. \] The last inequality follows edge by edge: the difference for an edge $jk$ is $(d_j-d_k)(b_{d_k}-b_{d_j})\ge0$. Consequently \[ \sum_i L_i\ge \sum_i[1-(d_i+1)f(d_i)+d_i(d_i-1)b_{d_i}]=0 \] by $2$; degree-zero terms equal zero as well. Some $L_i$ is nonnegative, completing the induction.

If $\alpha(G)<k$, every neighbourhood is independent, hence $\Delta(G)\le k-1$. Since $f$ decreases, $k>\alpha(G)\ge n f(k-1)$. Applying $4$ gives $1$.

An elementary lower construction

For large $k$, let $N=\lfloor\frac18(k/\log k)^{3/2}\rfloor$ and $p=2\log k/k$. In $G(N,p)$ the expected number of triangles is at most $N^3p^3/6\le N/48$. Markov's inequality makes the probability of more than $N/2$ triangles at most $1/24$. Meanwhile the probability of an independent $k$-set is at most \[ \binom Nk(1-p)^{\binom k2} \le\exp\left(k\log(eN/k)-p k(k-1)/2\right)=o(1). \] Thus some graph has no independent $k$-set and at most $N/2$ triangles. Delete one vertex from each triangle, removing at most $N/2$ vertices. The surviving induced graph is triangle-free, has at least $N/2$ vertices, and still has no independent $k$-set. This proves the stated weaker lower order.

Assessment and attribution

The sharp upper argument is a reconstruction of Shearer's work, using the exposition in Section 5 of Harris--Hefty--Horn--King--Pfender, https://arxiv.org/abs/2609.01782, with the scalar estimates supplied explicitly. The current lower record is documented in https://arxiv.org/abs/2510.19718. Problem: https://www.erdosproblems.com/165. The unrelated contents of the old gpt_pro_5.2/165.tex have not been reused. The asymptotic leading constant, and even a reconstruction here of a matching-order lower bound, remain unresolved in this attempt. No novelty claim is made.

COMPLETION ESTIMATE

COMPLETION: 45%

Erdos problem #165

1) FORMAL RESTATEMENT

For each integer $N\ge 1$, let $f(N)$ be the smallest size of a set $A\subseteq [N]$ such that the difference set \[ A-A:=\{a-a':a,a'\in A\} \] contains every integer $1,2,\dots,N$. The question asks whether $f(N)=N^{1-o(1)}$.

Ambiguity/typo check.

If $[N]=\{1,2,\dots,N\}$, then $A-A\subseteq\{-(N-1),\dots,N-1\}$, so it cannot contain $N$. Thus the intended $[N]$ must include both endpoints $0$ and $N$ (e.g. $[N]=\{0,1,\dots,N\}$), or the target differences should be $\{1,\dots,N-1\}$. In what follows I adopt the natural interpretation $[N]=\{0,1,\dots,N\}$ so that difference $N$ is attainable.

2) QUICK LITERATURE/CONTEXT CHECK

The problem file states:

• $f(N)\ge c N^{2/3}$ (Erdős--Olson).
• $f(N)\le N/2+2$ (Replanki--Svršek--Szabó--Wagner).
• $f(N)\le N/2+1$ for large $N$ (Hefty--Horn--King--Pfender).

I do not use these as black boxes; I re-prove a simple $\le N/2+2$ construction and a crude $\ge \sqrt N$ counting lower bound.

3) ATTACK PLAN

Give explicit construction for an $O(N)$ upper bound and basic counting for a $\Omega(\sqrt N)$ lower bound; compute exact $f(N)$ for small $N$.

4) WORK

Lemma 165.1 (simple explicit upper bound $f(N)\le \lfloor N/2\rfloor+2$).

Let $m:=\lfloor N/2\rfloor$. Then the set \[ A:=\{0,1,2,\dots,m\}\ \cup\ \{N\} \] satisfies $\{1,2,\dots,N\}\subseteq A-A$. Hence \[ f(N)\le (m+1)+1=\lfloor N/2\rfloor+2. \]

Proof. First, for $1\le d\le m$, we have $d=d-0\in A-A$ since both $d$ and $0$ lie in $A$. Second, for $m< d\le N$, write $d=N-(N-d)$. Because $d>m$ we have $N-d < N-m\le m$ (since $m=\lfloor N/2\rfloor$), so $N-d\in\{0,1,\dots,m\}\subseteq A$. Also $N\in A$. Thus $d=N-(N-d)\in A-A$. Therefore every $d\in\{1,\dots,N\}$ lies in $A-A$. $\square$

Lemma 165.2 (counting lower bound $f(N)\ge (1+\sqrt{1+4N})/2$).

If $A\subseteq\{0,1,\dots,N\}$ satisfies $\{1,\dots,N\}\subseteq A-A$ and $|A|=m$, then \[ m(m-1)\ge N\quad\text{and hence}\quad m\ge \frac{1+\sqrt{1+4N}}{2}. \] In particular, $f(N)\ge \sqrt N$ up to constants.

Proof. For each $d\in\{1,\dots,N\}$ choose one ordered pair $(a_d,b_d)\in A^2$ with $a_d-b_d=d$. These pairs are all distinct because their differences are distinct. There are $N$ such ordered pairs with $a_d\ne b_d$, and the number of ordered pairs with distinct elements is at most $m(m-1)$. Thus $m(m-1)\ge N$. Solving gives the claimed bound. $\square$

FAST REALITY CHECK (computed exact values for $N\le 12$).

By brute force over subsets of $\{0,1,\dots,N\}$, the exact values of $f(N)$ for $1\le N\le 12$ are: \[ \begin{array}{c|cccccccccccc} N&1&2&3&4&5&6&7&8&9&10&11&12\\\hline f(N)&2&3&3&4&4&4&5&5&5&6&6&6 \end{array} \] One achieving set for each $N$ (not unique): \[ \begin{array}{c|l} N & A \\\hline 1&(0,1)\\ 2&(0,1,2)\\ 3&(0,1,3)\\ 4&(0,1,3,4)\\ 5&(0,1,3,5)\\ 6&(0,2,5,6)\\ 7&(0,1,3,6,7)\\ 8&(0,1,3,6,8)\\ 9&(0,1,3,7,9)\\ 10&(0,1,4,8,9,10)\\ 11&(0,1,4,8,9,11)\\ 12&(0,2,5,10,11,12) \end{array} \]

5) VERIFICATION

• Lemma 165.1: the two ranges $d\le \lfloor N/2\rfloor$ and $d>\lfloor N/2\rfloor$ are covered by differences inside the initial segment and differences from $N$ to the initial segment.
• Lemma 165.2: injection from required differences to ordered pairs with distinct entries.
• Computation: exhaustive for $N\le 12$.

6) FINAL

UNRESOLVED

1. (i) Strongest fully proved partial result obtained here. A simple explicit construction gives $f(N)\le \lfloor N/2\rfloor+2$ (Lemma 165.1), while counting gives $f(N)\ge (1+\sqrt{1+4N})/2$ (Lemma 165.2).

2. (ii) Exact first gap. Bridge the gap between $\Omega(\sqrt N)$ and $O(N)$, in particular decide whether $f(N)$ must be $N^{1-o(1)}$ (almost linear) or can be substantially smaller.

3. (iii) Top 3 next moves (concrete targets).
   1. Improve the lower bound by using additive-combinatorial structure of difference covers: show $A-A$ cannot contain a full interval unless $|A|$ is large.
   2. Search for better explicit constructions beating $N/2+2$ substantially (if possible), perhaps via multi-scale sets.
   3. Compute $f(N)$ for $N\le 50$ by ILP/SAT to guess the growth and test conjectures.

4. (iv) Minimal counterexample structure (if $f(N)=N^{1-o(1)}$ is false). One would need an explicit family $A_N\subseteq\{0,1,\dots,N\}$ with $|A_N|\le N^{1-\varepsilon}$ for some fixed $\varepsilon>0$ and with $\{1,\dots,N\}\subseteq A_N-A_N$. Such sets would provide "difference bases" with sublinear size.