Counting False-Twin Witnesses in Induced Subgraphs: An Exact Identity, a Two-Constraint Entropy Rate, and a Plateau
- 1Department of Mathematics, Kuwait College of Science and Technology, Doha District, Safat 13133, Kuwait
Abstract
Given a fixed non-adjacent pair of vertices, suppose we know how many induced subgraphs make the pair look like false twins, allowing up to a prescribed number of disagreements. Can this local witness count recover how strongly the two vertices agree in the full graph? We study this inverse question. In the main deterministic setting, the graph size, the induced-subgraph size, the allowed number of disagreements and the exhaustive witness count are treated as known, while the global adjacency-agreement count is unknown. We first prove an exact counting formula and use it to determine when the unknown agreement count can be recovered uniquely and when saturation causes information to be lost. We then study the regime in which the subgraph size and the allowed number of disagreements grow proportionally with the graph. A method-of-types argument gives the exponential growth rate up to an O(logN) error. The resulting rate develops a plateau before the exact finite count itself becomes constant. Thus there is a range in which different global agreement levels are still distinguishable at finite size but are no longer distinguishable at exponential scale. In the exact-witness case we also obtain sharp asymptotic and finite-size stability estimates. Numerical calculations illustrate the finite-size behavior, and strongly regular graphs and the dense stochastic block model are discussed as examples.
Related
- Large induced subgraphs with k vertices of maximum degree
- A proof of Vince's conjecture on the average order of connected induced subgraphs
- A Note on Vertex-Critical Induced Subgraphs of Shift Graphs
- A Short Combinatorial Proof of the Pons-Batle Identity for Counting Tree-Child Networks
- On extending induced subgraphs
BibTeX
@article{nabavi2026counting,
title = {{Counting False-Twin Witnesses in Induced Subgraphs: An Exact Identity, a Two-Constraint Entropy Rate, and a Plateau}},
author = {Ali Nabavi and Rabih Ghostine},
journal = {Mathematics},
year = {2026},
month = oct,
doi = {10.3390/math14203805},
url = {https://www.mdpi.com/2227-7390/14/20/3805},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Counting False-Twin Witnesses in Induced Subgraphs: An Exact Identity, a Two-Constraint Entropy Rate, and a Plateau
AU - Ali Nabavi
AU - Rabih Ghostine
PY - 2026
DA - 2026/10/20
JO - Mathematics
DO - 10.3390/math14203805
UR - https://www.mdpi.com/2227-7390/14/20/3805
AB - Given a fixed non-adjacent pair of vertices, suppose we know how many induced subgraphs make the pair look like false twins, allowing up to a prescribed number of disagreements. Can this local witness count recover how strongly the two vertices agree in the full graph? We study this inverse question. In the main deterministic setting, the graph size, the induced-subgraph size, the allowed number of disagreements and the exhaustive witness count are treated as known, while the global adjacency-agreement count is unknown. We first prove an exact counting formula and use it to determine when the unknown agreement count can be recovered uniquely and when saturation causes information to be lost. We then study the regime in which the subgraph size and the allowed number of disagreements grow proportionally with the graph. A method-of-types argument gives the exponential growth rate up to an O(logN) error. The resulting rate develops a plateau before the exact finite count itself becomes constant. Thus there is a range in which different global agreement levels are still distinguishable at finite size but are no longer distinguishable at exponential scale. In the exact-witness case we also obtain sharp asymptotic and finite-size stability estimates. Numerical calculations illustrate the finite-size behavior, and strongly regular graphs and the dense stochastic block model are discussed as examples.
SN - 2227-7390
ER -