arxiv: 2604.20042 · v1 · submitted 2026-04-21 · 🧮 math.CO · cs.DM

Recognition: unknown

On Threshold Compatibility Graphs

Sheikh Azizul Hakim , Md. Shamsuzzoha Bayzid

Authors on Pith no claims yet

Pith reviewed 2026-05-10 01:27 UTC · model grok-4.3

classification 🧮 math.CO cs.DM

keywords threshold-PCGpairwise compatibility graphsgraph classesasymptotic densityexpressive powerk-AND-PCGobstruction setsinterval-PCG

0 comments

The pith

Every graph on n vertices is a (n,t)-threshold-PCG for every 1 ≤ t ≤ n, while for any fixed (k,t) the class is asymptotically rare among all graphs.

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

The paper defines (k,t)-threshold-PCGs by requiring a vertex pair to be adjacent when at least t out of k underlying pairwise compatibility graphs accept it. It establishes that setting k equal to n lets the model produce every possible graph on n vertices for any choice of threshold t. For any fixed values of k and t the representable graphs form a vanishing fraction of all graphs as n grows. This density result yields explicit separations from earlier models such as k-interval-PCGs and shows that the k-AND-PCG hierarchy is strict while k-AND-PCGs fail to be closed under complement.

Core claim

We introduce (k,t)-threshold-PCGs, a threshold-based framework that unifies several generalized notions of pairwise compatibility graphs: adjacency is determined by whether at least t among k underlying PCG predicates accept the vertex pair. We show that every graph on n vertices is a (n,t)-threshold-PCG for every 1 ≤ t ≤ n. We prove that for every fixed pair (k,t) the class of (k,t)-threshold-PCGs is asymptotically rare among all graphs. As a consequence we obtain sharp separations from previously studied models, including a strict expressive gap relative to k-interval-PCGs. We also study explicit obstruction families through incidence graphs and derive additional structural consequences, e

What carries the argument

The (k,t)-threshold predicate, which counts how many of k independent pairwise compatibility relations accept a vertex pair and declares adjacency precisely when the count is at least t.

If this is right

Every graph on n vertices admits a representation using exactly n pairwise compatibility graphs and any chosen threshold t.
For any fixed k and t the proportion of (k,t)-threshold-PCGs among all n-vertex graphs tends to zero.
k-interval-PCGs form a proper subclass of the threshold model, establishing a strict expressive gap.
The family of k-AND-PCGs forms a strict hierarchy under increasing k.
k-AND-PCGs are not closed under taking complements.

Where Pith is reading between the lines

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

Representing an arbitrary graph therefore requires the number of PCG factors to grow with n.
The strict gap implies that interval-based generalizations remain strictly weaker than the threshold model even when the number of factors is allowed to increase but stays bounded.
Obstruction families based on incidence graphs may be used to certify that a given graph lies outside the (k,t) class for small fixed parameters.

Load-bearing premise

The k underlying PCG predicates can be chosen independently so that their threshold combination produces a genuine generalization without hidden dependencies among the tree metrics that would collapse the claimed separations or universality.

What would settle it

An n-vertex graph that cannot be realized as any (n,t)-threshold-PCG for some t between 1 and n, or an explicit lower bound showing that the number of distinct (k,t)-threshold-PCGs for fixed k and t is at least a positive constant fraction of all graphs on n vertices.

read the original abstract

Pairwise Compatibility Graphs (PCGs) form a tree-metric graph class that originated in phylogeny and has since attracted sustained interest in graph theory. Several natural generalizations have been proposed in order to overcome the expressive limitations of classical PCGs, including $k$-interval-PCGs, $k$-OR-PCGs, and $k$-AND-PCGs. In this paper, we introduce $(k,t)$-threshold-PCGs, a threshold-based framework that unifies these generalized notions: adjacency is determined by whether at least $t$ among $k$ underlying PCG predicates accept the vertex pair. We investigate the expressive power of this model from both constructive and asymptotic viewpoints. On the positive side, we show that every graph on $n$ vertices is a $(n,t)$-threshold-PCG for every $1 \le t \le n$. On the negative side, we prove that for every fixed pair $(k,t)$, the class of $(k,t)$-threshold-PCGs is asymptotically rare among all graphs. As a consequence, we obtain sharp separations from previously studied models, including a strict expressive gap relative to $k$-interval-PCGs. We also study explicit obstruction families through incidence graphs and derive additional structural consequences for the conjunction case, including the strictness of the $k$-AND-PCG hierarchy and the failure of closure under complement.

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 defines (k,t)-threshold-PCGs to unify several PCG generalizations, proves every n-vertex graph arises when k=n, and shows fixed (k,t) versions are asymptotically rare with a strict gap from k-interval-PCGs.

