pith. sign in

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

Base Modulus for Matroid Truncation, Strength, and Fractional Arboricity

Huy Truong , Pietro Poggi-Corradini This is my paper

Pith reviewed 2026-05-10 14:54 UTC · model grok-4.3

classification 🧮 math.CO
keywords matroid truncationuniversal densityprincipal partitionp-modulusstrengthfractional arboricityKullback-Leibler divergence
0
0 comments X

The pith

The universal density for bases of a matroid determines the principal partition of every truncation.

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

The paper shows how the universal density of the bases extends to every truncation of a given matroid. This extension is equivalent to determining the principal partition for each truncation. The result sits inside the p-modulus framework on the family of all bases, which already recovers strength, fractional arboricity, and the lexicographical base in polymatroids. A separate characterization of the same density is given in terms of Kullback-Leibler divergence, and the paper examines strictly homogeneous matroids along with the probability mass functions on bases that achieve the density in simple cases.

Core claim

We first provide the universal density of every truncation of a given matroid; equivalently, we determine the principal partition for every matroid truncation. We give a new characterization of the universal density using the Kullback-Leibler divergence. We study strictly homogeneous matroids and offer several insights related to strength, fractional arboricity, and the set of probability mass functions for bases that induce the universal density in a simple case.

What carries the argument

Universal density η* arising from p-modulus on the family of all bases of the matroid, which recovers the lexicographical base in polymatroids.

Load-bearing premise

The p-modulus framework and the associated universal density remain well-defined and unique for every truncation of the original matroid.

What would settle it

Direct computation of the principal partition on a concrete truncated matroid that fails to match the density obtained by applying the derived formula to the original matroid.

Figures

Figures reproduced from arXiv: 2604.11946 by Huy Truong, Pietro Poggi-Corradini.

