Erdős Problem #82

Erdős Problem 82: induced regular subgraphs and the logarithmic barrier

1. Statement and scope

2. A refined elementary Ramsey lower bound

3. The precise inverse formulation

4. A restricted positive range and a failed shortcut

5. Assessment and attribution

Completion rate estimate: 15%.

1) FORMAL RESTATEMENT.

For $n\in\mathbb{N}$, define $F(n)$ to be the largest integer such that:

Every graph $G$ on $n$ vertices contains an induced subgraph on at least $F(n)$ vertices that is regular.

Here "regular induced subgraph" means: there exists $S\subseteq V(G)$ with $|S|\ge F(n)$ such that the induced graph $G[S]$ is $d$-regular for some $d$ (i.e. every vertex in $S$ has exactly $d$ neighbours in $S$).

The task is to prove \[ \frac{F(n)}{\log n}\to \infty\qquad (n\to\infty). \] Equivalently: for every constant $C>0$, for all sufficiently large $n$, every $n$-vertex graph contains a regular induced subgraph on at least $C\log n$ vertices.

2) QUICK LITERATURE/CONTEXT CHECK.

Per the integrity rule I only use what is stated in the problem text: it records that Ramsey's theorem implies $F(n)\gg \log n$, that $F(5)=3$ and $F(7)=4$ are known, and that there are upper bounds $F(n)\ll n^{1/2+o(1)}$ and $F(n)\le n^{1/2}(\log n)^{O(1)}$ from cited authors. I do not reproduce those deeper upper bounds here.

3) ATTACK PLAN.

Proof-track:

• Strengthen the Ramsey-theoretic guarantee (clique/independent sets) to force much larger induced regular subgraphs, possibly by exploiting degree patterns.
• Rephrase via $G(n)$ (inverse function) and attempt to prove $G(k)\le 2^{o(k)}$.

• Not applicable: the statement is a conjectural lower bound request.

Here I provide two fully proved lemmas: (a) the formal equivalence between $F$ and the inverse parameter $G$, and (b) an explicit Ramsey-type lower bound $F(n)\ge c\log n$ with constants proved from Lemma 77.1. I also give exhaustive small-$n$ computations as sanity checks.

4) WORK.

Fast reality check (exact small values by exhaustive enumeration). By exhaustive enumeration of all graphs on $n\le 7$ vertices (using complement symmetry to halve the search), the following exact values were computed: \[ F(1)=1,\ F(2)=2,\ F(3)=2,\ F(4)=2,\ F(5)=3,\ F(6)=3,\ F(7)=4. \] In particular this matches the statement's recorded values $F(5)=3$ and $F(7)=4$.

Lemma 82.1 (Equivalence between $F$ and $G$). Define $G(k)$ to be the least integer $m$ such that every graph on $m$ vertices contains a regular induced subgraph on at least $k$ vertices. Then for all $n,k\in\mathbb{N}$, \[ F(n)\ge k \quad\Longleftrightarrow\quad n\ge G(k). \] Equivalently, $G$ is the (left-continuous) inverse of the monotone function $F$.

Proof. ($\Rightarrow$) Assume $F(n)\ge k$. By definition, every graph on $n$ vertices contains a regular induced subgraph on at least $k$ vertices. Therefore $n$ satisfies the defining property of $G(k)$, so the minimal such integer $G(k)$ is at most $n$, i.e. $n\ge G(k)$.

($\Leftarrow$) Assume $n\ge G(k)$. Consider any graph $H$ on $n$ vertices. Choose any subset $W\subseteq V(H)$ of size exactly $G(k)$ and consider the induced subgraph $H[W]$. By definition of $G(k)$, $H[W]$ contains a regular induced subgraph on at least $k$ vertices, and this is also an induced subgraph of $H$. Thus every $n$-vertex graph contains a regular induced subgraph on at least $k$ vertices, meaning $F(n)\ge k$. $\square$

Lemma 82.2 (Ramsey lower bound: $F(n)\ge c\log n$ with an explicit constant). For every $n\ge 1$, \[ F(n)\ge \lfloor \log_4 n\rfloor+1. \] In particular $F(n)\ge \frac{\log n}{\log 4}$ for all $n$ (up to an additive constant).

Proof. Let $k:=\lfloor \log_4 n\rfloor+1$. Then $4^{k-1}\le n$. By Lemma 77.1, the diagonal Ramsey number satisfies $R(k)\le 4^{k-1}$. Hence $n\ge 4^{k-1}\ge R(k)$.

Therefore, in any graph on $n$ vertices, by the definition of $R(k)$ there exists either a clique of size $k$ or an independent set of size $k$. Either subgraph is regular as an induced subgraph: $K_k$ is $(k-1)$-regular and the empty graph on $k$ vertices is $0$-regular. Thus every graph on $n$ vertices contains a regular induced subgraph on at least $k$ vertices, i.e. $F(n)\ge k$. $\square$