read the letter

The main takeaway is that (k,t)-threshold-PCGs let you combine k separate PCG conditions and declare an edge when at least t of them hold. This setup recovers the k-OR case at t=1 and the k-AND case at t=k, and the authors position it as a common generalization that also relates to k-interval-PCGs. They prove two main results: every graph on n vertices is a (n,t)-threshold-PCG for any t in 1 to n, and for any fixed k and t the class contains only 2^{o(n^2)} graphs on n vertices. The second fact immediately gives a separation from k-interval-PCGs. They add some structural work on obstruction families via incidence graphs and show the k-AND hierarchy is strict and not closed under complement. These are concrete new statements beyond routine extensions of the cited PCG literature. The framework is presented cleanly and the positive-negative pair of results is a reasonable way to map the expressive limits. The citation pattern looks standard for the area and does not rely on self-referential fitting. The soft spots are in the missing details. The abstract states that proofs exist but does not sketch the tree-and-interval constructions needed for the universality claim or the counting argument behind the rarity bound. Without those steps it is hard to confirm that the threshold combination stays well-defined and that no hidden metric dependencies collapse the claimed separation. The asymptotic claim also needs an explicit upper bound on the number of distinct graphs obtainable from k trees to be fully convincing. This paper is for graph theorists who already work on tree-metric graph classes or phylogenetic compatibility problems. A reader who cares about the hierarchy of expressive power among these models will get value from the unification and the two main theorems. I would send it to peer review; the new class and the stated results are worth a careful check once the proofs are written out.

Referee Report

0 major / 2 minor

Summary. The paper introduces (k,t)-threshold-PCGs, a model in which a graph on a vertex set is obtained by taking k independent PCG instances (each defined by a tree metric and an interval) and declaring two vertices adjacent precisely when at least t of the k predicates accept the pair. It proves that every n-vertex graph arises as an (n,t)-threshold-PCG for any 1 ≤ t ≤ n, shows that the number of distinct (k,t)-threshold-PCGs on n vertices is 2^{o(n²)} whenever k and t are fixed, and deduces strict expressive separations from k-interval-PCGs. Additional results include explicit obstruction families via incidence graphs and structural facts for the k-AND-PCG hierarchy (strictness and failure of complement-closure).

Significance. If the constructions and counting arguments are correct, the work supplies a clean unifying framework for several existing PCG generalizations and delivers both a universality result (when the number of predicates may grow with n) and a strong sparsity result (when k and t are constant). The asymptotic rarity statement together with the separation from k-interval-PCGs clarifies the expressive boundaries of tree-metric interval models. The explicit obstruction analysis and the non-closure result for the conjunction case are further contributions that strengthen the structural understanding of these classes.

minor comments (2)

The definition of a (k,t)-threshold-PCG (presumably in the preliminaries or Section 2) would be clearer if accompanied by a small concrete example showing how the threshold t is applied to k tree-metric intervals.
In the counting argument establishing asymptotic rarity, the precise bound on the number of distinct graphs (e.g., the o(n²) exponent) should be stated explicitly rather than left implicit.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work on (k,t)-threshold-PCGs and for recommending minor revision. The report does not enumerate any specific major comments requiring point-by-point rebuttal.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper defines (k,t)-threshold-PCGs as a new unification of prior PCG generalizations and establishes its main results via explicit constructions (every n-vertex graph is an (n,t)-threshold-PCG) and standard asymptotic counting arguments (fixed (k,t) yields o(2^{n^2}) graphs). These steps rely on newly introduced definitions and elementary graph-theoretic techniques rather than any self-referential fitting, parameter renaming, or load-bearing self-citation chains. No equation or claim reduces to its own inputs by construction, and the separations from k-interval-PCGs follow directly from the counting bounds without hidden dependencies.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Only the abstract is available, so the ledger is necessarily incomplete; the work relies on standard definitions of PCGs and tree metrics from prior literature plus the new threshold predicate.

