Counting Successor-Closed Subsets of Functional Digraphs
Abstract
A functional digraph is a directed graph where each vertex has an out-degree of at most 1. We study the number of successor-closed subsets of a functional digraph, that is, subsets from which no edge leaves. We show that functional digraphs have a simple recursive formula for their corresponding generating function. Using this formula, we determine, among all functional digraphs with a fixed number of vertices and edges, the one that maximizes and the one that minimizes the number of successor-closed subsets of every size simultaneously. Somewhat unexpectedly, this extremal result yields a quantitative strengthening of the set-pairs inequality of Bollobas: rather than merely guaranteeing that some pair of a large enough family must violate the hypothesis of the theorem, we show that a uniformly random subset of the family witnesses a violation with high probability, quantitatively in terms of how far the family size exceeds the classical threshold. We further show that the same approach applies to the skew variant of Bollobas's inequality due to Hegedus and Frankl, yielding an analogous probabilistic strengthening.
Related
- Counting tangles in coverings of closed 2-orbifolds via ribbon categories
- Quantization for Palais-Smale sequences of the Liouville functional on closed surfaces
- Fast Functional Clustering via Closed-Form Covariance Updates
- Strong failures of club guessing at the successor of a regular cardinal
- The successor representation in high-risk drinking and alcohol-related contexts
BibTeX
@misc{marty2026counting,
title = {{Counting Successor-Closed Subsets of Functional Digraphs}},
author = {Mathias Marty},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.27145},
eprint = {2608.27145},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.27145},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Counting Successor-Closed Subsets of Functional Digraphs
AU - Mathias Marty
PY - 2026
DA - 2026/08/30
PB - arXiv
DO - 10.48550/arxiv.2608.27145
UR - https://arxiv.org/abs/2608.27145
AB - A functional digraph is a directed graph where each vertex has an out-degree of at most 1. We study the number of successor-closed subsets of a functional digraph, that is, subsets from which no edge leaves. We show that functional digraphs have a simple recursive formula for their corresponding generating function. Using this formula, we determine, among all functional digraphs with a fixed number of vertices and edges, the one that maximizes and the one that minimizes the number of successor-closed subsets of every size simultaneously. Somewhat unexpectedly, this extremal result yields a quantitative strengthening of the set-pairs inequality of Bollobas: rather than merely guaranteeing that some pair of a large enough family must violate the hypothesis of the theorem, we show that a uniformly random subset of the family witnesses a violation with high probability, quantitatively in terms of how far the family size exceeds the classical threshold. We further show that the same approach applies to the skew variant of Bollobas's inequality due to Hegedus and Frankl, yielding an analogous probabilistic strengthening.
ER -