Effective resistance in planar graphs and continued fractions

Alex Kontorovich; Igor Pak; Swee Hong Chan

REVIEW 1 major objections 4 minor 1 cited by

Effective resistance in planar graphs and continued fractions

T0 review · 1 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper resolves the inverse problem for effective resistance in planar graphs: for every reduced fraction $c/t$ it constructs a simple planar graph with an edge of resistance $c/t$ using $O(\max(t/c,\, t/(t-c),\, \log t))$ vertices…

desk verdict Strong upper-bound construction, but the lower-bound proof in Proposition 1.2 has a real gap, so the 'up to constant' optimality claim is currently unproved. read the letter →

arxiv 2505.19168 v1 pith:RROFD57K submitted 2025-05-25 math.CO math.NT

Swee Hong Chan , Alex Kontorovich , Igor Pak This is my paper · ORCID

classification math.COmath.NT MSC 05C1011A5505C30

keywords effectiveresistanceplanargraphsspanningtreesinverseproblemcontinuedfractionsmarkedplanedualitySedláček

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper resolves the inverse problem for effective resistance in planar graphs: given any reduced fraction $c/t$, it determines, up to a universal constant, the smallest number of vertices of a simple planar graph with an edge of effective resistance $c/t$. The extremal size is $\max(t/c,\, t/(t-c),\, \log t)$ up to constant factors, with a matching construction and lower bound. The result matters because effective resistance is a central graph invariant with electrical-network and random-walk interpretations, and knowing the exact growth of the minimal example makes the achievable values of the invariant concrete. The proof links the graph invariant to continued fractions, showing that rational resistances are realized by assembling small marked graph pieces whose spanning-tree ratios add.

What carries the argument

The load-bearing object is the marked graph $(G,e)$ together with the spanning-tree ratio $\zeta(G,e) = \tau(G-e)/\tau(G/e)$, since deletion–contraction gives $\rho(G,e)=1/(1+\zeta(G,e))$. Three operations on marked graphs carry the argument: the marked sum $\oplus$, under which $\zeta$ values add; the plane dual, which inverts $\zeta$ (so $\rho$ maps to $1-\rho$); and the simplification operation (doubling every other edge, then subdividing every other edge), which makes a graph simple while preserving $\zeta$ at the cost of a factor of $4$ in edges. A continued-fraction construction provides, for any rational $q$, a planar marked graph with $\zeta(G,e)=q$ and edge count $S(q)+1$, where $S$ is the sum of the partial quotients. Bourgain's theorem supplies the arithmetic input: every rational in $[0,1)$ is a sum of rationals of small $S$-height, with total height $O(\log)$ of the denominator.

What would settle it

Compute, for unit fractions $1/t$ with large $t$, the minimum total $S$-height of an expression $1/t = q_1+\cdots+q_k$ with each $q_i \in \mathbb{Q}\cap(-1,1)$; if this minimum grows faster than $C\log t$, then the construction of Theorem 1.1 collapses because the $\log t$ term in (1.3) would be too small. Graph-theoretically, enumerate simple planar graphs up to $n$ vertices, compute all achievable edge resistances, and check whether a planar graph with resistance $1/t$ appears for $n = o(t)$; Proposition 1.2 forbids $n \le C' t$, so any such graph would falsify the lower bound.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.1: for every coprime pair $t > c \ge 1$ there exists a simple planar graph $G=(V,E)$ and an edge $e$ with $\rho(G,e) = \tau(G/e)/\tau(G) = c/t$ and $|V| \le C\max(t/c,\, t/(t-c),\, \log t)$ for a universal constant $C$. Proposition 1.2 gives the matching lower bound $|V| \ge C'\max(t/c,\, t/(t-c),\, \log t)$ for any simple planar graph realizing a reduced resistance $c/t$ on a non-bridge edge. Together these resolve the inverse problem for planar effective resistance up to a universal constant. The paper also notes the corollary that for every integer $t\ge 2$ there is a simple connected planar graph with $\tau(G)\equiv 0 \pmod t$ and $O(\log t)$ vertices.

Load-bearing premise

The upper bound relies on Bourgain's theorem that every rational $d/c$ in $[0,1)$ can be written as a sum of rationals each of small continued-fraction height, with the total height growing only logarithmically in $c+d$.

Editorial extensions

If this is right

