More Like this

1. Random-Cluster Dynamics on Random Regular Graphs in Tree Uniqueness

   https://doi.org/10.1007/s00220-021-04093-z  

   Blanca, Antonio ; Gheissari, Reza ( April 2021 , Communications in Mathematical Physics)

   We establish rapid mixing of the random-cluster Glauber dynamics on random$$\varDelta $$$\Delta$-regular graphs for all$$q\ge 1$$$q\ge 1$and$$p$p<p_u(q,\Delta )$, where the threshold$$p_u(q,\varDelta )$$$p_u(q,\Delta )$corresponds to a uniqueness/non-uniqueness phase transition for the random-cluster model on the (infinite)$$\varDelta $$$\Delta$-regular tree. It is expected that this threshold is sharp, and for$$q>2$$$q>2$the Glauber dynamics on random$$\varDelta $$$\Delta$-regular graphs undergoes an exponential slowdown at$$p_u(q,\varDelta )$$$p_u(q,\Delta )$. More precisely, we show that for every$$q\ge 1$$$q\ge 1$,$$\varDelta \ge 3$$$\Delta \ge 3$, and$$p$p<p_u(q,\Delta )$, with probability$$1-o(1)$$$1-o\left(1\right)$over the choice of a random$$\varDelta $$$\Delta$-regular graph onnvertices, the Glauber dynamics for the random-cluster model has$$\varTheta (n \log n)$$$\Theta (nlogn)$mixing time. As a corollary, we deduce fast mixing of the Swendsen–Wang dynamics for the Potts model on random$$\varDelta $$$\Delta$-regular graphs for every$$q\ge 2$$$q\ge 2$, in the tree uniqueness region. Our proof relies on a sharp bound on the “shattering time”, i.e., the number of steps required to break up any configuration into$$O(\log n)$$$O(logn)$sized clusters. This is established by analyzing a delicate and novel iterative scheme to simultaneously reveal the underlying random graph with clusters of the Glauber dynamics configuration on it, at a given time.

    

   more » « less
2. Perfectly Packing a Square by Squares of Nearly Harmonic Sidelength

   https://doi.org/10.1007/s00454-023-00523-y  

   Tao, Terence ( July 2023 , Discrete & Computational Geometry)

   A well-known open problem of Meir and Moser asks if the squares of sidelength 1/nfor$$n\ge 2$$$n\ge 2$can be packed perfectly into a rectangle of area$$\sum _{n=2}^\infty n^{-2}=\pi ^2/6-1$$${\sum }_{n=2}^{\infty }{n}^{-2}={\pi }^2/6-1$. In this paper we show that for any$$1/2$1/2<t<1$, and any$$n_0$$$n_0$that is sufficiently large depending on t, the squares of sidelength$$n^{-t}$$$n^{-t}$for$$n\ge n_0$$$n\ge n_0$can be packed perfectly into a square of area$$\sum _{n=n_0}^\infty n^{-2t}$$${\sum }_{n=n_0}^{\infty }{n}^{-2t}$. This was previously known (if one packs a rectangle instead of a square) for$$1/2$1/2<t\le 2/3$(in which case one can take$$n_0=1$$$n_0=1$).

    

   more » « less
