Burnings of trees and their homologies

1. Problem Statement and Context

The paper investigates the graph burning problem, a model originally introduced to simulate social and network interaction processes (e.g., the spread of information or fire). While previous studies (notably by Bonato et al.) defined burning processes allowing a vertex to be chosen as a "source" at time $t$ even if it was already burned by a previous source at time $t-1$, the authors focus on a stricter definition introduced in their prior work [12].

The Core Constraint: In the authors' framework, at any time step $t+1$, a new burning source cannot be chosen from the set of vertices already burned at time $t$. This restriction fundamentally alters the combinatorial properties of the burning process and necessitates new algebraic topological tools for analysis.

The paper aims to:

1. Establish the relationship between the burning of a general graph and the burning of its spanning trees under this strict definition.
2. Analyze the properties of burning processes specifically on trees.
3. Introduce burning homomorphisms and investigate their existence and end times.
4. Define a strong burning configuration space and the associated strong burning homology, distinguishing them from previously defined burning homologies.

2. Methodology

The authors employ a blend of graph theory and algebraic topology:

• Graph Filtrations: They utilize filtrations of induced subgraphs ($N_j$ and $U_j$) to model the temporal evolution of the burning process.
• Graph Homomorphisms: They define a "burning map" $\lambda: G \to P_T$ (where $P_T$ is a path graph representing time steps). A burning homomorphism is a specific type of map where adjacent vertices in $G$ must map to adjacent vertices in $P_T$ (i.e., $|\lambda(v) - \lambda(w)| = 1$).
• Simplicial Complexes: They construct configuration spaces where vertices represent burning sources and simplices represent valid burning sequences.
• Algebraic Topology: They compute simplicial homology groups of these configuration spaces to derive topological invariants of the burning processes.

3. Key Contributions and Results

A. Relationship Between Graphs and Spanning Trees (Section 3)

• Theorem 3.2: The authors prove that for any connected graph $G$ and any valid burning sequence $S_G$, there exists a spanning tree $T \subset G$ such that $S_G$ is also a valid burning sequence for $T$.
• Significance: This reduces the investigation of graph burnings to the study of tree burnings.
• Distinction: Unlike previous results (Bonato et al.), the authors' proof ensures that the partition of vertices induced by the burning sources on the tree is non-empty for every source. In the authors' strict definition, a source cannot be "covered" by a previous source, preventing empty subtrees in the decomposition.

B. Burning Homomorphisms on Trees (Section 4)

• Definition: A burning is a homomorphism if the burning map $\lambda$ preserves adjacency strictly ($|\lambda(v) - \lambda(w)| = 1$ for all edges).
• Existence:
  • Path Graphs ($P_n$): Theorem 4.2 proves that every path graph admits a burning homomorphism.
  • General Trees: Not all trees admit a burning homomorphism (Example 4.3 provides a counter-example).
  • Non-Homomorphisms: Theorem 4.4 states that any connected graph with $>2$ vertices admits a burning that is not a homomorphism.
• Distance Constraint: Lemma 4.1 establishes that for a burning homomorphism, the distance between any two sources $v_i, v_j$ must be at least 3 ($d(v_i, v_j) \ge 3$).

C. End Time Bounds for Path Graphs (Section 5)

The authors derive sharp bounds for the end time ($T$) of burning homomorphisms on path graphs $P_n$:

• Theorem 5.4: For a path graph $P_n$, the size of the burning sequence $|S_P|$ (number of sources) satisfies:
  $$\left\lfloor \frac{\sqrt{4n - 3} - 1}{2} \right\rfloor \le |S_P| \le \left\lceil \frac{n}{3} \right\rceil$$
• Corollary 5.5: Since the end time $T = |S_P| + 1$ for homomorphisms (Lemma 5.1), the bounds for $T$ are shifted by 1.
• Example 5.6: They present a family of trees ($Y_m$) that burn "worse" than path graphs, requiring a specific starting vertex to achieve the optimal burning time, highlighting the sensitivity of tree structures to source selection.

D. Digraph Structures on Burned Trees (Section 6)

• Proposition 6.2: A burning of a tree induces a natural directed graph (digraph) structure on the tree.
• Mechanism: The direction of edges is determined by the burning time $\lambda$. If $\lambda(v) < \lambda(w)$, the edge is directed $v \to w$. If $\lambda(v) = \lambda(w)$, the direction is determined by the order of the sources in the sequence.
• Result: The burning map $\lambda$ becomes a digraph homomorphism from the induced digraph on the tree to the standard path digraph.

E. Strong Burning Configuration Space and Homology (Section 7)

The authors introduce a new topological invariant:

• Strong Burning Configuration Space ($\Gamma(G)$): A simplicial complex generated by the sets of burning sources for all burning homomorphisms of $G$. This is distinct from the standard configuration space $\Delta(G)$, which includes all burnings (homomorphisms and non-homomorphisms).
• Strong Burning Homology ($H_*(BH(G), R)$): The simplicial homology of $\Gamma(G)$.
• Key Findings:
  • $\Gamma(G)$ can be empty (e.g., for graphs with odd cycles or certain trees like in Example 4.3).
  • There is a natural inclusion $\Gamma(G) \hookrightarrow \Delta(G)$, inducing homomorphisms on homology groups.
  • Example 7.9: They compute the homology for specific graphs ($Y_8$ and $P_9$), showing that strong homology can be non-trivial (e.g., $H_0 \cong \mathbb{Z}, H_1 \cong \mathbb{Z}$) even for small graphs.
  • Non-Functoriality: Remark 7.10 notes that strong homology is not functorial for general graph inclusions, though it behaves well for inclusions of trees.

4. Significance and Impact

1. Refinement of the Burning Model: By enforcing the constraint that sources cannot be pre-burned, the authors create a more rigorous model that aligns better with certain physical or logical constraints where a "new" source must be distinct from the currently affected area.
2. Topological Perspective: The paper successfully bridges discrete graph problems with algebraic topology. By defining configuration spaces and computing homology, it provides new invariants to classify graphs based on their "burnability."
3. Structural Insights: The discovery that tree burnings induce digraph structures and that path graphs always admit homomorphisms (while general trees do not) deepens the understanding of the combinatorial geometry of trees.
4. New Invariants: The introduction of "strong burning homology" offers a tool to distinguish between graphs that may have similar standard burning numbers but different structural properties regarding homomorphisms.

In summary, this paper advances the theory of graph burning by restricting the definition to exclude redundant sources, proving that this restriction allows for a reduction to spanning trees, and utilizing algebraic topology to define new homological invariants that capture the structural constraints of "strong" (homomorphic) burning processes.