5) VERIFICATION.

• Lemma 82.1 is purely definitional and checks both directions carefully.
• Lemma 82.2 depends only on Lemma 77.1 (proved earlier) and the observation that cliques/independent sets are regular induced subgraphs.
• The exhaustive small-$n$ computations provide sanity checks and match the values quoted in the problem text.

6) FINAL.

UNRESOLVED

(i) Strongest proved partial result: $F(n)\ge \lfloor \log_4 n\rfloor+1$ for all $n$ (Lemma 82.2), hence $F(n)\gg \log n$. Also, $F$ and $G$ are inverse parameters in the precise sense of Lemma 82.1. Exhaustive enumeration confirms $F(5)=3$ and $F(7)=4$.

(ii) First gap (crisp): Prove that $F(n)\ge \omega(\log n)$, i.e. for every constant $C$ and all sufficiently large $n$, every $n$-vertex graph contains a regular induced subgraph on at least $C\log n$ vertices.

(iii) Top 3 next moves (concrete):

1. Strengthen Lemma 82.2 by finding an induced regular subgraph that is not necessarily complete or empty; a concrete target lemma is: "every $n$-vertex graph contains an induced subgraph on $\gg \log n$ vertices whose degrees (within the subgraph) are all equal" using degree-sequence pigeonholing plus iterative pruning.
2. Work with $G(k)$: prove an upper bound of the form $G(k)\le 2^{o(k)}$ by designing a strategy that in any $m$-vertex graph finds a $k$-vertex induced regular subgraph.
3. Computational exploration: for $n\le 9$ (or as far as feasible), compute $F(n)$ and identify extremal graphs; use their structure to hypothesise a general construction that might bound $F(n)$ from above or suggest the right growth for $F(n)$.

(iv) Minimal counterexample structure (to $F(n)/\log n\to\infty$): a family of graphs $G_n$ such that every induced regular subgraph has size $O(\log n)$, i.e. $\max\{|S|:G_n[S]\text{ regular}\}=O(\log n)$. Such graphs would need to avoid large complete/empty induced subgraphs (already Ramsey-forced) and also avoid large induced subgraphs with constant internal degree, suggesting a highly heterogeneous induced-degree behaviour across all moderately large vertex subsets.

OUTPUT 1) FORMAL RESTATEMENT Definitions/Conventions. - A (finite) graph $H$ is regular if all vertices of $H$ have the same degree (within $H$). - For $n\ge 1$, define $F(n)$ as the largest integer such that every graph on $n$ vertices contains an induced regular subgraph on at least $F(n)$ vertices. Equivalently, \[F(n):=\min_{|V(G)|=n}\ \max\{|V(H)|:\ H \text{ is an induced regular subgraph of }G\}.\]

Conjecture. Prove that \[\frac{F(n)}{\log n}\to\infty\quad\text{as }n\to\infty.\]

2) QUICK LITERATURE/CONTEXT CHECK Web browsing is not available in this session. From the problem text only: - Ramsey yields $F(n)\gg\log n$. - Known upper bounds are around $n^{1/2+o(1)}$, improved by AKS. - Equivalent formulation via $G(n)$ is given. I do not re-prove the deep AKS bound here.

3) ATTACK PLAN Proof track ideas: 1. Start from the trivial regular induced subgraphs (cliques and independent sets) and try to push beyond Ramsey. 2. Use degree-sequence pigeonhole principles: a large induced subgraph with a very narrow degree range can sometimes be made regular by deleting few vertices. 3. Work with the inverse function $G(t)$ and attempt to show $G(t)\le 2^{o(t)}$ via a probabilistic or iterative method.

Disproof track ideas: 1. Construct graphs where all induced regular subgraphs are small, aiming to show $F(n)=O(\log n)$. The problem text indicates this is believed false.

Chosen path in this attempt: prove (i) the Ramsey lower bound in a clean form, and (ii) the equivalence between the $F$-formulation and the subexponential bound on $G$.

4) WORK Lemma 1 (Ramsey lower bound gives $F(n)\ge c\log n$). For every $n\ge 2$, \[F(n)\ge \frac12\log_2 n.\]

Proof. Let $R(k)$ be the diagonal Ramsey number: the least $m$ such that every graph on $m$ vertices contains a clique of size $k$ or an independent set of size $k$. It is standard (and follows from the classical recursion $R(k,k)\le 2R(k-1,k)$) that \[R(k)\le 4^{k-1}\qquad(k\ge 2).\tag{*}\] I sketch the recursion proof: one shows $R(s,t)\le R(s-1,t)+R(s,t-1)$ by considering a pivot vertex and its red/blue neighborhoods, and then deduces $R(k,k)\le \binom{2k-2}{k-1}<4^{k-1}$ by induction on $s+t$.