For every reduced resistance $c/t$ there is a simple planar graph with that resistance on $O(\max(t/c,\, t/(t-c),\, \log t))$ vertices, and no such graph can be substantially smaller.
The extremal size is governed by the reciprocal of the resistance, the reciprocal of its complement, and the logarithm of the denominator, with the planar-dual symmetry $\rho \leftrightarrow 1-\rho$ reflected in the symmetric term $t/(t-c)$.
For every integer $t\ge 2$ there exists a simple connected planar graph with $\tau(G)\equiv 0 \pmod t$ and only $O(\log t)$ vertices.
The result extends earlier bounds that required the resistance to lie in $[1/3,2/3]$ and allowed multiple edges, to all rational resistances with simple graphs.
The construction is effective in principle: given $c/t$, one can assemble the graph from continued-fraction data once Bourgain's decomposition is supplied.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same marked-sum and simplification machinery should transfer to other invariants expressible as ratios of spanning-tree counts under deletion and contraction, such as other Tutte-polynomial evaluations.
The result suggests a concrete algorithmic challenge: make Bourgain's decomposition constructive, turning the existence proof into a polynomial-time procedure that outputs the $O(\log t)$-vertex planar graph realizing a given rational resistance.
The exact form of the extremal bound invites a sharper conjecture: that the true minimal vertex count, before universal constants, is governed by the continued-fraction expansion of $c/t$ itself, not merely by the three-way maximum.
A direct comparison with the poset analogue from the authors' related work suggests that the logarithmic term may be removable in that setting too, since the obstruction there is a technical limitation of the flip-flop construction rather than the arithmetic growth.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Main take: the upper-bound construction is the real contribution here, and it looks correct. The new simplification operation (doubling then halving all edges except the marked one) is a genuinely useful trick, and the reduction to Bourgain's continued-fraction decomposition is clean. If that were all, I'd be happy. But the matching lower bound in Proposition 1.2 has a genuine gap, and as written the paper does not resolve the inverse problem up to a constant.

The upper half: Theorem 1.5 builds a simple planar graph realizing any target sum of continued-fraction values, and Lemmas 3.1–3.3 chain it to Bourgain's theorem to cover all ratios. I checked the algebra in the lemmas; the bookkeeping is fine. The construction is explicit and, modulo the unspecified constant in [Bou12], gives |V| = O(max(t/c, t/(t-c), log t)). That's a clean improvement over the earlier O(log t (log log t)^2) for a restricted range, and the step from multigraphs to simple graphs is nontrivial.

The soft spot: Proposition 1.2. The proof of the second inequality applies Lemma 3.4 to the dual G*. But G* need not be simple—in an n-cycle the dual is two vertices with n parallel edges. The line |F|/2 > 1/(2ρ(G*,e)) requires |F| > 1/ρ(G*,e), which is the first inequality applied to the dual, and that only holds when the dual is simple. The displayed chain fails; for C_n, (3.7) reads 1 > n/2. So the lower bound |V| ≥ C' t/(t−c) is not proved. This is not a cosmetic issue: without it, the paper only proves an upper bound, and the optimality claim rests on an unproved statement. The authors do mention in §4.3 that the constant 1/2 can be removed, but that's not the problem; the problem is the validity of the inequality itself.

Everything else is honest: the use of Bourgain's theorem is flagged as external with unspecified constant, the small cases are absorbed, and the citation pattern looks appropriate. The upper bound alone is worth publishing, but the current text overstates the result. I'd send it to a referee who can assess whether the lower bound can be fixed; if it can't, the abstract and introduction need a major revision.

Referee Report

1 major / 4 minor

Summary. The paper studies the inverse problem for effective resistance in planar graphs. For a reduced fraction c/t, Theorem 1.1 constructs a simple planar graph G with an edge e such that ρ(G,e)=c/t and |V| ≤ C max(t/c, t/(t−c), log t), and Proposition 1.2 claims a matching lower bound |V| ≥ C′ max(t/c, t/(t−c), log t). The upper-bound construction (Theorem 1.5) represents the target ratio as a sum of rationals via Bourgain's continued-fraction theorem, builds marked graphs for each summand, and combines them by a marked-sum operation followed by a new simplification operation that preserves the spanning-tree ratio. The lower bound uses commute-time inequalities, planar duality, and Euler's formula.

