John Peca-Medlin

John Peca-Medlin

The Horton-Strahler (HS) number, a classical measure of branching complexity arising in hydrology and register allocation, is studied for butterfly trees, a recursive family of binary trees generated by block-merging operations. These trees arise as binary search trees of butterfly permutations, which form the $2$-Sylow subgroup of the symmetric group on $N = 2^n$ elements and appear in models of parallel computation and structured Gaussian elimination. For a single merging step applied to two independent Catalan trees with $m$ nodes, we show that HS$(\mathcal T_1 \oplus \mathcal T_2)/\log_2(2m) \to 1/2$ in probability, so the classical Catalan scaling is preserved under this restricted construction. In the simple butterfly model, where each level is formed from identical copies and encoded by an $n$-bit string $\mathbf{x}$, the HS number admits an exact representation as an additive functional of an explicit $8$-state Markov chain driven by iid bits $x_j \sim \mathrm{Bern}(p)$, and can be computed in $\mathcal O(n)$ time from $\mathbf{x}$. This yields a complete limit theory, including a strong law HS$(\mathcal T_n^B)/n \to μ_p = pq/(1-pq)$ almost surely and a functional central limit theorem with variance $σ_p^2 = pq(1 - 3pq - 2p^2q^2)/(1-pq)^3$. For general butterfly trees, obtained by recursively merging independent subtrees, the increment depends on an expanding edge profile, and the process does not admit a finite-state reduction. We give an $\mathcal O(N)$ algorithm to compute the HS number directly from the $(N-1)$-bit encoding, characterize the zero-HS class, and combine exact enumeration for small $n$ with Monte Carlo simulations up to $n=25$, supporting HS$(\mathcal T_n^B)/n \to α\approx 0.4450$ in probability for uniform butterfly trees, placing the general model strictly between the simple butterfly limit $1/3$ and the Catalan limit $1/2$.

John Peca-Medlin, Chenyang Zhong

Binary search trees (BSTs) are fundamental data structures whose performance is largely governed by tree height. We introduce a block model for constructing BSTs by embedding internal BSTs into the nodes of an external BST -- a structure motivated by parallel data architectures -- corresponding to composite permutations formed via Kronecker or wreath products. Extending Devroye's result that the height $h_n$ of a random BST satisfies $h_n / \log n \to c^* \approx 4.311$, we show that block BSTs with $nm$ nodes and fixed external size $m$ satisfy $h_{n,m} / \log n \to c^* + h_m$ in distribution. We then study butterfly trees: BSTs with $N = 2^n$ nodes generated from permutations built using iterated Kronecker or wreath products. For simple butterfly trees (from iterated Kronecker products of $S_2$), we give a full distributional description showing polynomial height growth: $\mathbb{E} h_n^{\operatorname{B}} = Θ(N^α)$ with $α= \log_2(3/2) \approx 0.58496$. For nonsimple butterfly trees (from wreath products), we prove power-law bounds: $cN^α\cdot (1 + o(1)) \le \mathbb{E} h_n^{\operatorname{B}} \le dN^β\cdot (1 + o(1))$, with $β\approx 0.913189$.

John Peca-Medlin

The growth problem in Gaussian elimination (GE) remains a foundational question in numerical analysis and numerical linear algebra. Wilkinson resolved the growth problem in GE with partial pivoting (GEPP) in his initial analysis from the 1960s, while he was only able to establish an upper bound for the GE with complete pivoting (GECP) growth problem. The GECP growth problem has seen a spike in recent interest, culminating in improved lower and upper bounds established by Bisain, Edelman, and Urschel in 2023, but still remains far from being fully resolved. Due to the complex dynamics governing the location of GECP pivots, analysis of GECP growth for particular input matrices often estimates the actual growth rather than computes the growth exactly. We present a class of dense random butterfly matrices for which we can compute the exact GECP growth. We extend previous results that established exact growth computations for butterfly matrices when using GEPP and GE with rook pivoting (GERP) to now also include GECP for structured subclasses of inputs. Moreover, we present a new method to construct random Hadamard matrices using butterfly matrices.