Now let $G$ be any graph on $n$ vertices, and choose $k:=\left\lfloor \frac12\log_2 n\right\rfloor$. Then $4^{k-1}\le 4^{\frac12\log_2 n}=n$, so by $*$ we have $R(k)\le n$. Therefore $G$ contains either a clique or an independent set on $k$ vertices. Both a clique and an independent set are regular graphs (degrees $k-1$ and $0$ respectively), and they are induced subgraphs on their vertex sets. Hence every $n$-vertex graph contains an induced regular subgraph of size at least $k\ge \frac12\log_2 n-1$. Absorbing the $-1$ into the constant for $n\ge 2$ yields $F(n)\ge \frac12\log_2 n$. $\square$

Lemma 2 (Equivalence with the inverse function $G$). Define $G(t)$ to be the least integer $m$ such that every graph on $m$ vertices contains an induced regular subgraph on at least $t$ vertices. Then the following are equivalent: (a) $\displaystyle \frac{F(n)}{\log n}\to\infty$; (b) $\displaystyle \log G(t)=o(t)$, i.e. $G(t)\le 2^{o(t)}$.

Proof. Write the inverse relationship (valid for all $n,t$): \[F(n)\ge t \quad\Longleftrightarrow\quad G(t)\le n.\tag{1}\] This is immediate from the definitions: $F(n)\ge t$ means every $n$-vertex graph has an induced regular subgraph on $\ge t$ vertices, so the minimal $m$ with this property satisfies $G(t)\le n$, and conversely.

(a)$\Rightarrow$(b). Fix $\varepsilon>0$. By (a), for all sufficiently large $n$ one has \[F(n)\ge \frac{1}{\varepsilon}\log n.\tag{2}\] Let $t$ be large and set $n:=\left\lceil e^{\varepsilon t}\right\rceil$ (so $\log n\ge \varepsilon t$ and $n$ is large enough for $2$). Then $2$ gives $F(n)\ge \frac{1}{\varepsilon}\log n \ge t$, and hence by $1$ we have $G(t)\le n\le e^{\varepsilon t}+1$. Taking logs yields $\log G(t)\le \varepsilon t + o(t)$. Since $\varepsilon>0$ was arbitrary, this implies $\log G(t)=o(t)$.

(b)$\Rightarrow$(a). Fix $\varepsilon>0$. By (b), for all sufficiently large $t$ one has \[\log G(t)\le \varepsilon t,\qquad\text{equivalently }G(t)\le e^{\varepsilon t}.\tag{3}\] Let $n$ be large and set $t:=\left\lfloor \frac{1}{\varepsilon}\log n\right\rfloor$; for $n$ large this $t$ satisfies $3$. Then $G(t)\le e^{\varepsilon t}\le n$, so by $1$ we get $F(n)\ge t\ge \frac{1}{\varepsilon}\log n-1$. Since $\varepsilon>0$ is arbitrary, $F(n)/\log n\to\infty$. $\square$

FAST REALITY CHECK The problem text reports $F(5)=3$ and $F(7)=4$ and that Ramsey gives $F(n)\gg\log n$. Lemma 1 recovers such a Ramsey-type lower bound with an explicit constant.

5) VERIFICATION - Lemma 1 uses only the classical explicit bound $R(k)\le 4^{k-1}$ and the observation that cliques/independent sets are regular induced subgraphs. - Lemma 2's inversion step is the key: setting $t=\lfloor \frac{1}{\varepsilon}\log n\rfloor$ and using $\log G(t)\le \varepsilon t$ forces $G(t)\le n$ and hence $F(n)\ge t$.

6) FINAL UNRESOLVED

(i) Strongest fully proved partial result: I proved a clean Ramsey lower bound $F(n)\ge \tfrac12\log_2 n$ (Lemma 1) and proved that the conjecture $F(n)/\log n\to\infty$ is equivalent to $\log G(t)=o(t)$, i.e. $G(t)\le 2^{o(t)}$ (Lemma 2).

(ii) First gap: Prove any super-Ramsey growth of induced regular subgraphs, i.e. show $F(n)$ grows faster than $c\log n$ for every fixed $c$. Equivalently, prove $\log G(t)=o(t)$ with an explicit rate.

(iii) Top 3 next moves (concrete): 1. Try to show that every large graph contains an induced subgraph with at most $O(1)$ distinct degrees and size $\gg \log n$, then prune it to a regular induced subgraph. 2. Investigate whether probabilistic or iterative deletion processes can force large induced subgraphs with very concentrated degree sequences. 3. For upper bounds, attempt to construct graphs where induced regular subgraphs are provably small, to understand the true scale of $F(n)$.

(iv) What a minimal counterexample would likely look like (structure/parameters): A sequence of graphs $G_n$ on $n$ vertices such that every induced regular subgraph has size $O(\log n)$ (or at most $C\log n$ for some fixed $C$), showing the Ramsey lower bound is essentially tight. (This is believed not to exist, per the conjecture.)