On Threshold Pairwise Compatibility Graphs

Sheikh Azizul Hakim, Md. Shamsuzzoha Bayzid · 2026

Read On Threshold Pairwise Compatibility Graphs by Sheikh Azizul Hakim, Md. Shamsuzzoha Bayzid (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-20042.txt.

Introduction

Hakim and Bayzid introduce threshold pairwise compatibility graphs, a framework unifying several generalizations of tree-metric graph classes from phylogeny. A pair counts as adjacent when at least t of k underlying compatibility predicates accept it. Every graph on n vertices fits the framework for every t up to n, yet for fixed k and t the class is asymptotically rare among all graphs. The model separates sharply from k-interval compatibility graphs, the k-AND hierarchy is strict, and closure under complement fails.

Catalog record

CREATORSheikh Azizul Hakim, Md. Shamsuzzoha Bayzid
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50315
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.20042

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On Threshold Pairwise Compatibility Graphs Sheikh Azizul Hakim, Md. Shamsuzzoha Bayzid 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 k -interval-PCGs , k k -OR-PCGs , and k k -AND-PCGs . In this paper, we introduce ( k , t ) (k,t) -threshold-PCGs , a threshold-based framework that unifies these generalized notions: adjacency is determined by whether at least t t among k 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 n vertices is a ( n , t ) (n,t) -threshold-PCG for every 1 ≤ t ≤ n 1\leq t\leq n . On the negative side, we prove that for every fixed pair ( k , t ) (k,t) , the class of ( k , t ) (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 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 k -AND-PCG hierarchy and the failure of closure under complement. Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology, Dhaka, Bangladesh [email protected] https://orcid.org/0000-0002-3405-2402 Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology, Dhaka, Bangladesh [email protected] https://orcid.org/0000-0002-5640-0615 ccs Mathematics of computing Graph theory ccs Theory of computation Design and analysis of algorithms keywords Pairwise Compatibility Graphs, threshold graph representations, multi-interval PCGs, graph classes, tree-metric representations † † runningauthor: S. A. Hakim and M. S. Bayzid † † copyright: Sheikh Azizul Hakim and Md. Shamsuzzoha Bayzid 1 Introduction Pairwise Compatibility Graphs ( PCGs ) were introduced by Kearney, Munro, and Phillips in the context of phylogeny, where compatibility relations among taxa are modeled through distances in an underlying edge-weighted tree [ 21 ] . Over time, however, the notion has developed into a graph-theoretic representation model of independent interest. Informally, a graph is a PCG if its vertices can be associated with the leaves of an edge-weighted tree so that two vertices are adjacent exactly when their leaf-to-leaf distance lies in a prescribed interval. This definition is easy to state and geometrically appealing, but the class it defines has proved to be surprisingly subtle. A large body of work has been devoted to understanding the expressive power of PCGs . On the positive side, several nontrivial graph classes are known to admit PCG representations; for example, graphs of Dilworth number at most two are PCGs [ 11 , 12 ] , triangle-free outerplanar 3 -graphs are PCGs [ 25 ] , and further sufficient conditions are known for broader families [ 10 , 20 ] . On the negative side, the class is not universal: it was shown that not every graph is a PCG [ 29 ] , and subsequent work developed explicit obstruction families, proof techniques for non- PCG ness, and enumerative studies of minimal non- PCG graphs [ 15 , 4 , 5 , 3 ] . Surveys such as [ 24 , 13 , 14 ] document both the breadth of the area and the persistence of several basic open problems. Even at small orders, the boundary is delicate: all graphs on at most seven vertices are PCGs [ 6 ] , while more intricate behavior appears immediately beyond that range. These limitations have motivated a number of natural generalizations. One direction relaxes the single-interval requirement while retaining a common witness tree, leading to k -interval-PCG [ 1 , 19 ] . Another direction combines several PCG representations on the same vertex set by Boolean operations, giving rise to classes such as k -OR-PCG and k -AND-PCG [ 8 , 14 ] . These models enlarge the expressive scope of classical PCGs , but they have largely been studied in parallel rather than within a single framework. As a consequence, some basic comparative questions have remained poorly understood. For example, the recent literature asks for sharper separations between multi-interval and Boolean-combination models, for explicit obstruction families in low-level OR / AND classes, and for a better understanding of distinguished hard families from the multi-interval literature [ 8 , 14 ] . In this paper, we unify these directions through a threshold-based framework. Given k underlying PCG predicates, we declare a pair of vertices adjacent whenever at least t of them accept the pair. This yields the class of (k,t) -threshold-PCG s. The definition subsumes several previously studied models as special cases: ordinary PCGs correspond to (1,1) , k -OR-PCG is recovered when t=1 , and k -AND-PCG is recovered when t=k . In this sense, (k,t) -threshold-PCG s provide a single framework for studying fixed-size combinations of tree-distance graph representations. This framework leads to a clear dichotomy. If the number of constituent predicates is allowed to grow with the graph size, then the model becomes universal: every graph on n vertices is a (n,t) -threshold-PCG for every 1\leq t\leq n . In contrast, if the number of predicates is fixed, then even after allowing all thresholds, the resulting classes occupy only an asymptotically vanishing fraction of all graphs. Thus the threshold model is both expressive and structurally restrictive. Moreover, it provides a convenient setting in which several phenomena can be studied uniformly: counting arguments yield separations from multi-interval representations, incidence graphs give explicit obstruction families, and the conjunction case exhibits both a strict hierarchy and failure of complement closure. Our contributions This paper initiates the systematic study of (k,t) -threshold-PCG s. Our main contributions are as follows. • We prove a universality theorem: every graph on n vertices is a (n,t) -threshold-PCG for every 1\leq t\leq n . • We prove an asymptotic sparsity theorem: for every fixed integer k , even after allowing all thresholds t\in[k] , the union of the corresponding threshold classes has asymptotic density zero among all graphs. • We compare threshold combinations with multi-interval representations and show that (k,t) -threshold-PCG s can be substantially more expressive. In particular, if f(k)\in o(k^{2}/\log k) , then for all sufficiently large k there exists a graph that is a (k,t) -threshold-PCG but not an f(k) -interval-PCG . As a consequence, for all sufficiently large k , k\textsc{-interval-{PCG}}\subsetneq k\textsc{-OR-{PCG}}. • We develop explicit obstruction families via set-system incidence graphs. This yields concrete lower bounds for threshold representations, explicit infinite families outside low-level threshold classes, and quantitative bounds for some graph classes. • In the conjunction setting, we prove that the hierarchy of k -AND-PCG classes is strict: k\textsc{-AND-{PCG}}\subsetneq(k+1)\textsc{-AND-{PCG}}\qquad\text{for every }k\geq 1. • We also show that the classes k - AND - PCG and k -interval-PCG are not closed under complement. Taken together, these results show that threshold combinations provide a robust and meaningful extension of the PCG paradigm. They are expressive enough to unify and strengthen several known variants, yet rigid enough to admit strong counting

Read the complete text