More Like this

1. Channels, Billiards, and Perfect Matching 2-Divisibility

   https://doi.org/10.37236/9151  

   Barkley, Grant T.; Liu, Ricky Ini (April 2021, The Electronic Journal of Combinatorics)

   null (Ed.)

   Let $$m_G$$ denote the number of perfect matchings of the graph $$G$$. We introduce a number of combinatorial tools for determining the parity of $$m_G$$ and giving a lower bound on the power of 2 dividing $$m_G$$. In particular, we introduce certain vertex sets called channels, which correspond to elements in the kernel of the adjacency matrix of $$G$$ modulo $$2$$. A result of Lovász states that the existence of a nontrivial channel is equivalent to $$m_G$$ being even. We give a new combinatorial proof of this result and strengthen it by showing that the number of channels gives a lower bound on the power of $$2$$ dividing $$m_G$$ when $$G$$ is planar. We describe a number of local graph operations which preserve the number of channels. We also establish a surprising connection between 2-divisibility of $$m_G$$ and dynamical systems by showing an equivalency between channels and billiard paths. We exploit this relationship to show that $$2^{\frac{\gcd(m+1,n+1)-1}{2}}$$ divides the number of domino tilings of the $$m\times n$$ rectangle. We also use billiard paths to give a fast algorithm for counting channels (and hence determining the parity of the number of domino tilings) in simply connected regions of the square grid. 

   more » « less
2. A Geometric Approach to Inelastic Collapse

   Chazelle, B; Karntikoon, K; Zheng, Y. (January 2022, Computational geometry)

   We show how to interpret logarithmic spiral tilings as one-dimensional particle systems undergoing inelastic collapse. By deforming the spirals appropriately, we can simulate collisions among particles with distinct or varying coefficients of restitution. Our geometric constructions provide a strikingly simple illustration of a widely studied phenomenon in the physics of dissipative gases: the collapse of inelastic particles. 

   more » « less
3. Matrix Multiplication via Matrix Groups

   Blasiak, Jonah; Cohn, Henry; Grochow, Joshua A.; Pratt, Kevin; Umans, Chris (January 2023, Leibniz international proceedings in informatics)

   Tauman Kalai, Yael (Ed.)

   In 2003, Cohn and Umans proposed a group-theoretic approach to bounding the exponent of matrix multiplication. Previous work within this approach ruled out certain families of groups as a route to obtaining ω = 2, while other families of groups remain potentially viable. In this paper we turn our attention to matrix groups, whose usefulness within this framework was relatively unexplored. We first show that groups of Lie type cannot prove ω = 2 within the group-theoretic approach. This is based on a representation-theoretic argument that identifies the second-smallest dimension of an irreducible representation of a group as a key parameter that determines its viability in this framework. Our proof builds on Gowers' result concerning product-free sets in quasirandom groups. We then give another barrier that rules out certain natural matrix group constructions that make use of subgroups that are far from being self-normalizing. Our barrier results leave open several natural paths to obtain ω = 2 via matrix groups. To explore these routes we propose working in the continuous setting of Lie groups, in which we develop an analogous theory. Obtaining the analogue of ω = 2 in this potentially easier setting is a key challenge that represents an intermediate goal short of actually proving ω = 2. We give two constructions in the continuous setting, each of which evades one of our two barriers. 

   more » « less
4. Lattice homology, formality, and plumbed L-space links

   https://doi.org/10.4171/JEMS/1562  

   Borodzik, Maciej; Liu, Beibei; Zemke, Ian (December 2024, Journal of the European Mathematical Society)

   We define a link lattice complex for plumbed links, generalizing constructions of Ozsváth, Stipsicz and Szabó, and of Gorsky and Némethi. We prove that for all plumbed links in rational homology 3-spheres, the link lattice complex is homotopy equivalent to the link Floer complex as anA_{\infty}-module. Additionally, we prove that the link Floer complex of a plumbed L-space link is a free resolution of its homology. As a consequence, we give an algorithm to compute the link Floer complexes of plumbed L-space links, in particular of algebraic links, from their multivariable Alexander polynomial. 

   more » « less
5. Stable polynomials and admissible numerators in product domains

   https://doi.org/10.1112/blms.13201  

   Bickel, Kelly; Knese, Greg; Pascoe, James_Eldred; Sola, Alan (December 2024, Bulletin of the London Mathematical Society)

   Abstract Given a polynomial with no zeros in the polydisk, or equivalently the poly‐upper half‐plane, we study the problem of determining the ideal of polynomials with the property that the rational function is bounded near a boundary zero of . We give a complete description of this ideal of numerators in the case where the zero set of is smooth and satisfies a nondegeneracy condition. We also give a description of the ideal in terms of an integral closure when has an isolated zero on the distinguished boundary. Constructions of multivariate stable polynomials are presented to illustrate sharpness of our results and necessity of our assumptions. 

   more » « less