More Like this

1. Connection probabilities of multiple FK-Ising interfaces

   https://doi.org/10.1007/s00440-024-01269-1  

   Feng, Yu; Peltola, Eveliina; Wu, Hao (June 2024, Probability Theory and Related Fields)

   Abstract We find the scaling limits of a general class of boundary-to-boundary connection probabilities and multiple interfaces in the critical planar FK-Ising model, thus verifying predictions from the physics literature. We also discuss conjectural formulas using Coulomb gas integrals for the corresponding quantities in general critical planar random-cluster models with cluster-weight$${q \in [1,4)}$$ $q\in [1,4)$. Thus far, proofs for convergence, including ours, rely on discrete complex analysis techniques and are beyond reach for other values ofqthan the FK-Ising model ($$q=2$$ $q=2$). Given the convergence of interfaces, the conjectural formulas for other values ofqcould be verified similarly with relatively minor technical work. The limit interfaces are variants of$$\text {SLE}_\kappa $$ ${\text{SLE}}_{\kappa }$curves (with$$\kappa = 16/3$$ $\kappa =16/3$for$$q=2$$ $q=2$). Their partition functions, that give the connection probabilities, also satisfy properties predicted for correlation functions in conformal field theory (CFT), expected to describe scaling limits of critical random-cluster models. We verify these properties for all$$q \in [1,4)$$ $q\in [1,4)$, thus providing further evidence of the expected CFT description of these models. 

   more » « less
2. Hardness and approximation of submodular minimum linear ordering problems

   https://doi.org/10.1007/s10107-023-02038-z  

   Farhadi, Majid; Gupta, Swati; Sun, Shengding; Tetali, Prasad; Wigal, Michael C (December 2023, Mathematical Programming)

   Abstract The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost$$f(\cdot )$$ $f(·)$due to an ordering$$\sigma $$ $\sigma$of the items (say [n]), i.e.,$$\min _{\sigma } \sum _{i\in [n]} f(E_{i,\sigma })$$ ${min}_{\sigma }{\sum }_{i\in \left[n\right]}f\left(E_{i,\sigma }\right)$, where$$E_{i,\sigma }$$ $E_{i,\sigma }$is the set of items mapped by$$\sigma $$ $\sigma$to indices [i]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whether the graphic matroid MLOP was NP-hard. We settle this question through non-trivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. This is in contrast to the rounding algorithm by Iwata et al. (in: APPROX, 2012), using Lovász extension of submodular functions. We show a$$(2-\frac{1+\ell _{f}}{1+|E|})$$ $(2-\frac{1+{\ell }_f}{1+\left|E\right|})$-approximation for monotone submodular MLOP where$$\ell _{f}=\frac{f(E)}{\max _{x\in E}f(\{x\})}$$ ${\ell }_f=\frac{f\left(E\right)}{{max}_{x\in E}f\left(\left\{x\right\}\right)}$satisfies$$1 \le \ell _f \le |E|$$ $1\le {\ell }_f\le \left|E\right|$. Our theory provides new approximation bounds for special cases of the problem, in particular a$$(2-\frac{1+r(E)}{1+|E|})$$ $(2-\frac{1+r\left(E\right)}{1+\left|E\right|})$-approximation for the matroid MLOP, where$$f = r$$ $f=r$is the rank function of a matroid. We further show that minimum latency vertex cover is$$\frac{4}{3}$$ $\frac{4}{3}$-approximable, by which we also lower bound the integrality gap of its natural LP relaxation, which might be of independent interest. 

   more » « less
