2018/03/30 by Melanie Fraser, Fraser, Melanie
Computer Science · Engineering · #05A19 #05C05 #05C85 #15A24 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Matrix Theory and Algorithms #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1804.00068
openalex publication_date 2018/03/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Lewis Carroll Identity expresses the determinant of a matrix in terms of\nsubdeterminants obtained by deleting one row and column or a pair of rows and\ncolumns. Using the matrix tree theorem, we can convert this into an equivalent\nidentity involving sums over pairs of forests. Unlike the Lewis Carroll\nIdentity, the Forest Identity involves no minus signs. In 2011, Vlasev and\nYeats suggested that such a Forest Identity could be proven using edge\ntransfers similar to Zeilberger's 1997 matrix proof. However, until now, such\nan algorithm has not yet been developed. In this paper, we provide this edge\ntransfer algorithm and a bijective proof for both the Lewis Carroll Identity\nand Forest Identity. This bijection is implemented by the Red Hot Potato\nalgorithm, so called because the way edges get tossed back and forth between\nthe two forests is reminiscent of the children's game of hot potato.\n