Introduction
Traditional graph theory classifies structures by properties like planarity or connectivity. This work shifts the focus to the informational cost of construction. By framing graph generation as a communication game between an instructor (Alice) and a builder (Bob), we can quantify the complexity of specific graph classes through the lens of resource constraints—instructions, memory, and randomness.
The Construction Model
The model assumes a sequential process where vertices $1, 2, \dots, n$ are added one by one. At each step $t$, Bob must decide which of the existing $t-1$ vertices to connect to the new vertex $t$. Alice provides instructions (bit strings), and Bob may utilize memory to track vertex labels or randomness to resolve ambiguities.
Resource Constraints
- Instructions: Fixed-length bit strings sent by Alice at each step.
- Memory: The ability to "label" vertices. "Perfect memory" allows labels to persist, while "fading memory" limits recall to the last $L$ vertices.
- Randomness: Using random bits when instructions are insufficient.
Graph Hierarchies and Resource Bounds
The simplest case involves 1-bit instructions and zero memory. In this scenario, Bob can only construct threshold graphs ($\mathcal{T}$). Each new vertex is either connected to all previous vertices (dominating) or none (isolated).
The Power of Memory
Introducing just one bit of memory allows Bob to partition vertices into two distinct groups. This small increase in resource availability enables the construction of more complex families, including complete bipartite graphs and split graphs.
As illustrated above, the connectivity of a new vertex can be determined by the memory labels of the target vertices. This mechanism allows for the differentiation of vertex sets that would otherwise be indistinguishable to a memoryless builder.
Taxonomy of Constructible Families
By varying the mapping of instructions to vertex sets (determined by memory states), a wide range of graph classes emerges. The following table summarizes the families constructible with 1-bit instructions and 1-bit memory.
As shown, combinations like $(0 \to 1)(1 \to 0)$ lead to complete bipartite graphs ($K_{l,m}$), while other mappings produce disjoint cliques ($K_l \uplus K_m$) or threshold graphs ($\mathcal{T}$).
Advanced Constraints: Fading Memory and Randomness
Fading memory, where only the most recent $L$ vertices are remembered, provides a middle ground. With $L=2$, Bob can construct linear forests—collections of paths—which are impossible to build without memory. This highlights how temporal locality in memory can still yield non-trivial global structures.
Randomness is found to be an expensive substitute for instructions. Constructing a specific graph using only randomness requires $\Theta(n^2)$ bits, asymptotically equivalent to generating a completely random Erdős-Rényi graph. This suggests that specific structural information is highly valuable compared to undirected noise.
Conclusion
This resource-based approach provides a new way to categorize graph complexity. While threshold graphs represent the "atoms" of this hierarchy, the transition to more complex structures like trees or general perfect graphs requires quantifiable increases in memory and instruction bandwidth. Future work remains to fully map this hierarchy and explore the implications of computationally bounded builders.
Summary updated