More Like this

1. Sampling List Packings

   https://doi.org/10.4230/LIPIcs.ITCS.2025.24  

   Camrud, Evan; Davies, Ewan; Karduna, Alex; Lee, Holden (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   We initiate the study of approximately counting the number of list packings of a graph. The analogous problem for usual vertex coloring and list coloring has attracted substantial attention. For list packing the setup is similar, but we seek a full decomposition of the lists of colors into pairwise-disjoint proper list colorings. The existence of a list packing implies the existence of a list coloring, but the converse is false. Recent works on list packing have focused on existence or extremal results of on the number of list packings, but here we turn to the algorithmic aspects of counting and sampling. In graphs of maximum degree Δ and when the number of colors is at least Ω(Δ²), we give a fully polynomial-time randomized approximation scheme (FPRAS) based on rapid mixing of a natural Markov chain (the Glauber dynamics) which we analyze with the path coupling technique. Some motivation for our work is the investigation of an atypical spin system, one where the number of spins for each vertex is much larger than the graph degree. 

   more » « less
2. New Packings in Grassmannian Space

   https://doi.org/10.1109/ISIT45174.2021.9517770  

   Soleymani, Mahdi; Mahdavifar, Hessam (July 2021, 2021 IEEE International Symposium on Information Theory (ISIT))
3. Constructive Packings of Triple Systems

   https://doi.org/10.1137/140965107  

   Nagle, Brendan (January 2017, SIAM Journal on Discrete Mathematics)
4. Projective rigidity of circle packings

   https://doi.org/10.1016/j.aim.2024.110024  

   Bonsante, Francesco; Wolf, Michael (February 2025, Advances in Mathematics)
5. Effective Counting in Sphere Packings

   https://doi.org/10.56994/JAMR.002.001.002  

   Kontorovich, Alex; Lutsko, Christopher (March 2024, Journal of the Association for Mathematical Research)

   Given a Zariski-dense, discrete group, Γ, of isometries acting on (n + 1)- dimensional hyperbolic space, we use spectral methods to obtain a sharp asymptotic formula for the growth rate of certain Γ-orbits. In particular, this allows us to obtain a best-known effective error rate for the Apollonian and (more generally) Kleinian sphere packing counting problems, that is, counting the number of spheres in such with radius bounded by a growing parameter. Our method extends the method of Kontorovich [Kon09], which was itself an extension of the orbit counting method of Lax-Phillips [LP82], in two ways. First, we remove a compactness condition on the discrete subgroups considered via a technical cut- off and smoothing operation. Second, we develop a coordinate system which naturally corresponds to the inversive geometry underlying the sphere counting problem, and give structure theorems on the arising Casimir operator and Haar measure in these coordinates. 

   more » « less