Exact determination of the Erdős–Reid–Schelp–Staton function $q(n,j,l)$: the minimum size of a graph in which every $n+j$ vertices induce a subgraph of maximum degree at least $n$

For integers $n \ge 1$, $j \ge 1$, $l \ge 0$, let $q(n,j,l)$ — written $m(n,k,j)$ with $k=j+l$ by Erdős, Reid, Schelp and Staton (1996) — be the minimum number of edges of a graph on $n+j+l$ vertices in which every $n+j$ vertices induce a subgraph of maximum degree at least $n$. The join $K_{l+1}+E_n$ with $j-1$ added isolated vertices shows $q(n,j,l) \le (l+1)n+\binom{l+1}{2}$ (the join bound), and Erdős–Reid–Schelp–Staton conjectured equality throughout the range $n \ge j+l$ (i.e. $k \le n$). Pikhurko and Thomason (2002) disproved this conjecture when $j$ and $l$ are both $\Omega(n)$ and determined the asymptotics $q(n,j,l)=(1+o(1))\,(1+l/(2n+2j))(l+1)n$ for $l=o(n(n+j)/\log n)$; they also proved the join bound exactly in an extended range and showed it fails for $n<(j-1)l$. The surviving open problem is the exact determination of $q(n,j,l)$: characterizing precisely the triples for which the join bound holds, computing exact values in the remaining regimes (the band between the known failure and success thresholds, and $l$ much larger than $n$), and deciding the associated question whether counterexamples to the Erdős decomposition property exist on exactly $2n+2$ vertices (the smallest known have $2n+80$).

Background

Fix integers $n \ge 1$, $j \ge 1$, $l \ge 0$ and put $k=j+l$. Write $\Delta(H)$ for the maximum degree of a graph $H$, and $\binom{a}{2}$ for the number of edges of the complete graph $K_a$. Erdős, Reid, Schelp and Staton (1996) introduced the extremal function

$m(n,k,j) \;=\; \min\Big\{\, |E(G)| \;:\; |V(G)|=n+k,\ \text{every } n+j \text{ vertices of } G \text{ induce a subgraph } H \text{ with } \Delta(H) \ge n \,\Big\},$

the least number of edges forcing the local property that every $(n+j)$-vertex subset spans a vertex adjacent, within the subset, to at least $n$ others. Pikhurko and Thomason (2002) write $q(n,j,l)$ for the same function with $k=j+l$ (the graph has $n+j+l$ vertices); that notation is used throughout. In the complement the local condition reads: every $(n+j)$-vertex induced subgraph of $\bar{G}$ has a vertex of degree less than $j$.

The join construction is central: $K_{l+1}+E_n$ (a complete graph on $l+1$ vertices completely joined to $n$ mutually non-adjacent vertices), together with $j-1$ isolated vertices, has $n+j+l$ vertices, satisfies the local condition, and has exactly $(l+1)n+\binom{l+1}{2}$ edges. Hence $q(n,j,l) \le (l+1)n+\binom{l+1}{2}$, called the join bound below; Pikhurko and Thomason call this the "obvious construction".

The problem descends from a 1981 question of Erdős, as recounted by Pikhurko and Thomason (2002): is every graph with fewer than $\binom{2n+1}{2}-\binom{n}{2}$ edges the edge-disjoint union of a bipartite graph and a graph of maximum degree less than $n$? Equivalently, is the restricted size Ramsey number $\hat{r}(K_{1,n},\mathcal{C}_{odd})$ — the minimum number of edges of a graph whose every red/blue edge-coloring contains a red star $K_{1,n}$ or a blue odd cycle — equal to $\binom{2n+1}{2}-\binom{n}{2}$, the number of edges of the join $P_{n+1,n}=K_{n+1}+E_n$? Faudree (as recounted by Pikhurko and Thomason) showed the statement holds on $2n+1$ vertices, and Erdős and Faudree believed no counterexample exists on exactly $2n+2$ vertices. Pikhurko (2001) disproved the conjecture in general, proving $n^2+(0.577+o(1))\,n^{3/2} < \hat{r}(K_{1,n},\mathcal{C}_{odd}) \le \hat{r}(K_{1,n},K_3) < n^2+2n^{3/2}+n$. Erdős, Reid, Schelp and Staton (1996) introduced $m(n,k,j)$ as a sharper attack on this circle of problems: for $k=n+1$ their bound is exactly the Faudree statement, their theorem for $j=1$ and their theorem for $j \ge 2$ under $n \ge \max\{\,j(k-j),\,\binom{k-j+2}{2}\,\}$ are the positive results, and they constructed counterexamples for $j=2$ with very large $k$ (complements of high-girth graphs), so the critical range is $k \le n$. Their Conjecture 1 asserted that the join bound holds for every triple with $n \ge j+l$.

