Pith. sign in

REVIEW 3 minor 23 references

Ordering and refining path-complete Lyapunov functions through composition lifts

T0 review · 0 major / 3 minor · reviewed 2026-05-22 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗

Pith's one-line read A conjecture that the composition lift preserves preorder relations on path-complete Lyapunov functions is false, revealing a structural feature for iterative graph refinement.

desk verdict The paper refutes the composition lift conjecture but turns the counterexample into a concrete graph refinement procedure and adapted lift. read the letter →

arxiv 2503.18189 v2 submitted 2025-03-23 math.OC cs.SYeess.SY

Wouter Jongeneel , Raphaël M. Jungers This is my paper
classification math.OCcs.SYeess.SY
keywords path-completeLyapunovfunctionsswitchedsystemscompositionliftpreordersstabilityanalysisgraphrefinementmultiplecombinatorialmethods
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

The paper studies how multiple Lyapunov functions can certify stability in switched systems through path-complete graphs. It demonstrates that an earlier conjecture claiming the composition lift turns algebraic preorders into combinatorial ones without loss of information does not hold. The counterexample nevertheless exposes a useful structural property of the lift, which the authors use to construct an iterative refinement procedure for the graphs and to propose a modified version of the lift itself. A sympathetic reader would care because the result clarifies when and how graphical templates for Lyapunov functions can be compared and improved without solving the full set of algebraic inequalities at each step.

What carries the argument

The composition lift, an operation that maps algebraic preorder comparisons of multiple Lyapunov functions to combinatorial comparisons on path-complete graphs.

What would settle it

A concrete switched linear system together with two path-complete graphs and associated Lyapunov functions such that applying the composition lift produces a combinatorial relation that contradicts the algebraic preorder between the functions.

Watch

Extended reading notes

Core claim

While the composition lift was conjectured to preserve the preorder relations among path-complete Lyapunov functions, making comparison purely combinatorial, this property does not hold in general. The refutation identifies a beneficial structural feature of the lift that supports an iterative refinement process on the underlying graphs and motivates a favourable adaptation of the lift operator.

Load-bearing premise

The preorders introduced to compare multiple Lyapunov functions, when combined with the proposed lifting techniques, correctly capture the stability properties without introducing spurious combinatorial artifacts that would invalidate the refinement procedure.

Editorial extensions

If this is right

  • Path-complete graphs can be iteratively refined by exploiting the structural feature uncovered in the composition lift.
  • An adapted form of the composition lift becomes available that respects the preorder in a more controlled way.
  • Some preorders on Lyapunov functions become algorithmically tractable through the refined lifting procedure.
  • The interplay between the choice of Lyapunov template and the switching signal can be explored combinatorially after refinement.

Reading between the lines

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

  • The refinement procedure may reduce the number of decision variables needed when searching for stability certificates in concrete switched systems.
  • Similar structural features could appear in other lift operators used for comparing multiple Lyapunov functions.
  • The approach suggests a way to generate sequences of successively tighter graphical certificates without restarting the search from scratch.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 3 minor

Summary. The manuscript refutes a conjecture on the composition lift for path-complete Lyapunov functions in switched systems by exhibiting a counterexample. It then exploits a structural feature of the composition lift revealed by the refutation to enable iterative refinement of path-complete graphs and to introduce an adapted composition lift.

Significance. If the counterexample is valid and the refinement procedure preserves stability properties without introducing spurious combinatorial artifacts, the work corrects a prior belief in the literature and converts the refutation into a practical tool for improving path-complete certificates. The explicit counterexample and derivation of positive consequences from it constitute a clear strength, as does the focus on combinatorial lifts that avoid parameter-dependent fitting.

minor comments (3)
  1. The abstract states that the refutation 'points us to a beneficial structural feature' but does not name the feature; a one-sentence description in the abstract would improve readability.
  2. Notation for the preorders and the various lifts should be collected in a single preliminary section or table to avoid repeated redefinitions when the refinement procedure is introduced.
  3. Figure captions (if present) should explicitly indicate which lift or preorder is illustrated in each panel to facilitate comparison with the textual claims.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, accurate summary of the contributions, and recommendation for minor revision. The significance of refuting the conjecture while extracting a practical refinement procedure is well noted. No specific major comments were raised in the report.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; refutation is self-contained via counterexample

full rationale

The paper's core contribution is an explicit counterexample refuting a prior conjecture on the composition lift for path-complete Lyapunov functions, followed by derivation of positive structural consequences for graph refinement. No load-bearing step reduces by construction to fitted parameters, self-definitions, or unverified self-citations; the preorders and lifts are treated as given inputs from prior literature, and the refutation itself is independent and falsifiable. The derivation chain does not invoke uniqueness theorems or ansatzes from the authors' own prior work in a circular manner. This matches the default expectation of non-circularity for a direct mathematical refutation.

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

