pith. sign in

arxiv: 2606.17974 · v1 · pith:GPPGZVQDnew · submitted 2026-06-16 · 🧮 math.CO

Edge-Number Bounds for the Inversion Diameter of Graphs

Jiawen Bo , Anqi Li , Xiaopan Lian , Xin Yan This is my paper

Pith reviewed 2026-06-27 00:01 UTC · model grok-4.3

classification 🧮 math.CO
keywords inversion diameterinversion graphoriented graphsCayley graphdiameter boundsbipartite graphsedge number
0
0 comments X

The pith

The inversion diameter of any graph is at most twice the square root of its number of edges.

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

The paper proves that the inversion diameter of a graph G, the longest shortest sequence of vertex-set inversions needed to turn one orientation into another, satisfies diam(I(G)) ≤ 2√|E(G)|. It also establishes a matching lower bound of |E(G)|/|V(G)| by treating the inversion graph as a Cayley graph over the vector space of edges with entries in F₂. For bipartite graphs the upper bound is sharpened to a function of the maximum degrees on each side. These results give explicit control over how many inversions are required to navigate between all possible ways of directing the edges of G.

Core claim

We prove the bound diam(I(G)) ≤ 2√|E(G)|, complement it with diam(I(G)) ≥ |E(G)|/|V(G)| obtained by viewing I(G) as a Cayley graph on F₂^E(G), and refine the upper bound for bipartite graphs to diam(I(G)) ≤ max{ρ, ⌈log₂(2 + σ(2^{ρ-1}−1))⌉} where the two parts have maximum degrees σ and ρ.

What carries the argument

The inversion graph I(G) whose vertices are the 2^|E| orientations of G and whose edges connect orientations that differ by the inversion of a single vertex set.

If this is right

  • Any two orientations of G differ by a sequence of at most 2√e inversions.
  • The inversion diameter is always at least e/n.
  • In a bipartite graph the diameter is controlled by the larger of the two maximum degrees and a logarithmic expression involving the smaller degree.
  • The Cayley-graph representation yields a linear lower bound in terms of average degree.

Where Pith is reading between the lines

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

  • The sqrt(e) scaling suggests that inversion diameter behaves like a geometric diameter in high-dimensional spaces of orientations.
  • The bipartite refinement may extend to graphs with bounded degeneracy or other structural restrictions on edge distribution.
  • The lower-bound technique using the F₂-vector space could apply to other group actions that reverse subsets of arcs.

Load-bearing premise

That the inversion graph can be identified with the Cayley graph of the elementary abelian 2-group on the edge set generated by single-edge inversions.

What would settle it

A concrete graph G together with two orientations whose shortest inversion sequence has length strictly larger than 2√|E(G)| would falsify the upper bound.

read the original abstract

The inversion of a set $X$ of vertices in an oriented graph reverses every arc with both endpoints in $X$. The inversion graph $I(G)$ of a graph $G$ has the labelled orientations of $G$ as its vertices, two orientations being adjacent when a single inversion transforms one into the other, and the inversion diameter $\diam(I(G))$ is its diameter. Answering a question of Havet, H\"orsch and Rambaud, we prove the bound in terms of edge number $\diam(I(G)) \le 2\sqrt{|E(G)|}$, and we complement it with a lower bound $\diam(I(G)) \ge \frac{|E(G)|}{|V(G)|}$ obtained by viewing $I(G)$ as a Cayley graph on $\F_2^{E(G)}$. We further refine the upper bound for bipartite graphs $G$ by showing $ \diam(I(G))\le \max\left\{\rho, \left\lceil\log_2\bigl(2+\sigma(2^{\rho-1}-1)\bigr)\right\rceil\right\}$ where the two parts of $G$ have maximum degrees $\sigma$ and $\rho$, respectively.

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

0 major / 2 minor

Summary. The manuscript studies the inversion graph I(G) whose vertices are the 2^{|E(G)|} orientations of an undirected graph G, with two orientations adjacent if one is obtained from the other by inverting all arcs inside a vertex subset X. It proves the upper bound diam(I(G)) ≤ 2√|E(G)|, complements it with the lower bound diam(I(G)) ≥ |E(G)|/|V(G)| by realizing I(G) as the Cayley graph of the elementary abelian 2-group F₂^{E(G)} generated by the single-edge vectors, and gives a tighter upper bound diam(I(G)) ≤ max{ρ, ⌈log₂(2 + σ(2^{ρ-1}−1))⌉} when G is bipartite with part-wise maximum degrees σ and ρ.

Significance. If the proofs are correct, the results answer the question posed by Havet, Hörsch and Rambaud by supplying the first explicit diameter bounds expressed solely in terms of |E(G)| (and, for bipartite graphs, in terms of the two maximum degrees). The Cayley-graph identification yields a clean, parameter-free linear lower bound that matches the square-root upper bound up to a constant factor; the bipartite refinement replaces the square-root dependence by a logarithmic one in the degrees. These are concrete, falsifiable statements that advance the quantitative understanding of orientation reconfiguration under inversions.