axioms (1)

domain assumption Standard definitions and properties of pairwise compatibility graphs and tree metrics from the cited phylogeny and graph-theory literature.
The new model is defined by combining existing PCG predicates; the abstract assumes these background notions are already established.

invented entities (1)

(k,t)-threshold-PCG no independent evidence
purpose: A new graph class that unifies k-interval, k-OR, and k-AND-PCGs via a threshold on k underlying PCG predicates.
Explicitly introduced in the paper as the central object of study.

pith-pipeline@v0.9.0 · 5535 in / 1502 out tokens · 49510 ms · 2026-05-10T01:27:25.933753+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[1]

org/10.1007/978-3-319-55911-7_6

URL: https://doi. org/10.1007/978-3-319-55911-7_6. 2 Naveed Ahmed Azam, Aleksandar Shurbevski, and H. Nagamochi. A method for enumerating pairwise compatibility graphs with a given number of vertices.Discret. Appl. Math., 303:171– 185,

work page doi:10.1007/978-3-319-55911-7_6
[2]

3 Naveed Ahmed Azam, Aleksandar Shurbevski, and H

URL:https://doi.org/10.1016/j.dam.2020.08.016. 3 Naveed Ahmed Azam, Aleksandar Shurbevski, and H. Nagamochi. On the enumeration of minimal non-pairwise compatibility graphs.Journal of Combinatorial Optimization, 44:2871– 2892,

work page doi:10.1016/j.dam.2020.08.016 2020
[3]

URL:https://doi.org/10.1007/s10878-021-00799-x. 4 P. Baiocchi, T. Calamoneri, A. Monti, and R. Petreschi. Some classes of graphs that are not pcgs

work page doi:10.1007/s10878-021-00799-x
[4]

URL:https://doi.org/10.1007/978-3-319-94667-2_4. 6 T. Calamoneri, Dario Frascaria, and B. Sinaimeri. All graphs with at most seven ver- tices are pairwise compatibility graphs.Comput. J., 56:882–886,

work page doi:10.1007/978-3-319-94667-2_4
[5]

URL:https://doi.org/10.46298/fi.12237. 8 T. Calamoneri, A. Monti, and B. Sinaimeri. On generalizations of pairwise compatibility graphs.Discret. Math. Theor. Comput. Sci., 26,

work page doi:10.46298/fi.12237
[6]

Backpropagation through time and the brain.Current Opinion in Neurobiology, 55:82–89, 2019

URL: https://doi.org/10.1016/j. endm.2013.10.006. 10 T. Calamoneri and R. Petreschi. On pairwise compatibility graphs having dilworth number two. Theor. Comput. Sci., 524:34–40,

work page doi:10.1016/j 2013
[7]

URL:https://doi.org/10.1016/j.tcs.2013.12.015. 11 T. Calamoneri, R. Petreschi, and B. Sinaimeri. On relaxing the constraints in pairwise compatibility graphs. InWorkshop on Algorithms and Computation,

work page doi:10.1016/j.tcs.2013.12.015 2013
[8]

URL: https://doi.org/10.1142/S1793830913600021. 13 T. Calamoneri and B. Sinaimeri. Pairwise compatibility graphs: A survey.SIAM Rev., 58:445–460,

work page doi:10.1142/s1793830913600021
[9]

14 Tiziana Calamoneri, Angelo Monti, and Blerina Sinaimeri.On Variants of PCGs: A Survey of Current Results and Open Problems, pages 39–59

URL:https://doi.org/10.1137/140978053. 14 Tiziana Calamoneri, Angelo Monti, and Blerina Sinaimeri.On Variants of PCGs: A Survey of Current Results and Open Problems, pages 39–59. Springer Nature Switzerland, Cham, 2025.doi:10.1007/978-3-031-91357-0_3. 15 Stephane Durocher, Debajyoti Mondal, and M. S. Rahman. On graphs that are not pcgs. In Theoretical Com...

