pith. sign in

arxiv: 2604.11525 · v1 · submitted 2026-04-13 · 🧮 math.CO

The number of induced paths in outerplanar graphs

Yichen Wang , Ervin Gy\H{o}ri , Casey Tompkins , Xiamiao Zhao This is my paper

Pith reviewed 2026-05-10 15:50 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C3505C1005C38
keywords outerplanar graphsinduced pathsextremal graph theoryFibonacci numbersgolden ratiopath countingplanar graphs
0
0 comments X

The pith

The maximum number of induced paths on k+1 vertices in an n-vertex outerplanar graph lies between two Fibonacci multiples of quadratic terms in n.

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

The paper determines the maximum number of induced copies of a path with k+1 vertices that can appear in any outerplanar graph on n vertices. For the cases k=2 and k=3 it supplies an exact formula and an asymptotic formula respectively, while for general k it establishes matching-order bounds in which the extremal count is at least the (k-1)th Fibonacci number times a squared linear term and at most the (k+1)th Fibonacci number times the number of vertex pairs. These bounds immediately imply that the k-th root of the extremal function tends to the golden ratio as k grows, a slower rate than the base-4 growth known for ordinary (non-induced) paths in the same graph class.

Core claim

We prove that fib(k-1) (n-2k+3)^2 /4 ≤ ex_OP(n, P_{k+1}^ind, ∅) ≤ fib(k+1) binom(n,2), where fib denotes the Fibonacci sequence. This yields the limit lim (ex_OP(n, P_{k+1}^ind, ∅))^{1/k} = (√5 +1)/2 as k tends to infinity.

What carries the argument

Fibonacci recurrence arising from the recursive decomposition of outerplanar graphs when counting induced paths.

If this is right

  • The exact value of the extremal function is known for induced copies of P_3 in outerplanar graphs of any order.
  • An asymptotic expression is known for the extremal function for induced copies of P_4.
  • For every fixed k the maximum number of induced P_{k+1} is Theta(phi^k n^2) where phi is the golden ratio.
  • The k-th root growth rate is the golden ratio rather than the constant 4 that governs the non-induced case.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same recursive counting technique may extend to other classes of bounded-treewidth graphs.
  • The lower-bound constructions are probably the triangulated outerplanar graphs, which maximize induced paths along their outer faces.
  • Analogous Fibonacci-type bounds could appear in induced-path extremal problems for any minor-closed family whose duals admit linear recurrences.

Load-bearing premise

The Fibonacci multipliers in the upper and lower bounds apply uniformly to every outerplanar graph without special cases or exceptions that would invalidate them for large k.

What would settle it

A single outerplanar graph on n=100 vertices containing strictly more than fib(k+1) binom(100,2) induced copies of P_{k+1} for k=10 would disprove the stated upper bound.

Figures

Figures reproduced from arXiv: 2604.11525 by Casey Tompkins, Ervin Gy\H{o}ri, Xiamiao Zhao, Yichen Wang.

