pith. sign in

arxiv: 2312.06513 · v5 · submitted 2023-12-11 · 🧮 math.CO

Labeling regions in deformations of graphical arrangements

G\'abor Hetyei This is my paper

Pith reviewed 2026-05-24 05:24 UTC · model grok-4.3

classification 🧮 math.CO
keywords graphical arrangementshyperplane arrangementsregion labelingsweighted digraphsnegative cyclesShi arrangementsFuss-Catalan arrangementsFarkas lemma
0
0 comments X

The pith

Regions of any deformation of a graphical arrangement can be bijectively labeled by weighted digraphs whose directed cycles all have negative weight.

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

The paper establishes a bijection that assigns to each region of a deformed graphical arrangement a weighted digraph containing only negative-weight directed cycles, with bounded regions corresponding exactly to the strongly connected ones. This is achieved by applying Carver's variant of Farkas' lemma together with the Flow Decomposition Theorem to the defining inequalities of the regions. The resulting labels are then used to supply missing details in Stanley's argument for the injectivity of the Pak-Stanley labeling on the extended Shi arrangement. The same framework generalizes ceiling diagrams from the deleted Shi and Ish arrangements and supplies a new explicit labeling for the regions of the Fuss-Catalan arrangement.

Core claim

Combining Carver's variant of the Farkas' lemma with the Flow Decomposition Theorem we show that the regions of any deformation of a graphical arrangement may be bijectively labeled with a set of weighted digraphs containing directed cycles of negative weight only. Bounded regions correspond to strongly connected digraphs.

What carries the argument

The bijection from regions to weighted digraphs that contain only negative-weight directed cycles, produced by Carver's Farkas variant and flow decomposition applied to the arrangement inequalities.

If this is right

  • The Pak-Stanley labeling of the extended Shi arrangement is injective.
  • Ceiling diagrams extend to the deleted Shi and Ish arrangements.
  • A new explicit labeling exists for the regions of the Fuss-Catalan arrangement.
  • Athanasiadis-Linusson labelings count regions in any arrangement containing the extended Shi and Fuss-Catalan arrangements as special cases.

Where Pith is reading between the lines

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

  • The negative-cycle digraph labels may supply a uniform combinatorial model for comparing region counts across different deformations.
  • Strong connectivity in the labels offers a graph-theoretic criterion for boundedness that could be checked algorithmically without solving linear programs.
  • The method suggests that similar Farkas-plus-flow arguments might produce digraph labelings for regions in non-graphical arrangements whose inequalities admit a network-flow interpretation.

Load-bearing premise

Carver's variant of Farkas' lemma and the Flow Decomposition Theorem can be applied directly to the linear inequalities that define the regions of an arbitrary deformation of a graphical arrangement.

What would settle it

An explicit deformation of a small graphical arrangement together with its regions for which the proposed map to weighted digraphs is not bijective or assigns a digraph containing a non-negative cycle to some region.

Figures

Figures reproduced from arXiv: 2312.06513 by G\'abor Hetyei.

