Estimate h_t(d): fewest edges forcing two edges at distance ≥ t in a max-degree-d graph (Erdős #934)
Statement
For two edges $e,f$ of a graph $G$, let their distance be the length (number of edges) of a shortest path in $G$ from an endpoint of $e$ to an endpoint of $f$; edges that intersect or are adjacent are at distance $0$. Let $h_t(d)$ be the least number of edges such that every graph $G$ with $h_t(d)$ edges and maximum degree at most $d$ contains two edges whose distance is at least $t$. Estimate $h_t(d)$ as a function of $d$, for each fixed $t\geq 1$. (For $t=2$ this asks when a bounded-degree graph is forced to contain an induced matching of size $2$.)
Acceptance. FULLY RESOLVES: a determination of $h_t(d)$ — an exact formula, or asymptotics pinning the constant $c_t=\lim_{d\to\infty} h_t(d)/d^t$ for every $t$ (in particular settling whether $h_t(d)=(1+o(1))d^t$) — with a complete proof. ADVANCES, any of: (a) prove or verify the conjectured bound $h_3(d)\leq d^3-d^2+d+2$ (or its equality characterisation $d=p^k+1$) for new values of $d$, with the extremal graph plus an exhaustiveness certificate; (b) compute a new exact value $h_t(d)$ beyond the solved $h_2$ case and $h_3(3)=23$, via search plus a certificate; (c) improve any general bound stated in the background (e.g. beat $h_t(d)\leq \tfrac{3}{2}d^t+1$, or the $0.629^t$ lower constant) with proof, strictly better than the best bound stated above. Deliver the formula/proof, or the extremal graph + verification code + exhaustiveness certificate.
Background
A problem of Erdős and Nešetřil [Er88], who wrote that it 'seems to be interesting only if there is a nice expression for $h_t(d)$'. Trivially $h_t(d)\leq 2d^t$ for all $t$, and $h_1(d)=d+1$. For $t=2$ (the induced-matching / strong-edge-colouring regime) Erdős–Nešetřil and, independently, Bermond, Bond, Paoli and Peyrat [BBPP83] conjectured $h_2(d)\leq \tfrac{5}{4}d^2+1$ with equality for even $d$ (cf. erdosproblems.com/149); this was proved by Chung, Gyárfás, Tuza and Trotter [CGTT90]. Cambie, Cames van Batenburg, de Joannis de Verclos and Kang [CCJK22] conjectured $$h_3(d)\leq d^3-d^2+d+2,$$ with equality if and only if $d=p^k+1$ for a prime power $p^k$, and proved $h_3(3)=23$. They further conjectured that for every $t\geq 3$ one has $h_t(d)\geq (1-o(1))d^t$ for infinitely many $d$ and $h_t(d)\leq (1+o(1))d^t$ for all $d$, and they proved that for large $t$ there are infinitely many $d$ with $h_t(d)\geq 0.629^t d^t$, while $h_t(d)\leq \tfrac{3}{2}d^t+1$ holds for all $t\geq 1$. Listed as open on erdosproblems.com/934 (fetched 2026-07-13, status 'open', tagged 'graph theory'). Attacker's tool: exhaustive/SAT search over bounded-degree graphs to compute exact small values ($h_3(d)$ for small $d$, testing the prime-power equality conjecture) and to certify extremal constructions.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #934 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.