On the (leq p)-inversion diameter of oriented graphs
Pith reviewed 2026-05-10 19:48 UTC · model grok-4.3
The pith
The (≤p)-inversion diameter of any graph G is at most ceil(|E(G)| / floor(p/2)) plus a constant Ψ_p depending only on p.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The paper shows that there exists a smallest number Ψ_p with one-fourth p minus three-halves less than or equal to Ψ_p less than or equal to one-half p squared such that the (≤p)-inversion diameter id^{≤p}(G) is at most the ceiling of |E(G)| over floor(p/2) plus Ψ_p for every graph G. It then gives improved upper bounds for trees and planar graphs, including exact or asymptotic expressions for small p on trees and explicit linear expressions in n for planar graphs.
What carries the argument
The (≤p)-inversion graph whose vertices are all orientations of the edges of G and whose edges connect two orientations when one is obtained from the other by inverting arcs inside some vertex set of size at most p; its diameter is the (≤p)-inversion diameter.
Load-bearing premise
There exists a finite constant Ψ_p depending only on p that uniformly bounds how much the diameter can exceed the main edge-count term for every graph.
What would settle it
A graph G where id^{≤p}(G) exceeds ceil(|E(G)| / floor(p/2)) plus one-half p squared.
Figures
read the original abstract
In an oriented graph $\vec{G}$, the {\it inversion} of a subset $X$ of vertices consists in reversing the orientation of all arcs with both endvertices in $X$. The {\it $(\leq p)$-inversion graph} of a labelled graph $G$, denoted by ${\mathcal{I}}^{\leq p}(G)$, is the graph whose vertices are the labelled orientations of $G$ in which two labelled orientations $\vec{G}_1$ and $\vec{G}_2$ of $G$ are adjacent if and only if there is a set $X$ with $|X|\leq p$ whose inversion transforms $\vec{G}_1$ into $\vec{G}_2$. In this paper, we study the {\it $(\leq p)$-inversion diameter} of a graph, denoted by $\mathrm{id}^{\leq p}(G)$, which is the diameter of its $(\leq p)$-inversion graph. We show that there exists a smallest number $\Psi_p$ with $\frac{1}{4}p - \frac{3}{2} \leq \Psi_p \leq \frac{1}{2}p^2$ such that $\mathrm{id}^{\leq p}(G) \leq \left\lceil\frac{|E(G)|}{\lfloor p/2\rfloor}\right \rceil + \Psi_p$ for all graph $G$. We then establish better upper bounds for several families of graphs and in particular trees and planar graphs. Let us denote by $\mathrm{id}^{\leq p}_{\cal F}(n)$ (resp. $\mathrm{id}^{\leq p}_{\cal P}(n)$) the maximum $(\leq p)$-inversion diameter of a tree (resp. planar graph) of order $n$. For trees, we show $\mathrm{id}^{\leq 3}_{\cal F}(n) = \left\lceil \frac{n-1}{2}\right\rceil$, $\mathrm{id}^{\leq 4}_{\cal F}(n)=\frac{3}{8}n + \Theta(1)$, $\mathrm{id}^{\leq 5}_{\cal F}(n)= \frac{2}{7}n + \Theta(1)$, and $\mathrm{id}^{\leq p}_{\cal F}(n) \leq \frac{n-1}{p- c\sqrt{p}} + 2$ with $c = \sqrt{2 + \sqrt{2}}$ for all $p\geq 6$. For planar graphs, we prove $\mathrm{id}^{\leq 3}_{\cal P}(n) \leq \frac{11n}{6} - \frac{8}{3}$, $\mathrm{id}^{\leq 4}_{\cal P}(n) \leq \frac{4n}{3} + \frac{10}{3}$, and $\mathrm{id}^{\leq p}_{\cal P}(n) \leq \left\lceil\frac{3n-6}{\lfloor p/2\rfloor}\right \rceil + 8\lfloor p/2\rfloor - 8$ for all $p\geq 6$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper defines the (≤p)-inversion graph I^{≤p}(G) whose vertices are labelled orientations of an undirected graph G, with two orientations adjacent if one is obtained from the other by inverting all arcs inside some vertex subset of size at most p. It proves that there exists a smallest constant Ψ_p satisfying ¼p − 3/2 ≤ Ψ_p ≤ ½p² such that the diameter id^{≤p}(G) of this graph is at most ⌈|E(G)| / ⌊p/2⌋⌉ + Ψ_p for every G. The paper also derives tighter upper bounds for trees (exact for p=3, linear with explicit coefficients for p=4,5, and (n-1)/(p−c√p)+2 for p≥6) and for planar graphs (linear in n with explicit additive terms for p=3,4 and ⌈(3n−6)/⌊p/2⌋⌉ + 8⌊p/2⌋−8 for p≥6).
Significance. If the central existence result holds, the work supplies a uniform additive-constant bound on inversion diameter in terms of edge count, which is a clean structural statement for a reconfiguration problem on orientations. The explicit linear-in-n upper bounds for the infinite families of trees and planar graphs, together with the matching lower-order terms for small p, constitute concrete, falsifiable predictions that strengthen the contribution.
major comments (2)
- [Main theorem on Ψ_p] The proof that Ψ_p is finite and at most ½p² (stated in the abstract and presumably proved in the main body) is load-bearing for the general theorem; the manuscript should explicitly identify the section or theorem number containing the argument that produces the quadratic upper bound, together with the precise construction or potential function used to bound the number of extra inversion steps.
- [Tree bounds section] For the tree bounds, the claim id^{≤p}_F(n) ≤ (n−1)/(p−c√p) + 2 with c=√(2+√2) for p≥6 relies on a specific choice of inversion sets along a tree; the manuscript should verify in the relevant section that the denominator p−c√p remains positive for all integer p≥6 and that the additive +2 is independent of n.
minor comments (2)
- [Introduction] The notation id^{≤p}_F(n) and id^{≤p}_P(n) is introduced without an explicit reminder that F stands for forests/trees and P for planar graphs; a short sentence in the introduction would improve readability.
- [Abstract] The abstract states the lower bound ¼p − 3/2 ≤ Ψ_p but does not name the family of graphs or the sequence of orientations that forces this linear lower bound; adding a one-sentence pointer to the construction would help readers locate the matching lower-bound argument.
Simulated Author's Rebuttal
We thank the referee for their careful reading and constructive comments on the manuscript. We address each major comment below.
read point-by-point responses
-
Referee: [Main theorem on Ψ_p] The proof that Ψ_p is finite and at most ½p² (stated in the abstract and presumably proved in the main body) is load-bearing for the general theorem; the manuscript should explicitly identify the section or theorem number containing the argument that produces the quadratic upper bound, together with the precise construction or potential function used to bound the number of extra inversion steps.
Authors: We agree that an explicit pointer to the proof of the quadratic upper bound on Ψ_p will improve readability. The argument appears in the section establishing the general bound and relies on a potential function that measures the number of edges whose orientations differ from those in a target orientation; after an initial phase, each inversion reduces the potential by at least ⌊p/2⌋, with the total number of extra steps bounded by ½p². In the revised version we will add a direct cross-reference to this section (and the relevant theorem) in the abstract and introduction, together with a one-sentence description of the potential function. revision: yes
-
Referee: [Tree bounds section] For the tree bounds, the claim id^{≤p}_F(n) ≤ (n−1)/(p−c√p) + 2 with c=√(2+√2) for p≥6 relies on a specific choice of inversion sets along a tree; the manuscript should verify in the relevant section that the denominator p−c√p remains positive for all integer p≥6 and that the additive +2 is independent of n.
Authors: We confirm that p − c√p > 0 for every integer p ≥ 6 (the value at p = 6 is approximately 1.48 and increases thereafter). The additive constant +2 is independent of n because it arises from a fixed number of initial and terminal inversion steps whose count does not grow with the size of the tree; this is already implicit in the proof but we will add an explicit verification sentence in the tree-bounds section of the revised manuscript. revision: yes
Circularity Check
No significant circularity; derivation self-contained
full rationale
Ψ_p is defined as the minimal constant making the stated inequality hold for every graph G, but the paper proves its finiteness and explicit bounds (linear lower, quadratic upper) via direct combinatorial arguments on sequences of ≤p-inversions that reduce differing arcs. This is not self-definitional: the bound is established by constructing reconfiguration paths whose length is at most the edge-count term plus a p-dependent overhead whose supremum is shown finite independently of the target diameter. No parameters are fitted to data and then relabeled as predictions, no load-bearing self-citations appear, and the tree/planar special cases are obtained from explicit matchings and inductive constructions rather than renaming known quantities. The overall claim is therefore a genuine upper-bound theorem, not a tautology.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard axioms of undirected and oriented graphs
Forward citations
Cited by 1 Pith paper
-
Increasing arc-connectivity by bounded- and fixed-size inversions
Inversions of size exactly p characterize when large digraphs become k-arc-strong, while at most p-sized inversions admit a (4k-2+ε)-approximation for the minimum number needed and are NP-hard and APX-hard to optimize.
Reference graph
Works this paper leans on
-
[1]
[ABB+26] Carmen Arana, Thomas Bellitto, Hector Buffi` ere, Quentin Chuet, Th´ eo Pierron, and Amadeus Reinald. Inversion diameter and 2-edge-colored ho- momorphisms, 2026.arXiv:2602.24171. [AHH+22] Guillaume Aubian, Fr´ ed´ eric Havet, Florian H¨ orsch, Felix Klingelhoefer, Nicolas Nisse, Cl´ ement Rambaud, and Quentin Vermande. Problems, proofs, and disp...
-
[2]
arXiv:2212.09188. [Alo06] Noga Alon. Ranking Tournaments.SIAM Journal on Discrete Mathemat- ics, 20(1):137–142,
-
[3]
[APS+24] Noga Alon, Emil Powierski, Michael Savery, Alex Scott, and Elizabeth Wilmer. Invertibility of digraphs and tournaments.SIAM Journal on Dis- crete Mathematics, 38(1):327–347, 2024.arXiv:2212.11969. [BBBP10] Houmem Belkhechine, Moncef Bouaziz, Imed Boudabbous, and Maurice Pouzet. Inversion dans les tournois.Comptes Rendus Math´ ematique, 348(13-14)...
-
[4]
[BJHH+25] Jørgen Bang-Jensen, Fr´ ed´ eric Havet, Florian H¨ orsch, Cl´ ement Ram- baud, Amadeus Reinald, and Caroline Silva. Making an oriented graph acyclic using inversions of bounded or prescribed size.arXiv preprint arXiv:2511.22562, 2025.arXiv:2511.22562. [BPP22] Marthe Bonamy, Thomas Perrett, and Luke Postle. Colouring graphs with sparse neighbourh...
-
[5]
[DHHR23] Julien Duron, Fr´ ed´ eric Havet, Florian H¨ orsch, and Cl´ ement Rambaud. On the minimum number of inversions to make a digraphk-(arc-)strong.arXiv preprint, 2023.arXiv:2303.11719. [Fer83] Wenceslas Fernandez de la Vega. On the maximum cardinality of a consis- tent set of arcs in a random tournament.Journal of Combinatorial Theory, Series B, 35(...
-
[6]
Diameter of the inversion graph.arXiv preprint, 2024.arXiv:2405.04119
[HHR24] Fr´ ed´ eric Havet, Florian H¨ orsch, and Cl´ ement Rambaud. Diameter of the inversion graph.arXiv preprint, 2024.arXiv:2405.04119. [Kar72] Richard M. Karp.Reducibility among Combinatorial Problems, page 85–103. Springer US,
-
[7]
On tournament inversion.Journal of Graph Theory, 110(1):82–91, 2025.arXiv:2312.01910
[Yus25] Raphael Yuster. On tournament inversion.Journal of Graph Theory, 110(1):82–91, 2025.arXiv:2312.01910. 25
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.