Review based on abstract only. No free parameters, invented entities, or non-standard axioms are identifiable from the provided text. The work relies on standard domain assumptions from Lyapunov stability theory for switched systems.

assumptions (1)
  • domain assumption Lyapunov inequalities can be used to certify stability of switched systems via multiple functions organized by path-complete graphs.
    Standard background assumption in the field of switched system stability invoked throughout the abstract.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Ordering and refining path-complete Lyapunov functions through composition lifts." pith.science (2026). https://pith.science/paper/2503.18189

@misc{pith2026250318189,
  author       = {Pith},
  title        = {Pith review of: Ordering and refining path-complete Lyapunov functions through composition lifts},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2503.18189}},
  note         = {Machine review of arXiv:2503.18189}
}
read the original abstract

A fruitful approach to study stability of switched systems is to look for multiple Lyapunov functions. However, in general, we do not yet understand the interplay between the desired stability certificate, the template of the Lyapunov functions and their mutual relationships to accommodate switching. In this work we elaborate on path-complete Lyapunov functions: a graphical framework that aims to elucidate this interplay. In particular, previously, several preorders were introduced to compare multiple Lyapunov functions. These preorders are initially algorithmically intractable due to the algebraic nature of Lyapunov inequalities, yet, lifting techniques were proposed to turn some preorders purely combinatorial and thereby eventually tractable. In this note we show that a conjecture in this area regarding the so-called composition lift, that was believed to be true, is false. This refutal, however, points us to a beneficial structural feature of the composition lift that we exploit to iteratively refine path-complete graphs, plus, it points us to a favourable adaptation of the composition lift.

Figures

Figures reproduced from arXiv: 2503.18189 by the authors.

