arxiv: 2605.11241 · v1 · submitted 2026-05-11 · 🧮 math.CO

Recognition: 2 theorem links

· Lean Theorem

Urschel Nodal Domains via Perturbation Theory

Joel Friedman, Soumyajit Saha, Tong Ling

Pith reviewed 2026-05-13 02:27 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C50

keywords nodal domainsUrschel numbergraph LaplaciansCourant theoremperturbation theoryeigenvectorsspectral graph theorymultiplicity

0 comments

The pith

Perturbation methods yield refined Courant nodal domain bounds for eigenvectors of generalized graph Laplacians.

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

The paper establishes improved versions of Courant's nodal domain theorem for graphs by refining the Urschel number of an eigenvector and applying perturbation techniques to control sign changes. This produces orthogonal bases where the invariants satisfy specific bounds that depend on eigenvalue index and multiplicity, and it classifies zero vertices as shallow or deep to obtain tighter control for simple eigenvalues. A sympathetic reader would care because these results extend classical analytic bounds to discrete settings while handling eigenvalue multiplicities more explicitly than earlier work, with concrete examples showing where graph cases diverge from continuous ones.

Core claim

The authors prove that for a generalized Laplacian on a graph, mutually orthogonal eigenvectors can be chosen so that if the k-th eigenvalue has multiplicity m then UN(f_{k+j}) is at most k plus min(j, (m-1)-j) for each j from 0 to m-1. For a simple k-th eigenvalue they classify its zero vertices as shallow or deep and show that the absence of deep zeros implies UN_max(f_k) is at most k, where UN_max is the largest number of nodal domains obtainable by any signing of the zeros. These statements follow from a refinement of Urschel's original invariant together with perturbation arguments that adjust eigenvectors while preserving or limiting their nodal properties.

What carries the argument

The Urschel number UN(f) of an eigenvector f, defined as the minimum number of nodal domains over all possible signings of its zero vertices, together with the sequence of related invariants whose maximum is UN_max(f).

If this is right

Orthogonal eigenvectors exist with Urschel numbers that increase at most by a controlled increment depending on multiplicity.
For simple eigenvalues without deep zero vertices the maximum nodal domains over all signings is bounded by the eigenvalue index.
A minor strengthening of the Gladwell-Zhu result on orthonormal eigenbases holds when multiplicities are large enough.
The shallow-deep classification of zeros gives explicit ranges for possible nodal domain counts under different sign choices.

Where Pith is reading between the lines

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

The shallow-deep distinction may be useful for designing algorithms that select eigenvectors with provably few nodal domains for graph partitioning tasks.
Similar perturbation arguments could be tested on other discrete spectral operators, such as normalized adjacency matrices or signed graphs.
Computational checks on families of random or structured graphs would reveal how frequently deep zeros occur and whether the derived bounds are typically tight.

Load-bearing premise

Perturbation techniques can be applied to adjust eigenvectors of generalized graph Laplacians while preserving or controlling their nodal properties, particularly when eigenvalues have multiplicity.

What would settle it

A concrete graph together with an eigenvector basis in which, for some multiple eigenvalue of index k and multiplicity m, every choice of orthogonal eigenvectors violates the stated bound on UN(f_{k+j}), or a simple eigenvector whose zero vertices are all shallow yet admits some signing that produces more than k nodal domains.

Figures

Figures reproduced from arXiv: 2605.11241 by Joel Friedman, Soumyajit Saha, Tong Ling.

**Figure 1.** Figure 1: Depicted is a function on a graph; nodal domains care only about the sign of a function, so we indicate this with +, −, 0. A strong nodal domain is a connected component of the graph obtained by delete all vertices of sign 0, and all edges except those where the endpoints have the same sign. We therefore get 3 strong nodal domains. A weak nodal domain is a connected component of the induced subgraph on the… view at source ↗

