Abstract
It is easy to assume that more ordering constraints leave fewer orderings. This paper counts all directed acyclic graphs on $6$ vertices and finds that the number of orderings is not set by the number of constraints. No new theorem or law is claimed.
First, the number of orderings is fixed at the two ends: $720$ with no edges and $1$ for a single chain, both confirmed by enumeration (Section 2).
Second, and this is the core. With the same number of edges, the number of orderings scatters widely: over the $3003$ graphs with $5$ edges, it takes $39$ values from $1$ to $120$ (Section 2).
Third, fixing the number of comparable pairs does not set it either: fixing the pairs, counted through transitivity, at $8$ still leaves $14$ to $48$ orderings, a factor of $\mathbf{3.428571}$ (Section 3).
Fourth, edges implied by transitivity do not reduce the orderings: adding $0\to5$ to the chain $0\to1\to\dots\to5$ leaves $1$ ordering; only the edge count rises (Section 3).
Fifth, the counts were obtained two ways and agree: adding placeable vertices one at a time and trying all $720$ permutations agreed on $400$ randomly chosen graphs (Section 2).
Sixth, the separator is whether one counts the edges or the number of answers they leave: the lower bound on the comparisons still needed is $\log_2$ of the number of orderings, which ranges from $0$ to $\mathbf{6.906891}$ even with $5$ edges (Section 4).
Keywords: topological sort, directed acyclic graph, linear extension, transitive closure, lower bound on comparisons.
Scope (what is not claimed)
No new theorem or law is claimed: that a directed acyclic graph has orderings respecting its arrows, their number (the number of linear extensions), and that edges implied by transitivity do not change the order, are all known. Algorithmic speed is not discussed: fast ways to count orderings, or how hard that is, are not entered. Real processes are not treated: scheduling of tasks or course prerequisites is not the subject. Size is not generalised: graphs on $7$ or more vertices were not counted, and only graphs with edges from smaller to larger labels were counted. Relation to earlier papers: Paper 843 showed that the lower bound on comparisons comes from the number of answers, not from the input. This paper stands beside it. There the number of answers was $n!$. Here, when the order is partly known, we count that the number of answers left is not set by the number of edges. What is added is counting the orderings of all $32768$ graphs, measuring $39$ values with $5$ edges, measuring a factor of $3.428571$ even with comparable pairs fixed, and placing the separator on edge count versus answers left.
1. Notation and the Question
Setting: on vertices $0,1,\dots,5$, any set of edges from smaller to larger labels is drawn. Each of the resulting $2^{15}=32768$ graphs is a directed acyclic graph. The number of orderings $e(G)$ is the number of orderings in which $a$ comes before $b$ for every edge $a\to b$.
$$e(G)=\#\{\pi\in S_6:\ a\to b\in G\Rightarrow \pi^{-1}(a)<\pi^{-1}(b)\},\qquad \text{lower bound on comparisons}=\log_2 e(G)$$The number of orderings was counted with the set of placed vertices as the state, adding one vertex at a time whose required predecessors were all placed. The number of comparable pairs includes pairs implied by transitivity (the edges of the transitive closure).
Question: if the number of edges is the same, is the number of orderings about the same?
2. Counting by Number of Edges
Computation 2.1: for each number of edges, the minimum, maximum and number of distinct values of the orderings were counted.
| edges | graphs | min | max | distinct values |
|---|---|---|---|---|
| $0$ | $1$ | $720$ | $720$ | $1$ |
| $1$ | $15$ | $360$ | $360$ | $1$ |
| $3$ | $455$ | $30$ | $180$ | $6$ |
| $5$ | $3003$ | $1$ | $120$ | $39$ |
| $7$ | $6435$ | $1$ | $54$ | $37$ |
| $10$ | $3003$ | $1$ | $18$ | $16$ |
| $15$ | $1$ | $1$ | $1$ | $1$ |
Observation 2.2 this is the core. With the same number of edges, the number of orderings scatters widely. With $5$ edges, a chain gives $1$ ordering and edges from one vertex to the other five give $120$, with $39$ values in between: from $5$ edges up to $15$, the minimum was $1$ for every count. Whether added edges settle the order depends not on how many there are but on where they are placed.
Observation 2.3 the counts were obtained two ways and agree. The vertex-by-vertex count was compared with trying all $720$ permutations on $400$ randomly chosen graphs: all agreed. $720$ with no edges and $1$ for the chain were also confirmed.
3. Fixing the Number of Comparable Pairs
Computation 3.1: for each number of comparable pairs, counted through transitivity, the orderings were counted.
| comparable pairs | min | max | distinct values |
|---|---|---|---|
| $2$ | $180$ | $240$ | $2$ |
| $5$ | $40$ | $120$ | $11$ |
| $8$ | $14$ | $48$ | $16$ |
| $12$ | $4$ | $8$ | $4$ |
| $14$ | $2$ | $2$ | $1$ |
Observation 3.2 fixing the comparable pairs does not set the number of orderings. With $8$ pairs, it still ranges from $14$ to $48$, a factor of $3.428571$: the scatter is smaller than by edge count, but knowing the same number of pairs, which pairs are known still changes what is left.
Observation 3.3 edges implied by transitivity do not reduce the orderings. Adding $0\to5$ to the chain $0\to1\to2\to3\to4\to5$ left $1$ ordering: the edge count rose from $5$ to $6$ but no new order was added. This is one reason the edge count does not set the orderings.
4. The Separator
Observation 4.1 the separator is whether one counts the edges or the number of answers they leave. The number of orderings is the number of answers left once the edges are known: the lower bound on the comparisons needed to finish is $\log_2$ of it: $9.491853$ with no edges, and from $0$ to $6.906891$ with $5$ edges. How many edges are known does not tell how many comparisons remain.
Observation 4.2 placed beside Paper 843. 843 showed that the lower bound on comparisons comes from the number of answers, not from the input. There the number of answers was $n!$. Here we count the answers left when the order is partly known, and show it is set neither by edges nor by comparable pairs.
Observation 4.3 what is not said. Fast counting methods, real schedules, and graphs on $7$ or more vertices are not treated. What is shown is that the number of orderings is not set by the number of edges.
5. Census and Closing
- number of orderings $e(G)$ (Section 1): orderings respecting the arrows.
- $720$ with no edges (Computation 2.1): $6!$.
- $1$ for a chain (Computation 2.1): fully settled.
- $1$ to $120$ with $5$ edges (Computation 2.1): the core.
- $39$ values with $5$ edges (Computation 2.1): the scatter.
- factor $\mathbf{3.428571}$ at $8$ pairs (Computation 3.1): fixing does not settle it.
- transitive edges change nothing (Observation 3.3): still $1$.
- two counts agree (Observation 2.3): $400$ graphs.
- bound from $0$ to $\mathbf{6.906891}$ (Observation 4.1): with $5$ edges.
- edge count, or answers left (Observation 4.1): the separator; Paper 843.
Closing: The number of orderings is set neither by the number of edges nor by the number of comparable pairs. Among directed acyclic graphs on $6$ vertices, those with just $5$ edges have from $1$ to $120$ orderings, over $39$ values, because placing the edges as a chain settles the order, while placing them all from one vertex leaves most of it open. Fixing the comparable pairs, counted through transitivity, at $8$ still leaves $14$ to $48$, a factor of $3.428571$, and adding edges implied by transitivity reduces nothing: the lower bound on remaining comparisons, $\log_2$ of the orderings, ranges from $0$ to $6.906891$ with $5$ edges. Placed among the earlier papers: beside Paper 843’s “the bound comes from the number of answers”, we placed the number of answers left when the order is partly known. To be honest: only graphs on $6$ vertices with edges from smaller to larger labels were counted.
References
- Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley.
- Stanley, R. P. (2011). Enumerative Combinatorics, Volume 1 (2nd ed.). Cambridge University Press.
- Yamagishi, Y. (2026). The Lower Bound on Comparisons Comes From the Number of Answers, Not From the Input [Paper 843]. YOI: https://www.yamagishiyuuki.com/yoi/843
Reference
Yamagishi, Y. (2026). The Number of Orderings Is Set Neither by the Number of Edges Nor by the Number of Comparable Pairs [Paper 869]. YOI: https://www.yamagishiyuuki.com/yoi/869
ORCID: 0009-0006-8587-3450
PDF (English) · PDF (Japanese) · Date proof of the English PDF (OpenTimestamps .ots) · SHA256SUMS
The record page for this paper (in Japanese, with the PDFs in each language and the date proof): YOI 869. This paper is a preprint and has not been peer reviewed.