Figure 1
Figure 1. Similarly, one could consider the inequalities [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 1
Figure 1. The graphs G1 and G2 as in [9, Ex. 3.9]. are graphs that can be ordered with respect to this template, yet, the ordering does not imply the existence of a T-sum lift simulation relation. This shows that Theorem II.2 fails subject to these restrictions. This motivates new lifts. Here, we can build upon [9, Ex. 3.9]. It can be shown that there is no simulation relation between G1 = (S1, E1) and G2 = (S2, E2) as drawn … view at source ↗
Figure 3
Figure 3. Even for strongly-connected graphs, the T-sum lift can result in a graph that fails to be connected (e.g. G ⊕2 α = Gα ⊔ G0), this, in contrast to the T-composition lift. whenever G is connected and without sinks (i.e, all nodes have outgoing edges), n.b., we merely discuss connectedness here, not graphs being strongly connected, see [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: The graphs corresponding to Example IV.3. [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]
Figure 5
Figure 5. Figure 5: Example construction of the transitive closure of [PITH_FULL_IMAGE:figures/full_fig_p006_5.png]
Figure 6
Figure 6. Figure 6: Reconsider the graphs Gφ and Gψ from Example IV.3. Although G ◦ φ does not simulate Gψ, (G ◦ φ) + does. Vc(fj (x)) and work with a template closed under compo￾sition with fi and fj , then we get Va(x) ≥ V(c,j)(fi(x)) for free. By identifying any expression of the form …

Discussion (0). Sign in to comment.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    Liberzon, Switching in systems and control

    D. Liberzon, Switching in systems and control . Birkh ¨auser, 2003

    work page 2003

  2. [2]

    Tabuada, Verification and control of hybrid systems: a symbolic approach

    P. Tabuada, Verification and control of hybrid systems: a symbolic approach. Springer, 2009

    work page 2009

  3. [3]

    Goebel, R

    R. Goebel, R. G. Sanfelice, and A. R. Teel, Hybrid dynamical systems. Princeton University Press, 2012

    work page 2012

  4. [4]

    R. G. Sanfelice, Hybrid Feedback Control . Princeton University Press, 2020

    work page 2020

  5. [5]

    Jongeneel and E

    W. Jongeneel and E. Moulay, Topological Obstructions to Stability and Stabilization: History, Recent Advances and Open Problems . Springer Nature, 2023

    work page 2023

  6. [6]

    Jungers, The joint spectral radius: theory and applications

    R. Jungers, The joint spectral radius: theory and applications . Springer, 2009

    work page 2009

  7. [7]

    Multiple Lyapunov functions and other analysis tools for switched and hybrid systems,

    M. S. Branicky, “Multiple Lyapunov functions and other analysis tools for switched and hybrid systems,” IEEE T. Automat. Contr. , vol. 43, no. 4, pp. 475–482, 1998

    work page 1998

  8. [8]

    Joint spectral radius and path-complete graph Lyapunov functions,

    A. A. Ahmadi, R. M. Jungers, P. A. Parrilo, and M. Roozbehani, “Joint spectral radius and path-complete graph Lyapunov functions,” SIAM J. Control Optim. , vol. 52, no. 1, pp. 687–717, 2014

    work page 2014

Show all 23 references
  1. [9]

    A complete characterization of the ordering of path-complete methods,

    M. Philippe and R. M. Jungers, “A complete characterization of the ordering of path-complete methods,” in International Conference on Hybrid Systems: Computation and Control , 2019, pp. 138–146

    2019

  2. [10]

    Path-complete and neural Lyapunov functions: Com- putation and performance,

    V . Debauche, “Path-complete and neural Lyapunov functions: Com- putation and performance,” Ph.D. dissertation, UCLouvain, 2024. [Online]. Available: https : / / dial . uclouvain . be / pr / boreal/object/boreal:291972

    2024

  3. [11]

    A note on the joint spectral radius,

    G.-C. Rota and G. Strang, “A note on the joint spectral radius,” Indag. Math, vol. 22, no. 4, pp. 379–381, 1960

    1960

  4. [12]

    Algebraic unsolvability of problem of absolute sta- bility of desynchronized systems,

    V . S. Kozyakin, “Algebraic unsolvability of problem of absolute sta- bility of desynchronized systems,” Automation and Remote Control , vol. 51, no. 6, pp. 754–759, 1990

    1990

  5. [13]

    The Lyapunov exponent and joint spectral radius of pairs of matrices are hard—when not impos- sible—to compute and to approximate,

    J. N. Tsitsiklis and V . D. Blondel, “The Lyapunov exponent and joint spectral radius of pairs of matrices are hard—when not impos- sible—to compute and to approximate,” Math. Control Signals Syst., vol. 10, pp. 31–40, 1997

    1997

  6. [14]

    The boundedness of all products of a pair of matrices is undecidable,

    V . D. Blondel and J. N. Tsitsiklis, “The boundedness of all products of a pair of matrices is undecidable,” Syst. Control Lett. , vol. 41, no. 2, pp. 135–140, 2000

    2000

  7. [15]

    Approximation of the joint spectral radius using sum of squares,

    P. A. Parrilo and A. Jadbabaie, “Approximation of the joint spectral radius using sum of squares,” Linear Algebra Appl., vol. 428, no. 10, pp. 2385–2402, 2008

    2008

  8. [16]

    Characterization of the ordering of path-complete stability certificates with addition- closed templates,

    V . Debauche, M. Della Rossa, and R. Jungers, “Characterization of the ordering of path-complete stability certificates with addition- closed templates,” in International Conference on Hybrid Systems: Computation and Control , 2023, pp. 1–10

    2023

  9. [17]

    Stability analysis of discrete- time switched systems through Lyapunov functions with nonminimal state,

    P.-A. Bliman and G. Ferrari-Trecate, “Stability analysis of discrete- time switched systems through Lyapunov functions with nonminimal state,” IFAC Proceedings, vol. 36, no. 6, pp. 325–329, 2003

    2003

  10. [18]

    Equivalence of stability concepts for discrete time-varying systems,

    A. Bhaya, F. Das, and C. Mota, “Equivalence of stability concepts for discrete time-varying systems,” Int. J. Robust Nonlin. , vol. 4, no. 6, pp. 725–740, 1994

    1994

  11. [19]

    On path-complete Lyapunov functions: Geometry and comparison,

    M. Philippe, N. Athanasopoulos, D. Angeli, and R. M. Jungers, “On path-complete Lyapunov functions: Geometry and comparison,” IEEE T. Automat. Contr., vol. 64, no. 5, pp. 1947–1957, 2018

    1947

  12. [20]

    Comparison of path-complete Lyapunov functions via template-dependent lifts,

    V . Debauche, M. Della Rossa, and R. M. Jungers, “Comparison of path-complete Lyapunov functions via template-dependent lifts,” Nonlinear Analysis: Hybrid Systems , vol. 46, p. 101 237, 2022

    2022

  13. [21]

    Solving semidefinite- quadratic-linear programs using SDPT3,

    R. H. T ¨ut¨unc¨u, K.-C. Toh, and M. J. Todd, “Solving semidefinite- quadratic-linear programs using SDPT3,” Math. Program., vol. 95, pp. 189–217, 2003

    2003

  14. [22]

    On preorders of path-complete Lyapunov functions through lifts,

    W. Jongeneel and R. M. Jungers, “On preorders of path-complete Lyapunov functions through lifts,” in Benelux Meeting on Systems and Control, 2025, p. 50

    2025

  15. [23]

    Statistical comparison of path-complete Lyapunov functions: A discrete-event systems perspective,

    R. M. Jungers, “Statistical comparison of path-complete Lyapunov functions: A discrete-event systems perspective,” IFAC Proceedings, vol. 58, no. 1, pp. 258–263, 2024

    2024

Pith tools

Reviewed May 22, 2026 · model on record in the stance chip above.