Figure 1
Figure 1. Figure 1: An example for O, O′ and C(vi , vj ) [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Different types of induced P4 in ϕ(xy). are shown in [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The graph G′ t . The red edges are from the path Pt . where J = Cn1 log n1 + Cn2 log n2 − Cn log n + 3n + 4. Then, it is sufficient to prove J ≤ 0, which is equivalent to 3n + 4 ≤ Cn1 log(n/n1) + Cn2 log(n/n2) + 2C log n. Since n ≥ 400, n1 + n2 = n + 2, and ni ≥ n 200 , i = 1, 2, we have ni ≤ 99 100n, i = 1, 2. Then log(n/ni) ≥ log(100/99), and the right-hand side is at least log(100/99) · Cn. When N0 and … view at source ↗
Figure 4
Figure 4. Figure 4: An illustration in the proof of the upper bound of Theorem 1.3. containing G as a subgraph. Then G′ admits a planar drawing with an outer cycle C, and we draw the graph G in the same way as G′ by removing the edges not in G. Let g(k) be the maximum number of induced Pk+1’s connecting two fixed vertices as end vertices of G. Then clearly, we have that p ind k+1(G) ≤ g(k) [PITH_FULL_IMAGE:figures/full_fig_p… view at source ↗
read the original abstract

Let $P_k$ denote the path with $k$ vertices, and $\mathrm{ex}_{\mathcal{OP}}(n,H^{\mathrm{ind}},\emptyset)$ be the maximum number of induced copies of $H$ in an $n$-vertex outerplanar graph. In this paper, we determine the exact value of $\mathrm{ex}_{\mathcal{OP}}(n,P_3^{\mathrm{ind}},\emptyset)$ for all $n$, and give an asymptotic value of $\mathrm{ex}_{\mathcal{OP}}(n,P_4^{\mathrm{ind}},\emptyset)$. For general $k$, Matolcsi and Nagy proved that $\lim_{k\to \infty} {\left( \mathrm{ex}_{\mathcal{OP}}(n, P_{k+1},\emptyset)\right)^{1/k}} =4$. In the induced case, we prove that \[ fib(k-1)\frac{{(n-2k+3)}^2}{4} \le \mathrm{ex}_{\mathcal{OP}}(n, P_{k+1}^{\mathrm{ind}},\emptyset) \le fib(k+1) \binom{n}{2}, \] where $fib(k)$ is the Fibonacci number. This implies that $\lim_{k\to \infty} {\left( \mathrm{ex}_{\mathcal{OP}}(n, P_{k+1}^{\mathrm{ind}},\emptyset)\right)^{1/k}} = \frac{\sqrt{5}+1}{2}\approx 1.618$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper determines the exact value of the maximum number of induced P_3 copies in n-vertex outerplanar graphs, gives an asymptotic for induced P_4, and for general k establishes the bounds fib(k-1)(n-2k+3)^2/4 ≤ ex_OP(n, P_{k+1}^ind, ∅) ≤ fib(k+1) binom(n,2). It claims these imply that the k-th root of the extremal function tends to the golden ratio φ as k→∞.

Significance. If the stated bounds hold and the limit is correctly interpreted (as a double limit with n growing after k), the result would give the precise exponential growth rate in k for the maximum number of induced paths in outerplanar graphs, providing a clean contrast to the non-induced case (limit 4) and using only standard Fibonacci growth. The exact determination for small k and the parameter-free Fibonacci multipliers are strengths.

major comments (2)
  1. [Abstract] Abstract and the paragraph following the displayed inequality: the claimed implication lim_{k→∞} [ex_OP(n, P_{k+1}^ind, ∅)]^{1/k} = φ does not hold for any fixed n, since the lower bound is nonnegative only for n ≳ 2k and ex vanishes for k ≫ n, forcing the k-th root to 0. The bounds at best support limsup_{k→∞, n→∞, n≫k} ex^{1/k} ≤ φ (and ≥ φ from the lower bound), but the single-limit statement with n free is incorrect and load-bearing for the main asymptotic claim.
  2. [Proof of lower bound (assumed §3 or §4)] The upper-bound construction and the verification that the lower-bound graphs remain outerplanar for all k (presumably in the proof of the lower bound) must be checked for exceptions when k is linear in n; any special cases that invalidate the Fibonacci multiplier would undermine the general-k result.
minor comments (2)
  1. [Abstract] The notation ex_OP(n, H^ind, ∅) is introduced without an explicit sentence defining the empty set as the forbidden subgraph condition; a one-sentence clarification would help readers.
  2. [Abstract] In the displayed inequality, the lower-bound factor (n-2k+3)^2/4 should be accompanied by a brief remark on when it is positive, to avoid readers misapplying the bound for small n relative to k.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the insightful comments on the limit statement and the scope of the constructions. We address each major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract and the paragraph following the displayed inequality: the claimed implication lim_{k→∞} [ex_OP(n, P_{k+1}^ind, ∅)]^{1/k} = φ does not hold for any fixed n, since the lower bound is nonnegative only for n ≳ 2k and ex vanishes for k ≫ n, forcing the k-th root to 0. The bounds at best support limsup_{k→∞, n→∞, n≫k} ex^{1/k} ≤ φ (and ≥ φ from the lower bound), but the single-limit statement with n free is incorrect and load-bearing for the main asymptotic claim.

    Authors: We agree that the single-limit statement as written in the abstract and the subsequent paragraph is imprecise and does not hold for fixed n. The bounds are meant to capture the growth rate in k for n growing at least linearly with k. We will revise the abstract and the relevant paragraph to replace the claim with the corrected double-limit form: the bounds imply that limsup_{k→∞, n→∞ with n≥2k} [ex_OP(n, P_{k+1}^ind, ∅)]^{1/k} = φ (with the matching lower bound also tending to φ). This clarification does not change the validity of the stated inequalities. revision: yes

  2. Referee: [Proof of lower bound (assumed §3 or §4)] The upper-bound construction and the verification that the lower-bound graphs remain outerplanar for all k (presumably in the proof of the lower bound) must be checked for exceptions when k is linear in n; any special cases that invalidate the Fibonacci multiplier would undermine the general-k result.

    Authors: The lower-bound construction is a specific family of outerplanar graphs (a triangulated outerplanar graph with a linear number of attached paths chosen to maximize the number of induced P_{k+1}) whose outerplanarity follows from an explicit embedding that does not depend on the ratio k/n. The Fibonacci recurrence for the number of induced paths holds by the same local counting argument for all k and all n ≥ 2k−3. We have verified there are no exceptional cases when k is linear in n (the embedding remains crossing-free and the recurrence is unaffected). We will add a short clarifying sentence in the proof of the lower bound to explicitly note that the construction and multiplier apply throughout the stated range. revision: partial

Circularity Check

0 steps flagged

No circularity; bounds and limit follow from independent constructions and standard Fibonacci asymptotics.

full rationale

The paper proves explicit combinatorial bounds fib(k-1)(n-2k+3)^2/4 ≤ ex ≤ fib(k+1) binom(n,2) for the extremal function. These are derived from constructions for the lower bound and a counting argument for the upper bound, with no fitted parameters or data-dependent steps. The subsequent limit statement uses only the closed-form growth rate lim fib(k)^{1/k} = φ, which is a standard external fact independent of the paper. No self-definitional reductions, no fitted inputs renamed as predictions, and no load-bearing self-citations appear in the derivation chain. The notation of the limit (n free) may be imprecise without an explicit double-limit regime, but this is a presentational issue rather than circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on the standard definition of outerplanar graphs and the recurrence for Fibonacci numbers; no free parameters are fitted and no new entities are postulated.

axioms (2)
  • domain assumption Outerplanar graphs are planar graphs that admit an embedding with all vertices on the outer face.
    This restricts the host graphs for the extremal function ex_OP throughout the paper.
  • standard math The Fibonacci sequence satisfies F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) for n>2.
    Used to obtain the multiplicative factors in both the lower and upper bounds.

pith-pipeline@v0.9.0 · 5580 in / 1493 out tokens · 43142 ms · 2026-05-10T15:50:22.065957+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    Chartrand and F

    G. Chartrand and F. Harary. Planar permutation graphs. InAnnales de l’institut Henri Poincar´ e. Section B. Calcul des probabilit´ es et statistiques, volume 3, pages 433–438. 1967

    work page 1967

  2. [2]

    Eppstein

    D. Eppstein. Connectivity, graph minors, and subgraph multiplicity.Journal of Graph Theory, 17(3):409–416, 1993

    work page 1993

  3. [3]

    Ghosh, E

    D. Ghosh, E. Gy˝ ori, O. Janzer, A. Paulos, N. Salia, and O. Zamora. The maximum number of inducedC 5’s in a planar graph.Journal of Graph Theory, 99(3):378–398, 2022

    work page 2022

  4. [4]

    Ghosh, E

    D. Ghosh, E. Gy˝ ori, R. R. Martin, A. Paulos, N. Salia, C. Xiao, and O. Zamora. The maximum number of paths of length four in a planar graph.Discrete Mathematics, 344(5):112317, 2021

    work page 2021

  5. [5]

    Grzesik, E

    A. Grzesik, E. Gy˝ ori, A. Paulos, N. Salia, C. Tompkins, and O. Zamora. The maximum number of paths of length three in a planar graph.Journal of Graph Theory, 101(3):493– 510, 2022

    work page 2022

  6. [6]

    Gy˝ ori and H

    E. Gy˝ ori and H. Hama Karim. Generalized planar Tur´ an numbers related to short cycles. arXiv e-prints, arXiv:2405.08162, May 2024

    work page arXiv 2024

  7. [7]

    Gy˜ ori, N

    E. Gy˜ ori, N. Salia, A. Paulos, O. Zamora, et al. Generalized planar tur´ an numbers. Electronic Journal of Combinatorics, 28(4):1–15, 2021

    work page 2021

  8. [8]

    Gy˝ ori, A

    E. Gy˝ ori, A. Paulos, N. Salia, C. Tompkins, and O. Zamora. The maximum number of pentagons in a planar graph.Journal of Graph Theory, 108(2):229–256, 2025

    work page 2025

  9. [9]

    Gy˝ ori, A

    E. Gy˝ ori, A. Paulos, and C. Xiao. Generalized outerplanar Tur´ an number of short paths. Discrete Mathematics, 346(1):113205, 2023

    work page 2023

  10. [10]

    Huynh, G

    T. Huynh, G. Joret, and D. R. Wood. Subgraph densities in a surface.Combinatorics, Probability and Computing, 31(5):812–839, 2022

    work page 2022

  11. [11]

    Leydold and P

    J. Leydold and P. F. Stadler. Minimal cycle bases of outerplanar graphs.The electronic journal of combinatorics, pages R16–R16, 1998

    work page 1998

  12. [12]

    Z. Lv, E. Gy˝ ori, Z. He, N. Salia, C. Tompkins, and X. Zhu. The maximum number of copies of an even cycle in a planar graph.Journal of Combinatorial Theory, Series B, 167:15–22, 2024. 12

    work page 2024

  13. [13]

    Matolcsi and Z

    D. Matolcsi and Z. L. Nagy. Generalised outerplanar Tur´ an numbers and maximum number of k-vertex subtrees.Discrete Applied Mathematics, 307:115–124, 2022

    work page 2022

  14. [14]

    M. Savery. Planar Graphs with the Maximum Number of Induced 6-Cycles.The Electronic Journal of Combinatorics, pages P4–6, 2023

    work page 2023

  15. [15]

    M. Savery. Planar graphs with the maximum number of induced 4-cycles or 5-cycles. Graphs and Combinatorics, 40(3):46, 2024. 13

    work page 2024