Significance. If correct, the paper resolves the planar inverse effective-resistance problem up to universal constants, identifying the extremal size as max(1/ρ, 1/(1−ρ), log t). The construction is explicit and parameter-free, and the simplification operation (Lemma 2.4) is a clean technical contribution. The upper-bound proof is modular and easy to verify. However, the proof of the matching lower bound contains a genuine gap, so the optimality claim is not currently established.

major comments (1)

[§3.3, Eq. (3.7)] The proof of the second inequality in Proposition 1.2 applies Lemma 3.4 and then the first inequality (3.6) to the plane dual G*. Inequality (3.6) relies on the graph being simple, since it uses deg(x), deg(y) < |V|. The dual of a simple planar graph need not be simple; for example, for G = C_n, G* has two vertices and n parallel edges, so deg(f) = n = |F|, and the analogue of (3.6) for G* would assert 2 > n, which is false. Indeed the displayed chain |V| > |F|/2 > 1/(2ρ(G*,e)) fails for n > 2 because 1 < n/2. Thus the lower bound |V| ≥ C′ t/(t−c) is not established as written. Since Proposition 1.2 is the matching lower bound that shows the upper bound is optimal up to a constant, this is a load-bearing gap. The proof must either give a direct argument for the second bound that does not require G* to be simple, or demonstrate that the failure of simplicity (multiple edges and loops) does not invalidate the estimate.

minor comments (4)

[§3.3 (Lemma 3.3)] There is a typographical error in Lemma 3.3: 'simple planar marked graph (G, E)' should be '(G, e)', and the formula for |E∘| is printed as '4(|E|−1)+1' but appears as '4|E|−1)+1' in the text.
[§3.2 (Lemma 3.2)] The phrase 'Theorem 1.5 applied to q1 ← (d/c−d′/c′) and k=1' is informal; the substitution should be written explicitly for clarity.
[§3.3 (Proposition 1.2)] The third inequality uses t ≤ τ(G); this follows from the reduced form of c/t and the integrality of τ(G/e), but the justification is omitted and should be stated.
[§4.3] The remark that the constant 1/2 in (3.7) can be removed should be revisited after the simplicity issue with the dual is resolved; as written, the main obstacle is not the constant but the validity of the inequality.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the main construction and lower bounds use external theorems and prior results that do not assume the target ratio.

full rationale

The paper's derivation is not circular. Theorem 1.1 is obtained by combining Bourgain's external Theorem 1.4 with Theorem 1.5, whose proof uses Proposition 2.1 and Lemma 2.2 cited from the authors' prior papers. These cited lemmas are constructive statements about continued fractions and marked graph sums; they do not assume Theorem 1.1 or the specific target resistance c/t. The simplification operation in Section 2.5 is proved in this paper via explicit spanning-tree counting and plane duality (Lemma 2.4), so the simplicity of the final graph is not imported by assumption. The lower bound Proposition 1.2 uses standard random-walk/commute-time inequalities and Euler's formula, not fitted parameters, and the target fraction c/t enters only as the input to the estimates. No fitted quantity is later renamed as a prediction, and no uniqueness theorem or ansatz is imported from the authors' own work to force the construction. The possible gap in applying Lemma 3.4 to the possibly non-simple dual graph in inequality (3.7) is a correctness concern, not a circularity concern.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central construction has no fitted numerical parameters. It relies on external and prior-work results: Bourgain's decomposition theorem, the continued fraction gadget from [CP24c], the marked sum lemma, and standard random walk/planarity bounds. The graph operations (subdivision, duplication, marked sum, simplification) are definitions, not invented entities.

assumptions (5)