minor comments (2)
  1. [Abstract / §1] The abstract states the bipartite bound with the clause “where the two parts of G have maximum degrees σ and ρ, respectively,” but the manuscript should add a sentence in §1 or §3 explicitly declaring which part receives σ and which receives ρ to avoid any ambiguity when the parts are not labelled.
  2. [§2 (lower-bound paragraph)] The Cayley-graph argument for the lower bound relies on the standard diameter estimate diam(Cay(G,S)) ≥ log_{|S|+1} |G|; while this is correctly invoked, a one-line reference to the elementary counting |G| ≤ 1 + |S| + … + |S|^d would make the derivation self-contained for readers outside group theory.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive report, the clear summary of our results, and the recommendation to accept the manuscript.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper derives the upper bound diam(I(G)) ≤ 2√|E(G)| via direct combinatorial arguments on sequences of inversions and the lower bound diam(I(G)) ≥ |E(G)|/|V(G)| by identifying I(G) as the Cayley graph of F₂^{E(G)} generated by single-edge flips, then applying the standard external fact that the diameter of such a Cayley graph is at least n/m where n = |E(G)| and m ≤ 2^{|V(G)|}. Both steps rely on independent group-theoretic and graph-theoretic facts rather than self-citations, fitted parameters, or self-definitional reductions. No load-bearing self-citation chains or ansatzes smuggled via prior work are present; the derivation is self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on the standard definition of oriented graphs, the group structure of F₂^E(G) under symmetric difference, and the general fact that Cayley graphs on abelian groups have diameter at least rank divided by generator-set size. No free parameters or invented entities appear.

axioms (2)
  • standard math The set of orientations of G forms an elementary abelian 2-group under symmetric difference of arc sets, with single-edge inversions as generators.
    Invoked in the sentence that obtains the lower bound by viewing I(G) as a Cayley graph on F₂^E(G).
  • standard math The diameter of any Cayley graph Cay(Γ,S) satisfies diam ≥ rank(Γ) / |S| when Γ is elementary abelian 2-group.
    Used to translate the generator count |E(G)| into the lower bound |E(G)|/|V(G)|.

pith-pipeline@v0.9.1-grok · 5748 in / 1632 out tokens · 38980 ms · 2026-06-27T00:01:02.075847+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

  1. [1]

    N. Alon, E. Powierski, M. Savery, A. Scott, and E. Wilmer, Invertibility of digraphs and tour- naments,SIAM J. Discrete Math.38(1) (2024), 327–347

    2024

  2. [2]

    Arana, T

    C. Arana, T. Bellitto, H. Buffière, Q. Chuet, T. Pierron, and A. Reinald, Inversion diameter and 2-edge-colored homomorphisms,arXiv:2602.24171(2026)

    arXiv 2026

  3. [3]

    Aubian, F

    G. Aubian, F. Havet, F. Hörsch, F. Klingelhoefer, N. Nisse, C. Rambaud, and Q. Vermande, Problems, proofs, and disproofs on the inversion number,Electron. J. Combin.32(1) (2025), P1.42

    2025

  4. [4]

    Bang-Jensen, J

    J. Bang-Jensen, J. C. F. da Silva, and F. Havet, On the inversion number of oriented graphs, Discrete Math. Theor. Comput. Sci.23(2) (2022)

    2022

  5. [5]

    Belkhechine, Indécomposabilité des graphes et des tournois,Theses, Université Claude Bernard-Lyon I; Université de Sfax

    H. Belkhechine, Indécomposabilité des graphes et des tournois,Theses, Université Claude Bernard-Lyon I; Université de Sfax. Faculté des sciences, (2009)

    2009

  6. [6]

    Belkhechine, M

    H. Belkhechine, M. Bouaziz, I. Boudabbous, and M. Pouzet, Inversion dans les tournois,C. R. Math. Acad. Sci. Paris348(13–14) (2010), 703–707

    2010

  7. [7]

    F. R. Chung and R. L. Graham, Quasi-random tournaments,J. Graph Theory15(2) (1991), 173–198. 11

    1991

  8. [8]

    Duron, F

    J. Duron, F. Havet, F. Hörsch, and C. Rambaud, On the minimum number of inversions to make a digraphk-(arc-)strong,J. Graph Theory111(2) (2025), 31–62

    2025

  9. [9]

    Füredi, J

    Z. Füredi, J. R. Griggs, R. Holzman, and D. J. Kleitman, Representations of families of triples over GF(2),J. Combin. Theory Ser. A53(2) (1990), 306–315

    1990

  10. [10]

    Havet, F

    F. Havet, F. Hörsch, and C. Rambaud, Diameter of the inversion graph,Innov. Graph Theory 3 (2026), 49–88

    2026

  11. [11]

    Spencer, Optimal ranking of tournaments,Networks1(2) (1971), 135–138

    J. Spencer, Optimal ranking of tournaments,Networks1(2) (1971), 135–138

    1971

  12. [12]

    Spencer, Optimally ranking unrankable tournaments,Period Math Hung11(2) (1980), 131– 144

    J. Spencer, Optimally ranking unrankable tournaments,Period Math Hung11(2) (1980), 131– 144

    1980

  13. [13]

    Yuster, On tournament inversion,J

    R. Yuster, On tournament inversion,J. Graph Theory110 (2025), 82–91

    2025

  14. [14]

    W. F. de la Vega, On the maximum cardinality of a consistent set of arcs in a random tour- nament,J. Combin. Theory Ser. B35(3) (1983), 328–332

    1983

  15. [15]

    Y. Wang, H. Wang, Y. Yang, and M. Lu, Inversion diameter and treewidth,Discrete Math. Theor. Comput. Sci.28(2) (2026). 12

    2026