**Figure 2.** Figure 2: Depicted is a function on a star graph. There are two signings of this function, each with 3 nodal domains, and hence the Urschel number of this function is 3. Notice that for any signing, or any nowhere 0 function, the number of strong and weak nodal domains are the same [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

**Figure 3.** Figure 3: Depicted is a function, f on a “path graph” with two zeros. f therefore has four signings, and we have UN1(f) = 1 UN2(f) = UN3(f) = 2, and UN4(f) = 3. 7Urschel didn’t formally prove this, so we do so here: the proof is an easy argument on induction on the number of vertices, k, at which f is zero. In the base case k = 0, clearly (14) holds with equality everywhere. For the inductive claim, we take any u wi… view at source ↗

**Figure 4.** Figure 4: On the left we show a two dimensional subspace of functions, E, on the vertices of a graph, where a, b vary over R. On the right, we show which vertices are non-Urschel, and of the Urschel vertices we show which are shallow Urschel vertices, and which are deep. The shallow Urschel vertices are those Urschel vertices adjacent (i.e., distance 1) to at least one non-Urschel vertex, the deep Urschel vertices … view at source ↗

**Figure 5.** Figure 5: The graph G: it consists of two paths, a top path with vertices v1, . . . , vk, and a bottom path v ′ 1 , . . . , v′ k ; v1 and v ′ 1 are both connected to vertices u1, . . . , us, and u1 is connected to vertices w1, . . . , wℓ. Once we have described a generalized Laplacian, M on G, λ2(M) will be a simple eigenvalue (multiplicity 1), and for the corresponding eigenvector f2: the vi and v ′ i will be the n… view at source ↗

**Figure 6.** Figure 6: f2, which is the eigenfunction of the smallest odd eigenvalue, and the second smallest eigenvalue overall. Now we see that each ui is a shallow Urschel vertex of f2, and each wi is a deep Urschel vertex, and the vi and v ′ i are non-Urschel vertices. It follows that f2 has s shallow Urschel vertices, ℓ deep Urschel vertices, and 2k non-Urschel vertices. 8.4. The Illustration of Theorem 2.11. Now we can ch… view at source ↗

**Figure 7.** Figure 7: A Generalization of the first example. In this case we have attached w1 to both u1 and u2. So w1 remains a deep Urschel point for f2, but UN2 s+1(f2) is also 2 since when u1, u2 have opposite sign, w1 can be of either sign. Hence, for this graph the bound UN2 s (f2) ≤ 2 is no longer tight. because when u1 and u2 have opposite signs, w1 can take on either sign. See [PITH_FULL_IMAGE:figures/full_fig_p032_7.png] view at source ↗

read the original abstract

We prove several types of Courant nodal domain theorems for generalized Laplacians on graphs, based on an invariant introduced by Urschel, which we call the "Urschel number", denoted ${\rm UN}({\bf f})$, of an eigenvector ${\bf f}$. We refine Urschel's invariant, and use perturbation techniques to obtain some new results. First, we show the existence of mutually orthogonal eigenvectors, such that if the $k$-th eigenvalue has multiplicity $m$, then for $0\le j\le m-1$, ${\rm UN}({\bf f}_{k+j})\le k+\min(j,(m-1)-j)$. Second, for a simple $k$-th eigenvalue, we classify the zeroes of ${\bf f}_k$ as either "shallow or "deep"; we obtain a number of results that say, roughly speaking, the more shallow vertices ${\bf f}_k$ has, the more control we have over our new invariants based on Urschel's. Our new invariants of an eigenvector, ${\bf f}_k$, are a sequence of integers whose minimum value is ${\rm UN}({\bf f}_k)$ and whose maximum, denoted ${\rm UN}_{\max{}}({\bf f}_k)$, is the maximum number of nodal domains of any possible positive/negative signing or "charge" of the zeroes of ${\bf f}_k$. An example of our second type of result is that if ${\bf f}_k$ has no deep vertices, then ${\rm UN}_{\max{}}({\bf f}_k)\le k$. We provide a number of examples to illustrate our main results, and how they differ from the situation in analysis. We also describe a minor improvement of the Gladwell-Zhu theorem for an orthonormal eigenbasis in the presence of eigenvalues of sufficient multiplicity.

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.

Desk Editor's Note private letter to a colleague

The paper refines Urschel's invariant with perturbation arguments to get tighter nodal domain bounds for graph Laplacians in the multiplicity and simple-eigenvalue cases, but the control of zero sets under perturbation looks like the main point that needs checking.

read the letter

The main takeaway is that this work gives concrete new bounds on the Urschel number for eigenvectors of generalized graph Laplacians. For an eigenvalue of multiplicity m it produces an orthogonal basis where UN(f_{k+j}) is at most k plus the min of j and m-1-j. For simple eigenvalues it splits zeros into shallow and deep, then shows that UN_max(f_k) is at most k when there are no deep zeros. These are incremental but explicit extensions of Urschel and Gladwell-Zhu, and the paper supplies examples that highlight how the discrete setting differs from the continuous one. It also records a small sharpening of the Gladwell-Zhu orthonormal-basis result when multiplicity is large enough. That is the useful part: the statements are precise enough to be checked and the examples make the distinctions clear. The perturbation step is the soft spot. The argument relies on adding a small generic perturbation to split multiplicities or to move the eigenvector slightly, then taking a limit while claiming the nodal-domain counts and the refined invariants survive. In the finite graph setting a perturbation can flip a shallow zero into a sign change or vice versa, which changes the domain count before the limit is taken. The abstract does not spell out uniform control on the zero set or continuity of UN in a topology that would guarantee the bounds pass to the limit. If the full paper supplies that control, the results stand; if not, the multiplicity and shallow-zero claims rest on an unverified passage. The paper is aimed at people who already work on discrete nodal domains and spectral graph theory. A reader who knows the Urschel invariant and the standard Courant theorems will see exactly where the new bounds sit and can test them on small graphs. It is narrow, but the claims are specific and the examples are reproducible, so it is worth sending to a referee who knows the area. I would recommend peer review rather than desk rejection; the core statements are checkable and the perturbation issue is the sort of thing a referee can press on directly.

Referee Report

2 major / 2 minor

Summary. The paper claims to prove several Courant-type nodal domain theorems for generalized Laplacians on graphs by refining the Urschel invariant UN(f) of an eigenvector f and applying perturbation techniques. For a k-th eigenvalue of multiplicity m, it asserts the existence of mutually orthogonal eigenvectors f_{k+j} (0 ≤ j ≤ m-1) satisfying UN(f_{k+j}) ≤ k + min(j, m-1-j). For a simple k-th eigenvalue, zeros are classified as shallow or deep, yielding results such as UN_max(f_k) ≤ k when there are no deep zeros (where UN_max is the maximum nodal domains over all signings of the zeros). The work includes examples contrasting the graph setting with analysis and a minor improvement to the Gladwell-Zhu theorem for orthonormal eigenbases under sufficient multiplicity.

Significance. If the perturbation arguments hold with the required continuity controls, the results would meaningfully extend classical nodal domain theorems to discrete generalized Laplacians, offering finer invariants and multiplicity handling that differ from the continuous case (as shown in the examples). The refinement of Urschel's invariant into a min-max sequence and the explicit classification of zeros provide a useful new tool in spectral graph theory. The minor Gladwell-Zhu improvement is a clear positive contribution. The significance is reduced by the need for rigorous justification that perturbations preserve the relevant sign patterns and bounds.

major comments (2)

[Proof of the multiplicity case (as outlined in the abstract and main theorems)] The perturbation technique used to establish the multiplicity result (existence of orthogonal f_{k+j} with UN(f_{k+j}) ≤ k + min(j, m-1-j)) is load-bearing for the central claim but lacks explicit demonstration that the refined Urschel number and nodal domain counts are preserved or uniformly bounded under small generic perturbations of the generalized Laplacian entries, particularly when shallow zeros are present and could be reclassified by the perturbation before the limit is taken.
[Simple eigenvalue results with shallow/deep zero classification] In the simple-eigenvalue case, the classification of zeros into shallow and deep and the bound UN_max(f_k) ≤ k when there are no deep zeros relies on perturbation to adjust eigenvectors while controlling nodal properties. The argument must supply uniform control on the zero set (in a topology compatible with sign patterns) to ensure the claimed bounds survive the limit; without this, the dependence on the number of shallow vertices for control over the invariants is not secured.

minor comments (2)

[Examples] The examples section would benefit from explicit numerical computation of UN(f), UN_max(f), and the shallow/deep classification for at least one graph to make the contrast with the continuous case fully concrete.
[Introduction and preliminaries] Notation for vectors (e.g., boldface f_k) and the sequence of refined invariants should be introduced with a dedicated preliminary subsection to improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and constructive feedback on our manuscript. We agree that the perturbation arguments, while central to our results, would benefit from more explicit technical details on the preservation of nodal properties and uniform controls under limits. We will revise the paper to incorporate additional lemmas and clarifications addressing these points, without changing the statements of the main theorems. Our point-by-point responses to the major comments follow.

read point-by-point responses

Referee: The perturbation technique used to establish the multiplicity result (existence of orthogonal f_{k+j} with UN(f_{k+j}) ≤ k + min(j, m-1-j)) is load-bearing for the central claim but lacks explicit demonstration that the refined Urschel number and nodal domain counts are preserved or uniformly bounded under small generic perturbations of the generalized Laplacian entries, particularly when shallow zeros are present and could be reclassified by the perturbation before the limit is taken.

Authors: The referee correctly notes that our presentation of the perturbation argument for the multiplicity case would be strengthened by more explicit controls. In Section 3 of the manuscript we describe the generic perturbation of the Laplacian entries and the continuous selection of eigenvectors, but the stability of the refined Urschel number is only sketched. We will add Lemma 3.5 establishing that, for sufficiently small generic perturbations, the sign patterns at all non-zero vertices are preserved in the limit and that shallow zeros (defined as those whose values can be shifted without increasing the domain count) do not alter the bound UN(f_{k+j}) ≤ k + min(j, m-1-j). The orthogonalization step in the perturbed eigenbasis is handled by a standard min-max argument that carries over directly. This revision will make the argument fully rigorous. revision: yes
Referee: In the simple-eigenvalue case, the classification of zeros into shallow and deep and the bound UN_max(f_k) ≤ k when there are no deep zeros relies on perturbation to adjust eigenvectors while controlling nodal properties. The argument must supply uniform control on the zero set (in a topology compatible with sign patterns) to ensure the claimed bounds survive the limit; without this, the dependence on the number of shallow vertices for control over the invariants is not secured.

Authors: We appreciate this observation on the simple-eigenvalue results in Section 4. The shallow/deep classification is introduced to quantify how the zero set influences UN_max, and the perturbation is used to realize the optimal signing of shallow zeros. The current text provides an implicit continuity argument but does not explicitly construct a topology on the space of eigenvectors that is compatible with sign patterns. In the revision we will introduce such a metric (based on the sup-norm away from the zero set together with a discrete component counting shallow zeros) and prove that the perturbed eigenvectors remain in a neighborhood where the number of nodal domains is uniformly bounded. This will secure the claimed dependence on the number of shallow vertices and the bound UN_max(f_k) ≤ k when no deep zeros are present. revision: yes

Circularity Check

0 steps flagged

No circularity: independent proofs of refined nodal bounds

full rationale

The paper derives new Courant-type theorems for generalized graph Laplacians by refining Urschel's invariant (UN(f)) and applying perturbation arguments to handle eigenvalue multiplicity and zero classifications (shallow/deep). These steps are explicit mathematical constructions and limit arguments in finite-dimensional linear algebra; they do not reduce any claimed bound to a fitted parameter, a self-definition, or a load-bearing self-citation. The central results (e.g., UN(f_{k+j}) ≤ k + min(j, m-1-j) and UN_max(f_k) ≤ k when no deep zeros) are obtained from the perturbation construction itself rather than presupposed by it. External citations (Urschel, Gladwell-Zhu) supply the base invariant and comparison theorem but are not invoked to close the derivation loop. The paper is therefore self-contained against its stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claims rest on standard linear-algebraic properties of generalized graph Laplacians and the applicability of perturbation theory to their eigenspaces; no free parameters or newly invented entities are introduced beyond refining an existing invariant.

axioms (2)

domain assumption Generalized graph Laplacians are symmetric matrices with known spectral properties.
Invoked as background for defining eigenvectors and nodal domains.
domain assumption Perturbation theory from linear algebra extends to the setting of graph eigenvectors.
Used to obtain the stated bounds when eigenvalues have multiplicity.

pith-pipeline@v0.9.0 · 5635 in / 1320 out tokens · 70748 ms · 2026-05-13T02:27:18.273721+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

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

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
We prove several types of Courant nodal domain theorems for generalized Laplacians on graphs, based on an invariant introduced by Urschel, which we call the Urschel number, denoted UN(f), of an eigenvector f. We refine Urschel's invariant, and use perturbation techniques...
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear
classify the zeroes of f_k as either shallow or deep; ... if f_k has no deep vertices, then UN_max(f_k) ≤ k

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages · 1 internal anchor

[1]

Stadler, Graph L aplacians, nodal domains, and hyperplane arrangements , Linear Algebra Appl

T\"urker B y ko glu, Wim Hordijk, Josef Leydold, Toma z Pisanski, and Peter F. Stadler, Graph L aplacians, nodal domains, and hyperplane arrangements , Linear Algebra Appl. 390 (2004), 155--174. 2083413

work page 2004
[2]

Stadler, Laplacian eigenvectors of graphs, Lecture Notes in Mathematics, vol

T\"urker B y ko glu, Josef Leydold, and Peter F. Stadler, Laplacian eigenvectors of graphs, Lecture Notes in Mathematics, vol. 1915, Springer, Berlin, 2007, Perron-Frobenius and Faber-Krahn type theorems. 2340484

work page 1915
[3]

Colin de Verdi\`ere, Multiplicit\'es des valeurs propres

Y. Colin de Verdi\`ere, Multiplicit\'es des valeurs propres. L aplaciens discrets et laplaciens continus , Rend. Mat. Appl. (7) 13 (1993), no. 3, 433--460. 1276254

work page 1993
[4]

Cioab a and M

Sebastian M. Cioab a and M. Ram Murty, A first course in graph theory and combinatorics, Texts and Readings in Mathematics, vol. 55, Hindustan Book Agency, New Delhi; Springer, Singapore, [2022] 2022, Second edition [of 2524249]. 4472230

work page 2022
[5]

Brian Davies, Graham M

E. Brian Davies, Graham M. L. Gladwell, Josef Leydold, and Peter F. Stadler, Discrete nodal domain theorems, Linear Algebra Appl. 336 (2001), 51--60. 1855391

work page 2001
[6]

Duval and Victor Reiner, Perron- F robenius type results and discrete versions of nodal domain theorems , Linear Algebra Appl

Art M. Duval and Victor Reiner, Perron- F robenius type results and discrete versions of nodal domain theorems , Linear Algebra Appl. 294 (1999), no. 1-3, 259--268. 1693975

work page 1999
[7]

Joel Friedman, Some geometric aspects of graphs and their eigenfunctions, Duke Math. J. 69 (1993), no. 3, 487--525. 94b:05134

work page 1993
[8]

G. M. L. Gladwell and H. Zhu, Courant's nodal line theorem and its discrete counterparts, Quart. J. Mech. Appl. Math. 55 (2002), no. 1, 1--15. 1883285

work page 2002
[9]

Tosio Kato, A short introduction to perturbation theory for linear operators, Springer-Verlag, New York-Berlin, 1982. 678094

work page 1982
[10]

Saikat Maji, Mayukh Mukherjee, and Soumyajit Saha, Nodal domains on surfaces under perturbation: Upper semicontinuity, courant-sharpness, and boundary intersections, 2026, Available as https://arxiv.org/abs/2507.04928

work page internal anchor Pith review Pith/arXiv arXiv 2026
[11]

Theo McKenzie and John Urschel, Nodal decompositions of a symmetric matrix, Int. Math. Res. Not. IMRN (2024), no. 7, 6224--6258. 4728733

work page 2024
[12]

Powers, Graph partitioning by eigenvectors, Linear Algebra Appl

David L. Powers, Graph partitioning by eigenvectors, Linear Algebra Appl. 101 (1988), 121--133. 941300

work page 1988
[13]

Uhlenbeck, Generic properties of eigenfunctions, Amer

K. Uhlenbeck, Generic properties of eigenfunctions, Amer. J. Math. 98 (1976), no. 4, 1059--1078. 464332

work page 1976
[14]

Urschel, Nodal decompositions of graphs, Linear Algebra Appl

John C. Urschel, Nodal decompositions of graphs, Linear Algebra Appl. 539 (2018), 60--71. 3739397

work page 2018