Figure 1
Figure 1. Figure 1: A shortest m-ascending cycle of length 5 the Linial arrangement A 0,2 n−1 to which Theorem 5.5, as well as [28, Theorem 8.6], are applicable. Looking at the formulas for the number of regions and the characteristic polynomial Aab n−1 in [28], counting regions in a combinatorial way promises to be easier in the cases when |a − b| ≤ 1 and a + b ≥ 2 hold for the parameters a and b. As we will see in Propositi… view at source ↗
Figure 2
Figure 2. Figure 2: A valid weighted digraph with a minimal m-ascending 4-cycle to tackle this case. As before, we may use Lemma 5.3, and after a cyclic rotation we may assume that i0 → i2 and i1 → i3 are the diagonals of finite weight present. Using the fact that the directed cycles (i0, i2, i3) and (i1, i3, i0) are not m-acyclic, the same calculation yields w(i0, i2) + w(i1, i3) ≤ −2 + w(i1, i2) − w(i3, i0). The left hand s… view at source ↗
Figure 3
Figure 3. Figure 3: An Athanasiadis-Linusson diagram β(i, j) = 2 for i < j and β(i, j) = 1 for i > j for all pairs {i, j} ⊂ {1, 2, 3, 4}. We add β(i, 5) = β(5, i) = 0 for i = 1, 2, 4, and we add β(3, 5) = 1 and β(3, 5) = 0. As in [5], for each i ∈ {1, 2, . . . , n} we define f(i) as the position of the leftmost element of the continuous component of i. We call the resulting (f(1), f(2), . . . , f(n)) the β-parking function of… view at source ↗
Figure 4
Figure 4. Figure 4: A rooted tree encoding an Athanasiadis-Linusson diagram Definition 6.8. Given an Athanasiadis-Linusson diagram, we define the parking tree representing it as follows: (1) Replace the labels j with j1, j2,. . . , jβ(j)+1, numbered left to right, so that we can distinguish the copies. (2) The copies of the labels satisfying f(j) = 1 become the children of the root 0. (3) We number the nodes in the tree level… view at source ↗
Figure 5
Figure 5. Figure 5: The weighted digraph associated to Example 7.1. This example illustrates the fact that not all weighted edges in our weighted digraphs encode facet inequalities for the corresponding regions. The m-acyclic property only ensures that each digraph encodes a nonempty region. Furthermore, different weighted digraphs assign a different weight to at least one directed edge, this difference between the implied in… view at source ↗
Figure 6
Figure 6. Figure 6: Codes labeling the regions of the Ish arrangement The labeling of the Ish arrangement in V2 is shown in [PITH_FULL_IMAGE:figures/full_fig_p037_6.png] view at source ↗
Figure 5
Figure 5. Figure 5: Introducing σ(j ′ ) = ik−1, only the weight of the edge ik−1 → ik = σ(j ′ ) → σ(1) can be nonzero, this edge is directed right to left. All other edges of i1 → · · · → ik point in the left to right direction. Hence we must have j < j′ and −ω(j ′ ) + = w(σ(j ′ ), σ(1)) ≥ w(σ(j), σ(1)) = −ω(j) +, implying ω(j) + ≥ ω(j ′ ) +. □ The coordinates of ω representing ceiling hyperplanes are underlined in [PITH_FUL… view at source ↗
Figure 7
Figure 7. Figure 7: Athanasiadis-Linusson diagram of a region in A 4,4 5 component consist of all a copies of a single j ∈ {1, 2, . . . , n} as shown in [PITH_FULL_IMAGE:figures/full_fig_p039_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: a-Catalan path corresponding to the Athanasiadis-Linusson diagram shown in [PITH_FULL_IMAGE:figures/full_fig_p040_8.png] view at source ↗
read the original abstract

Combining Carver's variant of the Farkas' lemma with the Flow Decomposition Theorem we show that the regions of any deformation of a graphical arrangement may be bijectively labeled with a set of weighted digraphs containing directed cycles of negative weight only. Bounded regions correspond to strongly connected digraphs. The study of the resulting labelings allows us to add the omitted details in Stanley's proof on the injectivity of the Pak-Stanley labeling of the regions of the extended Shi arrangement, to generalize the ceiling diagrams in the deleted Shi and Ish arrangements studied by Armstrong and Rhoades and to introduce a new labeling of the regions in the Fuss-Catalan arrangement. We also point out that Athanasiadis-Linusson labelings may be used to directly count regions in a class of arrangements properly containing the extended Shi arrangement and the Fuss-Catalan arrangement.

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

Summary. The manuscript proves that regions of arbitrary deformations of graphical arrangements admit a bijection to weighted digraphs whose directed cycles all have negative weight (with bounded regions corresponding to strongly connected digraphs), obtained by recasting the defining inequalities via Carver's variant of Farkas' lemma and applying the Flow Decomposition Theorem. It then uses the resulting labelings to supply the missing details in Stanley's argument for injectivity of the Pak-Stanley labeling on the extended Shi arrangement, to generalize the ceiling diagrams of Armstrong-Rhoades for deleted Shi and Ish arrangements, to define a new labeling on the Fuss-Catalan arrangement, and to observe that Athanasiadis-Linusson labelings directly enumerate regions in a class properly containing the extended Shi and Fuss-Catalan arrangements.

Significance. If the stated bijection holds, the work supplies a uniform combinatorial model that unifies several previously studied labelings of Shi-type arrangements and their deformations. The explicit use of two standard theorems (Carver's Farkas variant and flow decomposition) to produce the digraph labels is a strength, as is the subsequent application to complete an existing proof and to obtain new counting statements. The framework is falsifiable via direct verification on small deformations and yields concrete, checkable predictions for region counts.

minor comments (3)
  1. The abstract is dense; a single sentence separating the main bijection theorem from the three applications would improve readability for readers primarily interested in one or the other.
  2. Notation for the deformation parameters (introduced after the statement of the main theorem) should be fixed earlier, ideally in the definition of a deformed graphical arrangement, to avoid forward references when the inequality system is first written down.
  3. Figure 1 (the running example of a deformed graphical arrangement) would benefit from an explicit listing of the corresponding weighted digraphs on the right-hand side so that the bijection can be checked by inspection.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their supportive summary of the manuscript, recognition of its significance, and recommendation of minor revision. No major comments appear in the report.

Circularity Check

0 steps flagged

No circularity: derivation applies external theorems to arrangement regions

full rationale

The paper's central claim combines Carver's Farkas variant and the Flow Decomposition Theorem (both independent external results) to produce a bijection between regions of deformed graphical arrangements and certain weighted digraphs. No self-definitional equations, fitted parameters renamed as predictions, load-bearing self-citations, or ansatzes imported via prior author work appear in the abstract or described construction. The subsequent applications (completing Stanley's proof, generalizing ceiling diagrams) are consequences rather than inputs to the bijection. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof rests on two standard theorems from linear programming and network flows; no free parameters, ad-hoc axioms, or new entities are introduced in the abstract.

axioms (2)
  • standard math Carver's variant of Farkas' lemma
    Invoked in the abstract to combine with flow decomposition for the labeling.
  • standard math Flow Decomposition Theorem
    Invoked in the abstract to establish the bijection between regions and weighted digraphs.

pith-pipeline@v0.9.0 · 5667 in / 1390 out tokens · 26412 ms · 2026-05-24T05:24:24.651998+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

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

  1. [1]

    Hyperplane Arrangements and Diagonal Harmonics

    D. Armstrong, Hyperplane arrangements and diagonal harmonics, preprint (2010), arXiv:1005.1949 [math.CO]

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  2. [2]

    Armstrong, V

    D. Armstrong, V. Reiner and B. Rhoades, Parking spaces, Adv. Math. 269 (2015), 647–706

    work page 2015

  3. [3]

    Armstrong, and B

    D. Armstrong, and B. Rhoades, The Shi arrangement and the Ish arrangement, Trans. Amer. Math. Soc. 364 (2012), 1509–1528

    work page 2012

  4. [4]

    C. A. Athanasiadis, Characteristic polynomials of subspace arrangements and finite fields, Adv. Math. 122 (1996), 193–233

    work page 1996

  5. [5]

    C. A. Athanasiadis and S. Linusson, A simple bijection for the regions of the Shi arrangement of hyperplanes, Discrete Math. 204 (1999), 27–39

    work page 1999

  6. [6]

    M. Beck, A. Berrizbeitia, M. Dairyko, C. Rodriguez, A. Ruiz, S. Veeneman, Parking functions, Shi arrangements, and mixed graphs, Amer. Math. Monthly 122 (2015), 660–673

    work page 2015

  7. [7]

    Benedetti, K

    C. Benedetti, K. Knauer and J. Valencia-Porras, On lattice path matroid polytopes: alcoved triangulations and snake decompositions, preprint 2023, arXiv:2303.10458 [math.CO]

    work page arXiv 2023

  8. [8]

    Bernardi, Deformations of the braid arrangement and trees, Adv

    O. Bernardi, Deformations of the braid arrangement and trees, Adv. Math. 335 (2018), 466–518

    work page 2018

  9. [9]

    Berthom´ e, R

    P. Berthom´ e, R. Cordovil, D. Forge, V. Ventos and T. Zaslavsky, An elementary chromatic re- duction for gain graphs and special hyperplane arrangements, Electron. J. Combin. 16 (2009), no.1, Research Paper 121, 31 pp

    work page 2009

  10. [10]

    W. B. Carver, Systems of linear inequalities. Ann. of Math. (2) 23 (1922), 212–220

    work page 1922

  11. [11]

    Dermenjian and E, Tzanaki, Enumerating regions of Shi arrangements per Weyl cone,European J

    A. Dermenjian and E, Tzanaki, Enumerating regions of Shi arrangements per Weyl cone,European J. Combin. 122 (2024), Paper No. 104002, 37 pp

    work page 2024

  12. [12]

    Dorpalen-Barry and C

    G. Dorpalen-Barry and C. Stump, Shi arrangements restricted to Weyl cones, arXiv:2204.05829 [math.CO]

    work page arXiv

  13. [13]

    Drake, An Inversion Theorem for Labeled Trees and Some Limits of Areas under Lattice Paths, PhD thesis, Brandeis University, 2008

    B. Drake, An Inversion Theorem for Labeled Trees and Some Limits of Areas under Lattice Paths, PhD thesis, Brandeis University, 2008

    work page 2008

  14. [14]

    Duarte, A

    R. Duarte, A. Guedes de Oliveira, Pak-Stanley labeling of the m-Catalan hyperplane arrangement, Adv. Math. 387 (2021), Paper No. 107827, 17 pp

    work page 2021

  15. [15]

    Fl´ orez and D

    R. Fl´ orez and D. Forge, Activity from matroids to rooted trees and beyond, J. Combin. Theory Ser. A 198 (2023), Paper No. 105755, 21 pp

    work page 2023

  16. [16]

    Forge and T

    D. Forge and T. Zaslavsky, Lattice point counts for the Shi arrangement and other affinographic hyperplane arrangements, J. Combin. Theory Ser. A 114 (2007), 97–109

    work page 2007

  17. [17]

    Gallai, Maximum-minimum S¨ atze ¨ uber Graphen,Acta Math

    T. Gallai, Maximum-minimum S¨ atze ¨ uber Graphen,Acta Math. Acad. Sci. Hungar. 9 (1958), 395–434

    work page 1958

  18. [18]

    I. M. Gessel, S. T. Griffin and V. Tewari, Labeled binary trees, subarrangements of the Catalan arrangements, and Schur positivity, Adv. Math. 356 (2019), 106814, 67 pp

    work page 2019

  19. [19]

    Concrete mathematics. A foundation for computer science, Second Edition,

    R. Graham, D. E. Knuth and O. Patashnik, “Concrete mathematics. A foundation for computer science, Second Edition,” Addison–Wesley Publishing Company, Reading, MA, 1994

    work page 1994

  20. [20]

    Hetyei, Alternation acyclic tournaments, European J

    G. Hetyei, Alternation acyclic tournaments, European J. Combin. 81 (2019), 1–21. LABELING REGIONS IN DEFORMATIONS OF GRAPHICAL ARRANGEMENTS 45

    work page 2019

  21. [21]

    Hopkins and D

    S. Hopkins and D. Perkinson, Bigraphical arrangements, Trans. Amer. Math. Soc. 368 (2016), 709–725

    work page 2016

  22. [22]

    Hopkins and D

    S. Hopkins and D. Perkinson, Orientations, semiorders, arrangements, and parking functions, Electron. J. Combin. 19 (2012), no.4, Paper 8, 31 pp

    work page 2012

  23. [23]

    L. H. Kalikow, Symmetries in trees and parking functions, LaCIM 2000 Conference on Combina- torics, Computer Science and Applications (Montreal, QC) Discrete Math. 256 (2002), 719–741

    work page 2000

  24. [24]

    Korte and J

    B. Korte and J. Vygen, Combinatorial optimization, Theory and algorithms, Sixth edition Algo- rithms Combin. , 21 Springer, Berlin, 2018. xxi+698 pp

    work page 2018

  25. [25]

    Lam, and A

    T. Lam, and A. Postnikov, Alcoved polytopes. I, Discrete Comput. Geom. 38 (2007), 453–478

    work page 2007

  26. [26]

    Lam and A

    T. Lam and A. Postnikov, Alcoved polytopes II, in: Lie groups, geometry, and representation theory, 253–272, Progr. Math., 326 Birkh¨ auser/Springer, Cham, 2018

    work page 2018

  27. [27]

    Mazin, Multigraph hyperplane arrangements and parking functions, Ann

    M. Mazin, Multigraph hyperplane arrangements and parking functions, Ann. Comb. 21 (2017), 653–661

    work page 2017

  28. [28]

    Postnikov and R

    A. Postnikov and R. P. Stanley, Deformations of Coxeter hyperplane arrangements, J. Combin. Theory Ser. A 91 (2000), 544–97

    work page 2000

  29. [29]

    Roos, Linear Optimization: Theorems of the Alternative, In: Floudas, C., Pardalos, P

    K. Roos, Linear Optimization: Theorems of the Alternative, In: Floudas, C., Pardalos, P. (eds) Encyclopedia of Optimization. Springer, Boston, MA. https://doi.org/10.1007/ 978-0-387-74759-0_334

    work page

  30. [30]

    B. E. Sagan, Combinatorics: the art of counting, Grad. Stud. Math., 210 American Mathematical Society, Providence, RI, [2020], ©2020. xix+304 pp

    work page 2020

  31. [31]

    Scott and P

    D. Scott and P. Suppes, Foundational aspects of theories of measurement, J. Symbolic Logic 23 (1958), 113–128

    work page 1958

  32. [32]

    J. Y. Shi, Sign types corresponding to an affine Weyl group, J. London Math. Soc. (2) 35 (1987), 56–74

    work page 1987

  33. [33]

    R. P. Stanley, Hyperplane arrangements, interval orders, and trees, Proc. Nat. Acad. Sci. U.S.A. 93 (1996), 2620–2625

    work page 1996

  34. [34]

    R. P. Stanley, Hyperplane arrangements, parking functions and tree inversions, in: Mathemati- cal essays in honor of Gian-Carlo Rota (Cambridge, MA, 1996), 359–375. Progr. Math., 161 Birkh¨ auser Boston, Inc., Boston, MA, 1998

    work page 1996

  35. [35]

    R. P. Stanley, An introduction to hyperplane arrangements, Geometric combinatorics, 389–496. IAS/Park City Math. Ser., 13, American Mathematical Society, Providence, RI, 2007

    work page 2007

  36. [36]

    R. P. Stanley, Enumerative combinatorics, Volume 1, Second edition, Cambridge Stud. Adv. Math., 49 Cambridge University Press, Cambridge, 2012. xiv+626 pp

    work page 2012

  37. [37]

    Tewari, Gessel polynomials, rooks, and extended Linial arrangements, J

    V. Tewari, Gessel polynomials, rooks, and extended Linial arrangements, J. Combin. Theory Ser. A 163 (2019), 98–117

    work page 2019

  38. [38]

    Whitney, A logical expansion in mathematics, Bull

    H. Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc. 38(1932), 572–579

    work page 1932

  39. [39]

    Zaslavsky, Facing up to arrangements: face-count formulas for partitions of space by hyper- planes, Mem

    T. Zaslavsky, Facing up to arrangements: face-count formulas for partitions of space by hyper- planes, Mem. Amer. Math. Soc. 1 (1975), issue 1, no. 154, vii+102 pp

    work page 1975

  40. [40]

    Zaslavsky, Perpendicular dissections of space, Discrete Comput

    T. Zaslavsky, Perpendicular dissections of space, Discrete Comput. Geom. 27 (2002), 303–351. Department of Mathematics and Statistics, UNC Charlotte, Charlotte NC 28223-

    work page 2002

  41. [41]

    WWW: http://webpages.uncc.edu/ghetyei/

    work page