work page doi:10.1137/140978053 2025
[10]

16 Joseph Felsenstein

URL:https://doi.org/10.1016/j.tcs.2015.01.011. 16 Joseph Felsenstein. The number of evolutionary trees.Systematic Zoology, 27(1):27–33,

work page doi:10.1016/j.tcs.2015.01.011 2015
[11]

17 Ronald L

doi:10.2307/2412804. 17 Ronald L. Graham, Donald E. Knuth, and Oren Patashnik.Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, Reading, Massachusetts, 2 edition,

work page doi:10.2307/2412804
[12]

sciencedirect.com/science/article/pii/S0020019022000412, doi:10.1016/j.ipl.2022

URL: https://www. sciencedirect.com/science/article/pii/S0020019022000412, doi:10.1016/j.ipl.2022. 106284. 19 Seemab Hayat and Naveed Ahmed Azam. A method to generate multi-interval pairwise compatibility graphs.ArXiv, abs/2410.10525,

work page doi:10.1016/j.ipl.2022 2022
[13]

URL:https://doi.org/10.1007/978-3-319-30139-6_9. 21 P. Kearney, J. Munro, and Derek Phillips. Efficient generation of uniform samples from phylogenetic trees. InWorkshop on Algorithms in Bioinformatics,

work page doi:10.1007/978-3-319-30139-6_9
[14]

org/10.1007/978-3-540-39763-2_14

URL:https://doi. org/10.1007/978-3-540-39763-2_14. 22 Max Dupré la Tour, Manuel Lafond, and Ndiamé Ndiaye. Recognizing leaf powers and pairwise compatibility graphs is np-complete. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 6166–6183. SIAM,

work page doi:10.1007/978-3-540-39763-2_14 2026
[15]

URL: https://doi.org/10.1093/comjnl%2Fbxac011. 24 M. S. Rahman and Shareef Ahmed. A survey on pairwise compatibility graphs.AKCE Int. J. Graphs Comb., 17:788–795,

work page doi:10.1093/comjnl
[16]

25 Sammi Abida Salma and Md

URL:https://doi.org/10.1016/j.akcej.2019.12.011. 25 Sammi Abida Salma and Md. Saidur Rahman. Triangle-free outerplanar 3-graphs are pairwise compatibility graphs. InWorkshop on Algorithms and Computation,

work page doi:10.1016/j.akcej.2019.12.011 2019
[17]

26Charles Semple and Mike Steel.Phylogenetics

URL: https: //doi.org/10.1007/978-3-642-28076-4_13. 26Charles Semple and Mike Steel.Phylogenetics. Oxford University Press,

work page doi:10.1007/978-3-642-28076-4_13
[18]

27 Hugh E. Warren. Lower bounds for approximation by nonlinear manifolds.Transactions of the American Mathematical Society, 133(1):167–178, 1968.doi:10.2307/1994841. 28 Mingyu Xiao and Hiroshi Nagamochi. Some reduction operations to pairwise compatibility graphs.Information Processing Letters, 153:105875,

work page doi:10.2307/1994841 1968
[19]

com/science/article/pii/S0020019019301589,doi:10.1016/j.ipl.2019.105875

URL:https://www.sciencedirect. com/science/article/pii/S0020019019301589,doi:10.1016/j.ipl.2019.105875. 29 Muhammad N. Yanhaona, Md. Shamsuzzoha Bayzid, and M. S. Rahman. Discovering pairwise compatibility graphs. InDiscret. Math. Algorithms Appl.,

work page doi:10.1016/j.ipl.2019.105875 2019
[20]

30 Thomas Zaslavsky.Facing up to Arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes, volume 1 ofMemoirs of the American Mathematical Society

URL: https: //doi.org/10.1142/S1793830910000917. 30 Thomas Zaslavsky.Facing up to Arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes, volume 1 ofMemoirs of the American Mathematical Society. American Mathematical Society, 1975.doi:10.1090/memo/0154. A Non-closure of Multi-Interval PCGs under Complement It has been posed as an open pr...

work page doi:10.1142/s1793830910000917 1975