Figure 1
Figure 1. Figure 1: A graphic matroid with 36 vertices and 84 edges where edges are styled [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
read the original abstract

In [27], we provided results on the $p$-modulus of the family of all bases of matroids and showed that it recovers various concepts in matroid theory, including strength, fractional arboricity, and principal partitions. In particular, the unique optimal density $\eta^*$ that arises for $p$-modulus, which we will refer to as universal density from now on, was shown to recover the concept of lexicographical base in polymatroids. Since truncation is a fundamental operation in matroid theory, it is natural to ask how the universal density behaves under matroid truncation. In this paper, we first provide the universal density of every truncation of a given matroid; equivalently, we determine the principal partition for every matroid truncation. Next, we give a new characterization of the universal density using the Kullback--Leibler divergence. Furthermore, we study the notion of strictly homogeneous matroids, generalizing the corresponding notion in graphs from [6]. We also offer several insights related to strength, fractional arboricity, and give the set of probability mass functions (pmfs) for bases that induce the universal density in a simple case. Finally, this paper also addresses two optimization problems for graph structures, particularly those involving edge-disjoint spanning trees and forest edge-coverings.

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 / 4 minor

Summary. The paper extends the authors' prior p-modulus framework for matroid bases to truncations. It claims to give an explicit formula for the universal density (equivalently, the principal partition) of every truncation of a given matroid via a rank-adjustment rule on the original principal partition blocks. It further provides a Kullback-Leibler divergence characterization of the universal density, introduces and studies strictly homogeneous matroids (generalizing a graph notion), supplies insights on strength and fractional arboricity, describes certain base pmfs inducing the universal density, and treats two graph optimization problems on edge-disjoint spanning trees and forest edge-coverings.

Significance. If the derivations hold, the manuscript supplies a concrete, computable description of how universal density and principal partitions transform under truncation, a fundamental matroid operation. This removes the need to recompute the modulus minimization from scratch for each truncation and preserves uniqueness via strict convexity of the truncated base family. The KL characterization supplies an alternative variational view that may connect to probabilistic or information-theoretic techniques. The generalization of strictly homogeneous matroids and the explicit pmf description are natural extensions with potential for further applications. The graph optimization sections tie the abstract theory back to concrete combinatorial problems.

minor comments (4)
  1. [§3] §3: The rank-adjustment rule for obtaining the truncated density vector from the original principal partition blocks is stated clearly, but an explicit verification that the truncated base family remains a matroid base family (so that the modulus functional stays strictly convex) would strengthen the uniqueness claim.
  2. [§4] §4: The KL-divergence characterization is derived from the same variational problem; a short worked example (e.g., truncation of a uniform matroid) would make the equivalence and preservation of uniqueness more transparent to readers.
  3. [Abstract] Abstract and §1: The phrase 'several insights related to strength, fractional arboricity' is vague; listing the specific new statements or corollaries in one sentence would improve readability.
  4. [Notation] Notation: The symbol η* for the universal density is used throughout, but its dependence on the truncation parameter k is not always indicated in displayed equations; adding a subscript or explicit dependence would reduce ambiguity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, including the summary of our contributions on universal density for matroid truncations, the KL divergence characterization, strictly homogeneous matroids, and connections to strength, fractional arboricity, and graph optimization problems. We appreciate the recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper extends the p-modulus and universal density framework from the authors' prior work [27] but derives the truncation results independently. It explicitly shows that the optimal density for a truncation is obtained from the original via a rank-adjustment rule on principal partition blocks, with proofs in §§3–4 verifying that the truncated base family remains a matroid base family whose modulus is strictly convex. The KL-divergence characterization and other new results (strictly homogeneous matroids, strength/arboricity insights) follow from this derivation rather than reducing to fitted inputs or unverified self-citations. Self-citation of [27] is present for background but is not load-bearing, as the central claims are new computations with explicit verification that truncation commutes with the modulus minimization. No self-definitional, ansatz-smuggling, or renaming patterns appear.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on the standard axioms of matroid theory, the p-modulus definition from the authors' earlier work, and the existence and uniqueness of the universal density for any matroid.

axioms (2)
  • standard math Matroids satisfy the standard independence axioms (hereditary and augmentation).
    Invoked throughout as the ambient structure.
  • domain assumption The p-modulus of the family of bases is well-defined and attains a unique optimal density η*.
    Taken from the authors' prior paper [27] and used as the starting point for truncation results.

pith-pipeline@v0.9.0 · 5532 in / 1331 out tokens · 46628 ms · 2026-05-10T14:54:21.997359+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

30 extracted references · 30 canonical work pages

  1. [1]

    Modulus on graphs as a generalization of standard graph theoretic quantities

    Albin, N., Brunner, M., Perez, R., Poggi-Corradini, P., and Wiens, N. Modulus on graphs as a generalization of standard graph theoretic quantities. Conform. Geom. Dyn. 19\/ (2015), 298--317

    work page 2015

  2. [2]

    Blocking duality for p -modulus on networks and applications

    Albin, N., Clemens, J., Fernando, N., and Poggi-Corradini, P. Blocking duality for p -modulus on networks and applications. Ann. Mat. Pura Appl. (4) 198 , 3 (2019), 973--999

    work page 2019

  3. [3]

    Fairest edge usage and minimum expected overlap for random spanning trees

    Albin, N., Clemens, J., Hoare, D., Poggi-Corradini, P., Sit, B., and Tymochko, S. Fairest edge usage and minimum expected overlap for random spanning trees. Discrete Math. 344 , 5 (2021), Paper No. 112282, 24

    work page 2021

  4. [4]

    Spanning tree modulus for secure broadcast games

    Albin, N., Kottegoda, K., and Poggi-Corradini, P. Spanning tree modulus for secure broadcast games. Networks 76 , 3 (2020), 350--365

    work page 2020

  5. [5]

    An exact-arithmetic algorithm for spanning tree modulus

    Albin, N., Kottegoda, K., and Poggi-Corradini, P. An exact-arithmetic algorithm for spanning tree modulus. Networks 85 , 4 (2025), 1--13 [412--424]

    work page 2025

  6. [6]

    Minimizing the determinant of the graph L aplacian

    Albin, N., Lind, J., Melikyan, A., and Poggi-Corradini, P. Minimizing the determinant of the graph L aplacian. J. Graph Theory 110 , 3 (2025), 337--350

    work page 2025

  7. [7]

    Minimal subfamilies and the probabilistic interpretation for modulus on graphs

    Albin, N., and Poggi-Corradini, P. Minimal subfamilies and the probabilistic interpretation for modulus on graphs. J. Anal. 24 , 2 (2016), 183--208

    work page 2016

  8. [8]

    A., Grossman, J

    Catlin, P. A., Grossman, J. W., Hobbs, A. M., and Lai, H.-J. Fractional arboricity, strength, and principal partitions in graphs and matroids. Discrete Applied Mathematics 40 , 3 (1992), 285--302

    work page 1992

  9. [9]

    C., Koh, K

    Chen, C. C., Koh, K. M., and Peng, Y.-H. On the higher-order edge toughness of a graph. vol. 111. 1993, pp. 113--123. Graph theory and combinatorics (Marseille-Luminy, 1990)

    work page 1993

  10. [10]

    The higher-order edge toughness of a graph and truncated uniformly dense matroids

    Chen, Z.-H., and Lai, H.-J. The higher-order edge toughness of a graph and truncated uniformly dense matroids. J. Combin. Math. Combin. Comput. 22\/ (1996), 157--160

    work page 1996

  11. [11]

    Uniform density in matroids, matrices and graphs

    Devriendt, K., and Mulas, R. Uniform density in matroids, matrices and graphs. Australas. J. Combin. 94\/ (2026), 145--176

    work page 2026

  12. [12]

    Lehman's switching game and a theorem of tutte and nash-williams

    Edmonds, J. Lehman's switching game and a theorem of tutte and nash-williams. J. Res. Nat. Bur. Standards Sect. B 69\/ (1965), 73--77

    work page 1965

  13. [13]

    M., and Sturmfels, B

    Feichtner, E. M., and Sturmfels, B. Matroid polytopes, nested sets and B ergman fans. Port. Math. (N.S.) 62 , 4 (2005), 437--468

    work page 2005

  14. [14]

    Lexicographically optimal base of a polymatroid with respect to a weight vector

    Fujishige, S. Lexicographically optimal base of a polymatroid with respect to a weight vector. Mathematics of Operations Research 5 , 2 (1980), 186--196

    work page 1980

  15. [15]

    Theory of principal partitions revisited

    Fujishige, S. Theory of principal partitions revisited. Research Trends in Combinatorial Optimization: Bonn 2008\/ (2009), 127--162

    work page 2008

  16. [16]

    Fulkerson, D. R. Blocking polyhedra. In Graph T heory and its A pplications ( P roc. A dvanced S em., M ath. R esearch C enter, U niv. of W isconsin, M adison, W is., 1969)\/ (1970), Academic Press, New York, pp. 93--112

    work page 1969

  17. [17]

    Characterizations of arboricity of graphs

    Haas, R. Characterizations of arboricity of graphs. Ars Combinatoria 63\/ (2002), 129--138

    work page 2002

  18. [18]

    Ordering of the elements of a matroid such that its consecutive w elements are independent

    Kajitani, Y., Ueno, S., and Miyano, H. Ordering of the elements of a matroid such that its consecutive w elements are independent. In Proceedings of the F irst J apan C onference on G raph T heory and A pplications ( H akone, 1986)\/ (1988), vol. 72, pp. 187--194

    work page 1986

  19. [19]

    Reinforcing a matroid to have k disjoint bases

    Lai, H.-J., Li, P., Liang, Y., and Xu, J. Reinforcing a matroid to have k disjoint bases. Applied Mathematics 1 , 03 (2010), 244--249

    work page 2010

  20. [20]

    Characterization of removable elements with respect to having k disjoint bases in a matroid

    Li, P., Lai, H.-J., and Liang, Y. Characterization of removable elements with respect to having k disjoint bases in a matroid. Discrete Applied Mathematics 160 , 16-17 (2012), 2445--2451

    work page 2012

  21. [21]

    Reinforcing the number of disjoint spanning trees

    Liu, D., Lai, H.-J., and Chen, Z.-H. Reinforcing the number of disjoint spanning trees. Ars Combin 93\/ (2009), 113--127

    work page 2009

  22. [22]

    Nash-Williams, C. S. J. Decomposition of finite graphs into forests. Journal of the London Mathematical Society 1 , 1 (1964), 12--12

    work page 1964

  23. [23]

    Nash-Williams, C. S. J. A. Edge-disjoint spanning trees of finite graphs. J. London Math. Soc. 36\/ (1961), 445--450

    work page 1961

  24. [24]

    Pitsoulis, L. S. Topics in matroid theory . SpringerBriefs in Optimization. Springer, New York, 2014

    work page 2014

  25. [25]

    Fulkerson duality for modulus of spanning trees and partitions

    Truong, H., and Poggi-Corradini, P. Fulkerson duality for modulus of spanning trees and partitions. arXiv preprint arXiv:2306.15984\/ (2023)

    work page arXiv 2023

  26. [26]

    Matroid reinforcement and sparsification

    Truong, H., and Poggi-Corradini, P. Matroid reinforcement and sparsification. arXiv preprint arXiv:2408.00173\/ (2024)

    work page arXiv 2024

  27. [27]

    Modulus for bases of matroids

    Truong, H., and Poggi-Corradini, P. Modulus for bases of matroids. Discrete Math. 348 , 5 (2025), Paper No. 114395, 26

    work page 2025

  28. [28]

    Modulus of hypertrees

    Truong, H., and Poggi-Corradini, P. Modulus of hypertrees. arXiv preprint arXiv:2504.02289\/ (2025)

    work page arXiv 2025

  29. [29]

    Tutte, W. T. On the problem of decomposing a graph into n connected factors. J. London Math. Soc. 36\/ (1961), 221--230

    work page 1961

  30. [30]

    Cyclic orderings and cyclic arboricity of matroids

    van den Heuvel, J., and Thomass\'e, S. Cyclic orderings and cyclic arboricity of matroids. J. Combin. Theory Ser. B 102 , 3 (2012), 638--646

    work page 2012