3. On a Traveling Salesman Problem for Points in the Unit Cube

   https://doi.org/10.1007/s00453-024-01257-w  

   Balogh, József ; Clemen, Felix Christian ; Dumitrescu, Adrian ( September 2024 , Algorithmica)

   LetXbe ann-element point set in thek-dimensional unit cube$$[0,1]^k$$${[0,1]}^k$where$$k \ge 2$$$k\ge 2$. According to an old result of Bollobás and Meir (Oper Res Lett 11:19–21, 1992) , there exists a cycle (tour)$$x_1, x_2, \ldots , x_n$$$x_1,x_2,\dots ,x_n$through thenpoints, such that$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le c_k$$${\left({\sum }_{i=1}^n,{|x_i-x_{i+1}|}^k\right)}^{1/k}\le c_k$, where$$|x-y|$$$|x-y|$is the Euclidean distance betweenxandy, and$$c_k$$$c_k$is an absolute constant that depends only onk, where$$x_{n+1} \equiv x_1$$$x_{n+1}\equiv x_1$. From the other direction, for every$$k \ge 2$$$k\ge 2$and$$n \ge 2$$$n\ge 2$, there existnpoints in$$[0,1]^k$$${[0,1]}^k$, such that their shortest tour satisfies$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} = 2^{1/k} \cdot \sqrt{k}$$${\left({\sum }_{i=1}^n,{|x_i-x_{i+1}|}^k\right)}^{1/k}=2^{1/k}·\sqrt{k}$. For the plane, the best constant is$$c_2=2$$$c_2=2$and this is the only exact value known. Bollobás and Meir showed that one can take$$c_k = 9 \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$$c_k=9{\left(\frac{2}{3}\right)}^{1/k}·\sqrt{k}$for every$$k \ge 3$$$k\ge 3$and conjectured that the best constant is$$c_k = 2^{1/k} \cdot \sqrt{k}$$$c_k=2^{1/k}·\sqrt{k}$, for every$$k \ge 2$$$k\ge 2$. Here we significantly improve the upper bound and show that one can take$$c_k = 3 \sqrt{5} \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$$c_k=3\sqrt{5}{\left(\frac{2}{3}\right)}^{1/k}·\sqrt{k}$or$$c_k = 2.91 \sqrt{k} \ (1+o_k(1))$$$c_k=2.91\sqrt{k}(1+o_k\left(1\right))$. Our bounds are constructive. We also show that$$c_3 \ge 2^{7/6}$$$c_3\ge 2^{7/6}$, which disproves the conjecture for$$k=3$$$k=3$. Connections to matching problems, power assignment problems, related problems, including algorithms, are discussed in this context. A slightly revised version of the Bollobás–Meir conjecture is proposed.

    

   more » « less
4. Characterizing Schwarz maps by tracial inequalities

   https://doi.org/10.1007/s11005-023-01636-4  

   Carlen, Eric ; Müller-Hermes, Alexander ( February 2023 , Letters in Mathematical Physics)

   Let$$\phi $$$\varphi$be a positive map from the$$n\times n$$$n\times n$matrices$$\mathcal {M}_n$$$M_n$to the$$m\times m$$$m\times m$matrices$$\mathcal {M}_m$$$M_m$. It is known that$$\phi $$$\varphi$is 2-positive if and only if for all$$K\in \mathcal {M}_n$$$K\in M_n$and all strictly positive$$X\in \mathcal {M}_n$$$X\in M_n$,$$\phi (K^*X^{-1}K) \geqslant \phi (K)^*\phi (X)^{-1}\phi (K)$$$\varphi \left(K^{\ast }{X}^{-1}K\right)⩾\varphi {\left(K\right)}^{\ast }\varphi {\left(X\right)}^{-1}\varphi \left(K\right)$. This inequality is not generally true if$$\phi $$$\varphi$is merely a Schwarz map. We show that the corresponding tracial inequality$${{\,\textrm{Tr}\,}}[\phi (K^*X^{-1}K)] \geqslant {{\,\textrm{Tr}\,}}[\phi (K)^*\phi (X)^{-1}\phi (K)]$$$\text{Tr}\left[\varphi \left(K^{\ast }{X}^{-1}K\right)\right]⩾\text{Tr}\left[\varphi {\left(K\right)}^{\ast }\varphi {\left(X\right)}^{-1}\varphi \left(K\right)\right]$holds for a wider class of positive maps that is specified here. We also comment on the connections of this inequality with various monotonicity statements that have found wide use in mathematical physics, and apply it, and a close relative, to obtain some new, definitive results.

    

   more » « less
5. Hermitian–Yang–Mills Connections on Collapsing Elliptically Fibered K3 Surfaces

   https://doi.org/10.1007/s12220-021-00808-9  

   Datar, Ved ; Jacob, Adam ( January 2022 , The Journal of Geometric Analysis)

   Let$$X\rightarrow {{\mathbb {P}}}^1$$$X\to P^1$be an elliptically fiberedK3 surface, admitting a sequence$$\omega _{i}$$${\omega }_i$of Ricci-flat metrics collapsing the fibers. LetVbe a holomorphicSU(n) bundle overX, stable with respect to$$\omega _i$$${\omega }_i$. Given the corresponding sequence$$\Xi _i$$${\Xi }_i$of Hermitian–Yang–Mills connections onV, we prove that, ifEis a generic fiber, the restricted sequence$$\Xi _i|_{E}$$${\Xi }_i{|}_E$converges to a flat connection$$A_0$$$A_0$. Furthermore, if the restriction$$V|_E$$${V|}_E$is of the form$$\oplus _{j=1}^n{\mathcal {O}}_E(q_j-0)$$${\oplus }_{j=1}^n{O}_E(q_j-0)$forndistinct points$$q_j\in E$$$q_j\in E$, then these points uniquely determine$$A_0$$$A_0$.

    

   more » « less