domain assumption Bourgain's decomposition theorem [Bou12, Prop. 1]: every rational d/c in [0,1) equals q_1+...+q_k with q_i in Q∩(-1,1) and Σ S(|q_i|) ≤ C log(c+d).
Used as Theorem 1.4 in Lemmas 3.1 and 3.2; the logarithmic bound on continued fraction height is what forces the O(log t) term in the vertex bound. Not proved in this paper and its constant C is unspecified.
domain assumption Proposition 2.1 from [CP24c, Thm 5.1]: for any rational d/c with continued fraction [a0; a1,...,aℓ], there exists a planar marked graph G with τ(G-e)=d, τ(G/e)=c and |E|=a0+...+aℓ+1.
Invoked in Theorem 1.5 to convert each rational q_i into a marked graph gadget. The construction is from the authors' prior work and is not rederived here.
domain assumption Lemma 2.2 (marked sum additivity): for proper marked graphs, ζ(G⊕G',e) = ζ(G,e) + ζ(G',e).
Cited from [CP24c, Lem. 5.4]; used in Theorem 1.5 and Lemma 3.2 to add spanning tree ratios. The proof is a short deletion-contraction argument but is not given in this paper.
domain assumption Lemma 3.4 (commute time bound): ρ(G,e) ≥ 1/2(1/deg(x)+1/deg(y)), derived from κ(G,e)=2|E|ρ ≥ |E|(1/deg(x)+1/deg(y)).
Used in Proposition 1.2 for the t/c and t/(t-c) lower bounds; cited from [C+96] and [Lov96].
standard math Euler's formula for simple planar graphs (|E| ≤ 3|V|-6, |F| ≤ 2|V|-4) and the exponential bound τ(G) < 2^{|E|} for the number of spanning trees.
Used in Proposition 1.2 to obtain the log t lower bound and to relate |F| to |V|.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Effective resistance in planar graphs and continued fractions." pith.science (2026). https://pith.science/paper/RROFD57K

@misc{pith2026250519168,
  author       = {Pith},
  title        = {Pith review of: Effective resistance in planar graphs and continued fractions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RROFD57K}},
  note         = {Machine review of arXiv:2505.19168}
}

abstract

For a simple graph $G=(V,E)$ and edge $e\in E$, the effective resistance is defined as a ratio $\frac{\tau(G/e)}{\tau(G)}$, where $\tau(G)$ denotes the number of spanning trees in $G$. We resolve the inverse problem for the effective resistance for planar graphs. Namely, we determine (up to a constant) the smallest size of a simple planar graph with a given effective resistance. The results are motivated and closely related to our previous work arXiv:2411.18782 on Sedl\'a\v{c}ek's inverse problem for the number of spanning trees.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

On some results of Korobov and Larcher and Zaremba's conjecture
math.NT 2026-03 accept novelty 7.0 of 10

Zaremba's conjecture holds for all large primes: an absolute M exists so every large prime p admits a coprime a whose continued-fraction partial quotients are all ≤ M, with quantitative lower bounds on the number of such a.

Reference graph

Works this paper leans on

23 extracted references · 20 canonical work pages · cited by 1 Pith paper

[1]

Noga Alon, Matija Buci\'c and Lior Gishboliner, The spanning tree spectrum: improved bounds and simple proofs, preprint (2025), 8 pp.; arXiv:2503.23648

arXiv 2025
[2]

Jernej Azarija and Riste S krekovski, Minimal graphs with a prescribed number of spanning trees, in Open problem garden, 2012; available online at tinyurl.com/2tc6v469 http://garden.irmacs.sfu.ca/op/minimal_graphs_with_a_prescribed_number_of_spanning_trees

work page 2012
[3]

Jean Bourgain, Partial quotients and representation of rational numbers, C. R. Math. 350 (2012), 727--730

work page 2012
[4]

180 (2014), 137--196

Jean Bourgain and Alex Kontorovich, On Zaremba's conjecture, Annals of Math. 180 (2014), 137--196

work page 2014
[5]

Kevin Buchin and Andr\'e Schulz, On the number of spanning trees a planar graph can have, in Proc.\ 18th ESA, Springer, Berlin, 2010, 110--121

work page 2010
[6]

Swee Hong Chan, Alex Kontorovich and Igor Pak, Spanning trees and continued fractions, preprint (2024), 20 pp.; arXiv:2411.18782

arXiv 2024
[7]

1015 (2024), Paper No

Swee Hong Chan and Igor Pak, Computational complexity of counting coincidences, Theor.\ Comp.\ Sci. 1015 (2024), Paper No. 114776, 19 pp

work page 2024
[8]

122 (2024), 104018, 14 pp

Swee Hong Chan and Igor Pak, Linear extensions and continued fractions, European J.\ Combin. 122 (2024), 104018, 14 pp

work page 2024

Show all 23 references

[9]

Swee Hong Chan and Igor Pak, Equality cases of the Stanley–Yan log-concave matroid inequality, preprint (2024), 35 pp.; arXiv:2407.19608

2024 arXiv
[10]

Chandra, Prabhakar Raghavan, Walter L

Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky and Prasoon Tiwari, The electrical resistance of a graph captures its commute and cover times, Comput.\ Complexity 6 (1996), 312--340

