Any six-vertex tree
A connected network without loops. Each of its five edges may be cut or kept, independently.
p(Tₙ) = 2ⁿ⁻¹
Combinatorics / Geometric Partition Counting
Same objects.
Different connections.
Different possibilities.
Six towns. The same six towns every time. Change the roads between them, and you change the ways they can form connected regions—from 32 to 203.
My question begins here: what does a count forget when it leaves out the relationships?
Independent research Bee Rosa Davis · April 2026 preprint · Companion strengthened October 27, 2026
A region has to hold together.
Imagine dividing these towns into service regions. Every town must belong to exactly one region. Inside each region, you must be able to travel between its towns without passing through another region.
01 / Exact enumeration · six labeled towns
Give the same towns more ways to connect.
Solid lines: roads in the network
Dotted lines: roads you could add
32
valid ways to group the towns
6 TOWNS · FIXED
5 ROADS
Five roads form a chain. Each road can be kept or cut: 2 × 2 × 2 × 2 × 2 = 32 groupings.
Edit individual roads · add or remove any connection
A pressed button means the road exists. Removing roads may disconnect the network; each region must still be connected within itself.
Why one road creates a new grouping
The possibilities are actual groupings.
Matching colors show towns in the same region. The written sets make the membership explicit. Faint dashed roads cross between regions; they are not used to connect a region internally.
In practice / Planning connected service areas
Two crews. Six sites. Which assignments actually work?
Suppose a maintenance team has six service sites and two crews. Each crew gets three sites. The planner also requires each crew’s sites to form a connected area: moving between them must not require passing through a site assigned to the other crew.
There are 10 ways to split six sites into two unlabeled groups of three. But with the chain of roads, only one meets the connectivity requirement. Close the ring and there are three. Connect every pair and all 10 work.
Teal and amber mark the two service areas. Solid colored roads connect sites within an area. Swapping the crew names does not create another plan.
What this gives a planner
A complete set of assignments that satisfy the stated connectivity and size rules. Instead of choosing a convenient-looking split and discovering it is disconnected, the planner can compare valid candidates and then evaluate travel time, workload and cost.
The useful distinction: the theorem guarantees a strict increase across all connected groupings. A particular planning constraint can filter the new ones out. Adding a shortcut from A to C to the original chain still leaves just one balanced two-crew plan. Closing A–F creates two more. The practical question is which new possibilities meet the job’s requirements.
Try the presets here, or edit individual roads above. Both views use the same network and recompute every valid assignment exactly.
02 / The stronger statement
Every new edge creates a new possibility.
Strict spanning-subgraph monotonicity. Keep the same labeled vertices. If a simple undirected graph H contains every edge of G and at least one more, then H has strictly more connected set-partitions.
E(G) ⊊ E(H) ⇒ p(G) < p(H)
- Nothing old is lost. Any group connected in G remains connected in H. Adding roads cannot disconnect it.
- Something new is gained. Choose a new edge uv. Put u and v together, and put every other vertex in a singleton block. This partition is valid in H and invalid in G: the two-vertex block has no edge in G.
- So the count strictly increases. H contains all the old valid partitions and at least one new one. No assumption that G is connected is needed.
In fact, every added edge supplies a different two-vertex-block witness. This gives the quantitative bound:
p(H) − p(G) ≥ |E(H) ∖ E(G)|
One edge can unlock many more than one grouping. Closing the six-town chain adds a single road but creates 26 new groupings. The bound guarantees an increase; it does not assert a constant increase per edge.
This companion strengthens the non-strict inclusion statement in the deposited manuscript. The argument is elementary; no claim of historical priority is made for this strengthening.
03 / Three exact landmarks
The floor, a ring, and the ceiling.
A six-vertex cycle
One loop. Two or more cut edges determine the regions; the uncut, one-region case counts once.
p(Cₙ) = 2ⁿ − n
The complete graph
Every pair has a road, so every possible set partition is connected. The count is the Bell number.
p(Kₙ) = B(n)
For any connected simple graph on n vertices, 2ⁿ⁻¹ ≤ p(G) ≤ B(n). The lower bound is attained exactly by trees; the upper bound exactly by the complete graph. A spanning tree supplies the lower bound, and strict edge addition establishes the equality cases.
Why the cycle count is 2ⁿ − n
There are 2ⁿ subsets of the cycle’s edges. Every cut set of size at least two gives a distinct partition into connected intervals. Exclude the empty cut set and the n single-edge cut sets, then restore the one-block partition once: 2ⁿ − 1 − n + 1 = 2ⁿ − n.
04 / What approaches what?
The growth rates converge. The counts do not.
The cycle’s ratio from one size to the next approaches 2, the exact growth factor for trees. In the paper, the difference from 2 is called “connection curvature”:
κₙ = p(Cₙ₊₁) / p(Cₙ) − 2 = (n − 1) / (2ⁿ − n)
This quantity is positive and tends to zero. But the cycle-to-tree count ratio tends to 2, not 1. Large cycles still have nearly twice as many connected partitions as trees of the same size.
| Vertices | Tree | Cycle | Cycle / tree | Growth-factor excess κₙ |
|---|---|---|---|---|
| 3 | 4 | 5 | 1.2500 | 0.400000 |
| 6 | 32 | 58 | 1.8125 | 0.086207 |
| 10 | 512 | 1,014 | 1.9805 | 0.008876 |
| 20 | 524,288 | 1,048,556 | 2.0000 | 0.000018 |
The companion corrects the manuscript’s phrase that the “geometric excess” over trees vanishes. What vanishes is the difference between their successive growth factors. This is a defined sequence statistic; the calculation alone does not establish curvature of a differential-geometric connection.
05 / Proof, computation, and applications
What the evidence establishes.
The exact result
The explorer enumerates all 203 set partitions of six labeled towns and tests connectivity inside each block. It uses no random sampling or fitted model.
A separate subset-recursion algorithm agrees with the enumerator on 1,099 labeled graphs with 1–5 vertices. All 5,325 possible single-edge additions strictly increase the count, with an explicit new-partition witness for each. The connected cases also satisfy the tree and complete-graph equality conditions.
06 / The paper and its mathematical setting
Keep the relationships in the count.
The quantity p(G) is the established connected-set-partition count, equivalently Q(G, 1) for the partition polynomial studied by Simon, Tittmann and Trinks. My paper places it within the geometric counting program and investigates its ordering and applications. The definitions, established identities, strengthened proof and empirical questions are distinguished here.
Davis, B. R. (2026). The Subgraph Lattice Theorem and Geometric Partition Counting. Zenodo, v1. DOI: 10.5281/zenodo.19503065.