Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates the stacking and clearing numbers of graphs by introducing and analyzing the Almost Stacked Hypothesis (ASH), which posits that these parameters are determined by configurations with at most one vertex holding multiple pebbles. The authors prove that ASH implies tight bounds for cycles $C_{2n}$ and $C_{2n+1}$, and establish that ASH is equivalent to the equality $\operatorname{stack}(T)=\operatorname{estim}(T)$ for finite trees $T$. Furthermore, assuming ASH, they construct infinite families of perfectly pebblable graphs with vanishing edge density, challenging the intuition that perfect pebblability requires dense connectivity.
A conjecture on graph pebbling thresholds, if true, implies the existence of infinitely many sparse graphs with minimal clearing numbers.
We study two graph pebbling parameters, the stacking number and the clearing number, through the Almost Stacked Hypothesis (ASH). This hypothesis asserts that these thresholds can be determined by testing only configurations in which at most one vertex carries more than one pebble. We prove that every almost stacked configuration of size $2^{n+1}-1$ on $C_{2n}$ is stackable and that every almost stacked configuration of size $3\cdot 2^n-2$ on $C_{2n+1}$ is clearable. Together with the known lower bounds, these results show that ASH implies $\operatorname{stack}(C_{2n})=2^{n+1}-1$ and $\operatorname{clear}(C_{2n+1})=3\cdot 2^n-2$. For a finite tree $T$, we introduce an explicit invariant $\operatorname{estim}(T)$. We prove unconditionally that $\operatorname{stack}(T)\geq\operatorname{estim}(T)$ and prove the reverse inequality under ASH. Consequently, ASH yields $\operatorname{stack}(T)=\operatorname{estim}(T)$, and we conjecture that this equality holds unconditionally. Finally, we study perfectly pebblable graphs: finite connected non-bipartite graphs whose clearing number has the minimum possible value $\operatorname{clear}(G)=|V(G)|+1$. Every complete graph with at least three vertices is perfectly pebblable, which might suggest that perfect pebblability requires high edge density. Assuming ASH, however, we show that this is not the case. We give a sufficient criterion involving strong edge-triangulation and Hamiltonian-path and path-cover conditions in vertex-deleted subgraphs and use it to construct two explicit infinite families of perfectly pebblable graphs with edge density tending to zero, one of which has only a linear number of edges.