Pikhurko and Thomason (2002) showed the conjecture is false in that range: they proved $m(n,k,j)=(1+o(1))\,(1+\frac{k-j}{2n+2j})(k-j+1)n$ for $k=o(n(n+j)/\log n)$, and their upper bound is below the join bound whenever $j$ and $k-j$ are both $\Omega(n)$. Exactly, they proved the join-bound equation fails for $n<(j-1)l$ (explicit constructions) and holds in an extended range beyond $n \ge \max\{jl,\binom{l+2}{2}\}$ (their Theorem 14, an improvement when $j$ is smaller than about $l/2$), concluding that $jl$ is roughly the threshold on $n$ below which the join construction fails to be extremal. They also constructed the smallest known counterexamples to the decomposition question, on $2n+80$ vertices for large $n$. At $n=1$ the problem is Turán-type: $q(1,j,l)=\binom{1+j+l}{2}-\operatorname{ex}(1+j+l,K_{j+1})$, where $\operatorname{ex}(N,K_{j+1})$ is the Turán number (the maximum number of edges in an $N$-vertex graph with no $(j+1)$-clique); for $l$ much larger than $n$, Pikhurko and Thomason state that "the overall situation is not clear".

Problem Statement

Let $n \ge 1$, $j \ge 1$, $l \ge 0$ be integers and let

$q(n,j,l) \;=\; \min\Big\{\, |E(G)| \;:\; |V(G)|=n+j+l,\ \text{every } n+j \text{ vertices of } G \text{ induce a subgraph of maximum degree at least } n \,\Big\}$

(the function $m(n,k,j)$ of Erdős–Reid–Schelp–Staton with $k=j+l$). Determine $q(n,j,l)$ exactly for every triple $(n,j,l)$, and decide the associated decomposition question of item (3) below:

(1) Characterize precisely the triples $(n,j,l)$ for which the join bound holds, $q(n,j,l)=(l+1)n+\binom{l+1}{2}$, the value attained by $K_{l+1}+E_n$ with $j-1$ isolated vertices. It is currently known to hold for $j=1$, for $n \ge \max\{jl,\binom{l+2}{2}\}$, and in the further range proved by Pikhurko–Thomason's Theorem 14, and to fail for $n<(j-1)l$; the band in between — roughly $n$ near $jl$ — is unresolved.

(2) Determine the exact value of $q(n,j,l)$ in all regimes where the join bound fails, including the regime $l$ much larger than $n$, where Pikhurko–Thomason state the situation is "not clear" and where at $n=1$ the answer is the Turán-type formula $q(1,j,l)=\binom{1+j+l}{2}-\operatorname{ex}(1+j+l,K_{j+1})$.

(3) Decide whether every graph on exactly $2n+2$ vertices with fewer than $\binom{2n+1}{2}-\binom{n}{2}$ edges is the edge-disjoint union of a bipartite graph and a graph of maximum degree less than $n$: no counterexample on $2n+1$ vertices exists (Faudree), Erdős and Faudree believed none exist on $2n+2$ vertices, and the smallest known counterexamples have $2n+80$ vertices for large $n$ (Pikhurko–Thomason).

References

1. Paul Erdős, Talmage James Reid, Richard Schelp, William Staton, "Sizes of graphs with induced subgraphs of large maximum degree", Discrete Mathematics 158 (1996) 283–286. DOI: 10.1016/0012-365X(95)00008-K, https://doi.org/10.1016/0012-365X(95)00008-K.
2. Oleg Pikhurko, "Size Ramsey Numbers of Stars Versus 3-chromatic Graphs", Combinatorica 21(3) (2001) 403–412. DOI: 10.1007/s004930100004, https://doi.org/10.1007/s004930100004. Full text available at the author's copy: https://pikhurko.github.io/E/Pikhurko01c.pdf.
3. Oleg Pikhurko, Andrew Thomason, "Disjoint subgraphs of large maximum degree", Discrete Mathematics 248(1–3) (2002) 125–141. DOI: 10.1016/S0012-365X(01)00190-X, https://doi.org/10.1016/S0012-365X(01)00190-X. Full text available at the author's copy: https://pikhurko.github.io/E/PikhurkoThomason02dm.pdf.
4. Oleg Pikhurko, "Size Ramsey numbers of stars versus 4-chromatic graphs", Journal of Graph Theory 42(3) (2003) 220–233. DOI: 10.1002/jgt.10086, https://doi.org/10.1002/jgt.10086.
5. Mathew Cropper, András Gyárfás, Jenő Lehel, "Edge list multicoloring trees: An extension of Hall's theorem", Journal of Graph Theory 42(3) (2003). DOI: 10.1002/jgt.10093, https://doi.org/10.1002/jgt.10093.
6. Shih-Yan Chen, Shin-Shin Kao, Hsun Su, "On degree-sequence characterization and the extremal number of edges for various Hamiltonian properties under fault tolerance", Discrete Mathematics & Theoretical Computer Science 17(3) (2016). DOI: 10.46298/dmtcs.2149, https://doi.org/10.46298/dmtcs.2149.