3. Multipliers on bi-parameter Haar system Hardy spaces

   https://doi.org/10.1007/s00208-024-02887-9  

   Lechner, R.; Motakis, P.; Müller, P_F_X; Schlumprecht, Th (May 2024, Mathematische Annalen)

   Abstract Let$$(h_I)$$ $\left(h_I\right)$denote the standard Haar system on [0, 1], indexed by$$I\in \mathcal {D}$$ $I\in D$, the set of dyadic intervals and$$h_I\otimes h_J$$ $h_I\otimes h_J$denote the tensor product$$(s,t)\mapsto h_I(s) h_J(t)$$ $(s,t)\mapsto h_I\left(s\right)h_J\left(t\right)$,$$I,J\in \mathcal {D}$$ $I,J\in D$. We consider a class of two-parameter function spaces which are completions of the linear span$$\mathcal {V}(\delta ^2)$$ $V\left({\delta }^2\right)$of$$h_I\otimes h_J$$ $h_I\otimes h_J$,$$I,J\in \mathcal {D}$$ $I,J\in D$. This class contains all the spaces of the formX(Y), whereXandYare either the Lebesgue spaces$$L^p[0,1]$$ $L^p[0,1]$or the Hardy spaces$$H^p[0,1]$$ $H^p[0,1]$,$$1\le p < \infty $$ $1\le p<\infty$. We say that$$D:X(Y)\rightarrow X(Y)$$ $D:X\left(Y\right)\to X\left(Y\right)$is a Haar multiplier if$$D(h_I\otimes h_J) = d_{I,J} h_I\otimes h_J$$ $D(h_I\otimes h_J)=d_{I,J}{h}_I\otimes h_J$, where$$d_{I,J}\in \mathbb {R}$$ $d_{I,J}\in R$, and ask which more elementary operators factor throughD. A decisive role is played by theCapon projection$$\mathcal {C}:\mathcal {V}(\delta ^2)\rightarrow \mathcal {V}(\delta ^2)$$ $C:V\left({\delta }^2\right)\to V\left({\delta }^2\right)$given by$$\mathcal {C} h_I\otimes h_J = h_I\otimes h_J$$ $C{h}_I\otimes h_J=h_I\otimes h_J$if$$|I|\le |J|$$ $\left|I\right|\le \left|J\right|$, and$$\mathcal {C} h_I\otimes h_J = 0$$ $C{h}_I\otimes h_J=0$if$$|I| > |J|$$ $\left|I\right|>\left|J\right|$, as our main result highlights: Given any bounded Haar multiplier$$D:X(Y)\rightarrow X(Y)$$ $D:X\left(Y\right)\to X\left(Y\right)$, there exist$$\lambda ,\mu \in \mathbb {R}$$ $\lambda ,\mu \in R$such that$$\begin{aligned} \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C})\text { approximately 1-projectionally factors through }D, \end{aligned}$$ $\begin{array}{c}\lambda C+\mu (\text{Id}-C)\text{approximately 1-projectionally factors through}D,\end{array}$i.e., for all$$\eta > 0$$ $\eta >0$, there exist bounded operatorsA, Bso thatABis the identity operator$${{\,\textrm{Id}\,}}$$ $\text{Id}$,$$\Vert A\Vert \cdot \Vert B\Vert = 1$$ $\Vert A\Vert ·\Vert B\Vert =1$and$$\Vert \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C}) - ADB\Vert < \eta $$ $\Vert \lambda C+\mu (\text{Id}-C)-ADB\Vert <\eta$. Additionally, if$$\mathcal {C}$$ $C$is unbounded onX(Y), then$$\lambda = \mu $$ $\lambda =\mu$and then$${{\,\textrm{Id}\,}}$$ $\text{Id}$either factors throughDor$${{\,\textrm{Id}\,}}-D$$ $\text{Id}-D$. 

   more » « less
4. 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)

   Abstract 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
5. Twisted-bilayer FeSe and the Fe-based superlattices

   https://doi.org/10.21468/SciPostPhys.15.3.081  

   Eugenio, Paul Myles; Vafek, Oskar (January 2023, SciPost Physics)

   We derive BM-like continuum models for the bands of superlattice heterostructures formed out of Fe-chalcogenide monolayers: (I) a single monolayer experiencing an external periodic potential, and (II) twisted bilayers with long-range moire tunneling. A symmetry derivation for the inter-layer moire tunnelling is provided for both the\Gamma $\Gamma$andM $M$high-symmetry points. In this paper, we focus on moire bands formed from hole-band maxima centered on\Gamma $\Gamma$, and show the possibility of moire bands withC=0 $C=0$or±1 $\pm 1$topological quantum numbers without breaking time-reversal symmetry. In theC=0 $C=0$region for\theta→0 $\theta \to 0$(and similarly in the limit of large superlattice period for I), the system becomes a square lattice of 2D harmonic oscillators. We fit our model to FeSe and argue that it is a viable platform for the simulation of the square Hubbard model with tunable interaction strength. 

   more » « less