Georgia Institute of Technology College of Sciences

We will discuss proper q-colourings of sparse, bounded degree graphs when the maximum degree is near the so-called shattering threshold. This threshold, first identified in the statistical physics literature, coincides with the point at which all known efficient colouring algorithms fail and it has been hypothesized that the geometry of the solution space (the space of proper colourings) is responsible. This hypothesis is a cousin of the Overlap-Gap property of Gamarnik ‘21. Significant evidence for this picture was provided by Achlioptos and Coja-Oghlan ‘08, who drew inspiration from statistical physics, but their work only explains the performance of algorithms on random graphs (average-case complexity). We extend their work beyond the random setting by proving that the geometry of the solution space is well behaved for all graphs below the “shattering threshold”. This follows from an original result about the structure of uniformly random colourings of fixed graphs. Joint work with François Pirot.

Morphogenesis is the biological process that causes cells, tissues, or organisms to develop their shape. The theory of morphogenesis, proposed by Alan Turning, is a chemical model where biological cells differentiate and form patterns through intercellular reaction-diffusion mechanisms. Various reaction-diffusion models can produce a chemical pattern that mimics natural patterns. However, while they provide a plausible prepattern, they do not describe a mechanism in which the pattern is expressed. An alternative model is a mechanical model of the skin, initially described by Murray, Oster, and Harris. This model used mechanical interactions between cells without a chemical prepattern to produce structures like those observed in a Turing model. In this talk, we derive a modified version of the Murray, Oster, and Harris model incorporating nonlinear deformation effects. Since it is observed in some experiments that chemicals present in developing skin can cause or disrupt pattern formation, the mechanical model is coupled with a single diffusing chemical. Furthermore, it is observed that the interaction between tissue deformations with a diffusing chemical can cause a previously undescribed instability. This instability could describe both the pattern’s chemical patterning and mechanical expression without the need for a reaction-diffusion system.

We show how the theory of Lorentzian polynomials extends to cones other than the positive orthant, and how this may be used to prove Hodge-Riemann relations of degree one for Chow rings. If time permits, we will show explicitly how the theory applies to volume polynomials of matroids and/or polytopes. Joint work with Petter Brändén.