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. Stable polynomials and admissible numerators in product domains

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

   Bickel, Kelly; Knese, Greg; Pascoe, James Eldred; Sola, Alan (February 2025, 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
5. Programming interactions in magnetic handshake materials

   https://doi.org/10.1039/D2SM00604A  

   Du, Chrisy Xiyu; Zhang, Hanyu Alice; Pearson, Tanner G.; Ng, Jakin; McEuen, Paul L.; Cohen, Itai; Brenner, Michael P. (August 2022, Soft Matter)

   The ability to rapidly manufacture building blocks with specific binding interactions is a key aspect of programmable assembly. Recent developments in DNA nanotechnology and colloidal particle synthesis have significantly advanced our ability to create particle sets with programmable interactions, based on DNA or shape complementarity. The increasing miniaturization underlying magnetic storage offers a new path for engineering programmable components for self assembly, by printing magnetic dipole patterns on substrates using nanotechnology. How to efficiently design dipole patterns for programmable assembly remains an open question as the design space is combinatorially large. Here, we present design rules for programming these magnetic interactions. By optimizing the structure of the dipole pattern, we demonstrate that the number of independent building blocks scales super linearly with the number of printed domains. We test these design rules using computational simulations of self assembled blocks, and experimental realizations of the blocks at the mm scale, demonstrating that the designed blocks give high yield assembly. In addition, our design rules indicate that with current printing technology, micron sized magnetic panels could easily achieve hundreds of different building blocks. 

   more » « less