1996
[11]

48 (1947), 966--993

Marshall Hall, On the sum and product of continued fractions, Annals of Math. 48 (1947), 966--993

1947
[12]

Doyle and Laurie J

Peter G. Doyle and Laurie J. Snell, Random walks and electric networks, MAA, Washington, DC, 1984, 159 pp

1984
[13]

62 (2023), 69--110

Jaroslav Han c l and Ond r ej Turek, Continued fractions with bounded even-order partial quotients, Ramanujan J. 62 (2023), 69--110

2023
[14]

Hardy and Edward M

Godfrey H. Hardy and Edward M. Wright, An introduction to the theory of numbers (sixth ed., revised), Oxford Univ.\ Press, Oxford, UK, 2008, 621 pp

2008
[15]

AMS 30 (2017), 1023--1046

Alex Kontorovich, Peter McNamara and Geordie Williamson, Appendix to: S chubert calculus and torsion explosion (by G eordie W illiamson), Jour. AMS 30 (2017), 1023--1046

2017
[16]

2, Bolyai Math.\ Soc., Budapest, 1996, 353--397

L\'aszl\'o Lov\'asz, Random walks on graphs: a survey, in Combinatorics, Paul Erd o s is eighty , Vol. 2, Bolyai Math.\ Soc., Budapest, 1996, 353--397

1996
[17]

Russell Lyons and Yuval Peres, Probability on trees and networks, Cambridge Univ.\ Press, New York, 2016, 699 pp

2016
[18]

Crispin St J. A. Nash-Williams, Random walk and electric currents in networks, Proc.\ Cambridge Philos. Soc. 55 (1959), 181--194

1959
[19]

Ji r \'i Sedl\'a c ek, On the spanning trees of finite graphs (in Czech), C asopis P e st. Mat. 91 (1966), 221--227

1966
[20]

Ji r \'i Sedl\'a c ek, On the number of spanning trees of finite graphs, C asopis P e st. Mat. 94 (1969), 217--222

1969
[21]

13 (1970), 515--517

Ji r \'i Sedl\'a c ek, On the minimal graph with a given number of spanning trees, Canad.\ Math.\ Bull. 13 (1970), 515--517

1970
[22]

VIII, AMS, Providence, RI, 1965, 1--15

Atle Selberg, On the estimation of Fourier coefficients of modular forms, in Proc.\ Sympos.\ Pure Math., Vol. VIII, AMS, Providence, RI, 1965, 1--15

1965
[23]

82 (2022), 182--196

Richard Stong, Minimal graphs with a prescribed number of spanning trees, Australas.\ J.\ Combin. 82 (2022), 182--196

2022

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Noga Alon, Matija Buci\'c and Lior Gishboliner, The spanning tree spectrum: improved bounds and simple proofs, preprint (2025), 8 pp.; arXiv:2503.23648

arXiv 2025

[2] [2]

Jernej Azarija and Riste S krekovski, Minimal graphs with a prescribed number of spanning trees, in Open problem garden, 2012; available online at tinyurl.com/2tc6v469 http://garden.irmacs.sfu.ca/op/minimal_graphs_with_a_prescribed_number_of_spanning_trees

work page 2012

[3] [3]

Jean Bourgain, Partial quotients and representation of rational numbers, C. R. Math. 350 (2012), 727--730

work page 2012

[4] [4]

180 (2014), 137--196

Jean Bourgain and Alex Kontorovich, On Zaremba's conjecture, Annals of Math. 180 (2014), 137--196

work page 2014

[5] [5]

Kevin Buchin and Andr\'e Schulz, On the number of spanning trees a planar graph can have, in Proc.\ 18th ESA, Springer, Berlin, 2010, 110--121

work page 2010

[6] [6]

Swee Hong Chan, Alex Kontorovich and Igor Pak, Spanning trees and continued fractions, preprint (2024), 20 pp.; arXiv:2411.18782

arXiv 2024

[7] [7]

1015 (2024), Paper No

Swee Hong Chan and Igor Pak, Computational complexity of counting coincidences, Theor.\ Comp.\ Sci. 1015 (2024), Paper No. 114776, 19 pp

work page 2024

[8] [8]

122 (2024), 104018, 14 pp

Swee Hong Chan and Igor Pak, Linear extensions and continued fractions, European J.\ Combin. 122 (2024), 104018, 14 pp

work page 2024