More Like this

1. The Dimension of Divisibility Orders and Multiset Posets

   https://doi.org/10.1007/s11083-023-09653-7  

   Haiman, Milan ( November 2023 , Order)

   The Dushnik–Miller dimension of a posetPis the leastdfor whichPcan be embedded into a product ofdchains. Lewis and Souza isibility order on the interval of integers$$[N/\kappa , N]$$$[N/\kappa ,N]$is bounded above by$$\kappa (\log \kappa )^{1+o(1)}$$$\kappa {(log\kappa )}^{1+o\left(1\right)}$and below by$$\Omega ((\log \kappa /\log \log \kappa )^2)$$$\Omega \left({(log\kappa /loglog\kappa )}^2\right)$. We improve the upper bound to$$O((\log \kappa )^3/(\log \log \kappa )^2).$$$O({(log\kappa )}^3/{(loglog\kappa )}^2).$We deduce this bound from a more general result on posets of multisets ordered by inclusion. We also consider other divisibility orders and give a bound for polynomials ordered by divisibility.

    

   more » « less
2. Introducing isodynamic points for binary forms and their ratios

   https://doi.org/10.1007/s40627-022-00112-4  

   Hägg, Christian ; Shapiro, Boris ; Shapiro, Michael ( January 2023 , Complex Analysis and its Synergies)

   The isodynamic points of a plane triangle are known to be the only pair of its centers invariant under the action of the Möbius group$${\mathcal {M}}$$$M$on the set of triangles, Kimberling (Encyclopedia of Triangle Centers,http://faculty.evansville.edu/ck6/encyclopedia). Generalizing this classical result, we introduce below theisodynamicmap associating to a univariate polynomial of degree$$d\ge 3$$$d\ge 3$with at most double roots a polynomial of degree (at most)$$2d-4$$$2d-4$such that this map commutes with the action of the Möbius group$${\mathcal {M}}$$$M$on the zero loci of the initial polynomial and its image. The roots of the image polynomial will be called theisodynamic pointsof the preimage polynomial. Our construction naturally extends from univariate polynomials to binary forms and further to their ratios.

    

   more » « less
3. Evidence of a liquid–liquid phase transition in H$$_2$$O and D$$_2$$O from path-integral molecular dynamics simulations

   https://doi.org/10.1038/s41598-022-09525-x  

   Eltareb, Ali ; Lopez, Gustavo E. ; Giovambattista, Nicolas ( April 2022 , Scientific Reports)

   We perform path-integral molecular dynamics (PIMD), ring-polymer MD (RPMD), and classical MD simulations of H$$_2$$${}_2$O and D$$_2$$${}_2$O using the q-TIP4P/F water model over a wide range of temperatures and pressures. The density$$\rho (T)$$$\rho \left(T\right)$, isothermal compressibility$$\kappa _T(T)$$${\kappa }_T\left(T\right)$, and self-diffusion coefficientsD(T) of H$$_2$$${}_2$O and D$$_2$$${}_2$O are in excellent agreement with available experimental data; the isobaric heat capacity$$C_P(T)$$$C_P\left(T\right)$obtained from PIMD and MD simulations agree qualitatively well with the experiments. Some of these thermodynamic properties exhibit anomalous maxima upon isobaric cooling, consistent with recent experiments and with the possibility that H$$_2$$${}_2$O and D$$_2$$${}_2$O exhibit a liquid-liquid critical point (LLCP) at low temperatures and positive pressures. The data from PIMD/MD for H$$_2$$${}_2$O and D$$_2$$${}_2$O can be fitted remarkably well using the Two-State-Equation-of-State (TSEOS). Using the TSEOS, we estimate that the LLCP for q-TIP4P/F H$$_2$$${}_2$O, from PIMD simulations, is located at$$P_c = 167 \pm 9$$$P_c=167\pm 9$ MPa,$$T_c = 159 \pm 6$$$T_c=159\pm 6$ K, and$$\rho _c = 1.02 \pm 0.01$$${\rho }_c=1.02\pm 0.01$ g/cm$$^3$$${}^3$. Isotope substitution effects are important; the LLCP location in q-TIP4P/F D$$_2$$${}_2$O is estimated to be$$P_c = 176 \pm 4$$$P_c=176\pm 4$ MPa,$$T_c = 177 \pm 2$$$T_c=177\pm 2$ K, and$$\rho _c = 1.13 \pm 0.01$$${\rho }_c=1.13\pm 0.01$ g/cm$$^3$$${}^3$. Interestingly, for the water model studied, differences in the LLCP location from PIMD and MD simulations suggest that nuclear quantum effects (i.e., atoms delocalization) play an important role in the thermodynamics of water around the LLCP (from the MD simulations of q-TIP4P/F water,$$P_c = 203 \pm 4$$$P_c=203\pm 4$ MPa,$$T_c = 175 \pm 2$$$T_c=175\pm 2$ K, and$$\rho _c = 1.03 \pm 0.01$$${\rho }_c=1.03\pm 0.01$ g/cm$$^3$$${}^3$). Overall, our results strongly support the LLPT scenario to explain water anomalous behavior, independently of the fundamental differences between classical MD and PIMD techniques. The reported values of$$T_c$$$T_c$for D$$_2$$${}_2$O and, particularly, H$$_2$$${}_2$O suggest that improved water models are needed for the study of supercooled water.

    

   more » « less
4. Non-simple conformal loop ensembles on Liouville quantum gravity and the law of CLE percolation interfaces

   https://doi.org/10.1007/s00440-021-01070-4  

   Miller, Jason ; Sheffield, Scott ; Werner, Wendelin ( June 2021 , Probability Theory and Related Fields)

   We study the structure of the Liouville quantum gravity (LQG) surfaces that are cut out as one explores a conformal loop-ensemble$$\hbox {CLE}_{\kappa '}$$${\text{CLE}}_{{\kappa }^{\prime }}$for$$\kappa '$$${\kappa }^{\prime }$in (4, 8) that is drawn on an independent$$\gamma $$$\gamma$-LQG surface for$$\gamma ^2=16/\kappa '$$${\gamma }^2=16/{\kappa }^{\prime }$. The results are similar in flavor to the ones from our companion paper dealing with$$\hbox {CLE}_{\kappa }$$${\text{CLE}}_{\kappa }$for$$\kappa $$$\kappa$in (8/3, 4), where the loops of the CLE are disjoint and simple. In particular, we encode the combined structure of the LQG surface and the$$\hbox {CLE}_{\kappa '}$$${\text{CLE}}_{{\kappa }^{\prime }}$in terms of stable growth-fragmentation trees or their variants, which also appear in the asymptotic study of peeling processes on decorated planar maps. This has consequences for questions that do a priori not involve LQG surfaces: In our paper entitled “CLE Percolations” described the law of interfaces obtained when coloring the loops of a$$\hbox {CLE}_{\kappa '}$$${\text{CLE}}_{{\kappa }^{\prime }}$independently into two colors with respective probabilitiespand$$1-p$$$1-p$. This description was complete up to one missing parameter$$\rho $$$\rho$. The results of the present paper about CLE on LQG allow us to determine its value in terms ofpand$$\kappa '$$${\kappa }^{\prime }$. It shows in particular that$$\hbox {CLE}_{\kappa '}$$${\text{CLE}}_{{\kappa }^{\prime }}$and$$\hbox {CLE}_{16/\kappa '}$$${\text{CLE}}_{16/{\kappa }^{\prime }}$are related via a continuum analog of the Edwards-Sokal coupling between$$\hbox {FK}_q$$${\text{FK}}_q$percolation and theq-state Potts model (which makes sense even for non-integerqbetween 1 and 4) if and only if$$q=4\cos ^2(4\pi / \kappa ')$$$q=4{cos}^2(4\pi /{\kappa }^{\prime })$. This provides further evidence for the long-standing belief that$$\hbox {CLE}_{\kappa '}$$${\text{CLE}}_{{\kappa }^{\prime }}$and$$\hbox {CLE}_{16/\kappa '}$$${\text{CLE}}_{16/{\kappa }^{\prime }}$represent the scaling limits of$$\hbox {FK}_q$$${\text{FK}}_q$percolation and theq-Potts model whenqand$$\kappa '$$${\kappa }^{\prime }$are related in this way. Another consequence of the formula for$$\rho (p,\kappa ')$$$\rho (p,{\kappa }^{\prime })$is the value of half-plane arm exponents for such divide-and-color models (a.k.a. fuzzy Potts models) that turn out to take a somewhat different form than the usual critical exponents for two-dimensional models.

    

   more » « less
5. Algorithms for covering multiple submodular constraints and applications

   https://doi.org/10.1007/s10878-022-00874-x  

   Chekuri, Chandra ; Inamdar, Tanmay ; Quanrud, Kent ; Varadarajan, Kasturi ; Zhang, Zhao ( June 2022 , Journal of Combinatorial Optimization)

   We consider the problem of covering multiple submodular constraints. Given a finite ground setN, a weight function$$w: N \rightarrow \mathbb {R}_+$$$w:N\to R_{+}$,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$$f_1,f_2,\dots ,f_r$overNand requirements$$k_1,k_2,\ldots ,k_r$$$k_1,k_2,\dots ,k_r$the goal is to find a minimum weight subset$$S \subseteq N$$$S\subseteq N$such that$$f_i(S) \ge k_i$$$f_i\left(S\right)\ge k_i$for$$1 \le i \le r$$$1\le i\le r$. We refer to this problem asMulti-Submod-Coverand it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$$r=1$Multi-Submod-Covergeneralizes the well-known Submodular Set Cover problem (Submod-SC), and it can also be easily reduced toSubmod-SC. A simple greedy algorithm gives an$$O(\log (kr))$$$O(log(kr\left)\right)$approximation where$$k = \sum _i k_i$$$k={\sum }_i{k}_i$and this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm forMulti-Submod-Coverthat covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$$(1-1/e-\epsilon )$while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$$O(\frac{1}{ϵ}logr)$in the cost. Second, we consider the special case when each$$f_i$$$f_i$is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (Partial-SC), covering integer programs (CIPs) and multiple vertex cover constraints Bera et al. (Theoret Comput Sci 555:2–8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems.

    

   more » « less