More Like this

1. 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
2. Linking Numbers in Three-Manifolds

   https://doi.org/10.1007/s00454-021-00287-3  

   Cahn, Patricia; Kjuchukova, Alexandra (July 2021, Discrete & Computational Geometry)

   Abstract LetMbe a connected, closed, oriented three-manifold andK, Ltwo rationally null-homologous oriented simple closed curves in M. We give an explicit algorithm for computing the linking number betweenKandLin terms of a presentation of Mas an irregular dihedral three-fold cover of $$S^3$$ $S^3$branched along a knot$$\alpha \subset S^3$$ $\alpha \subset S^3$. Since every closed, oriented three-manifold admits such a presentation, our results apply to all (well-defined) linking numbers in all three-manifolds. Furthermore, ribbon obstructions for a knot $$\alpha $$ $\alpha$can be derived from dihedral covers of $$\alpha $$ $\alpha$. The linking numbers we compute are necessary for evaluating one such obstruction. This work is a step toward testing potential counter-examples to the Slice-Ribbon Conjecture, among other applications. 

   more » « less
3. Finding solutions with distinct variables to systems of linear equations over $$\mathbb {F}_p$$

   https://doi.org/10.1007/s00208-022-02391-y  

   Sauermann, Lisa (April 2022, Mathematische Annalen)

   Abstract Let us fix a primepand a homogeneous system ofmlinear equations$$a_{j,1}x_1+\dots +a_{j,k}x_k=0$$ $a_{j,1}{x}_1+\cdots +a_{j,k}{x}_k=0$for$$j=1,\dots ,m$$ $j=1,\cdots ,m$with coefficients$$a_{j,i}\in \mathbb {F}_p$$ $a_{j,i}\in F_p$. Suppose that$$k\ge 3m$$ $k\ge 3m$, that$$a_{j,1}+\dots +a_{j,k}=0$$ $a_{j,1}+\cdots +a_{j,k}=0$for$$j=1,\dots ,m$$ $j=1,\cdots ,m$and that every$$m\times m$$ $m\times m$minor of the$$m\times k$$ $m\times k$matrix$$(a_{j,i})_{j,i}$$ ${\left(a_{j,i}\right)}_{j,i}$is non-singular. Then we prove that for any (large)n, any subset$$A\subseteq \mathbb {F}_p^n$$ $A\subseteq F_p^n$of size$$|A|> C\cdot \Gamma ^n$$ $\left|A\right|>C·{\Gamma }^n$contains a solution$$(x_1,\dots ,x_k)\in A^k$$ $(x_1,\cdots ,x_k)\in A^k$to the given system of equations such that the vectors$$x_1,\dots ,x_k\in A$$ $x_1,\cdots ,x_k\in A$are all distinct. Here,Cand$$\Gamma $$ $\Gamma$are constants only depending onp,mandksuch that$$\Gamma $\Gamma <p$. The crucial point here is the condition for the vectors$$x_1,\dots ,x_k$$ $x_1,\cdots ,x_k$in the solution$$(x_1,\dots ,x_k)\in A^k$$ $(x_1,\cdots ,x_k)\in A^k$to be distinct. If we relax this condition and only demand that$$x_1,\dots ,x_k$$ $x_1,\cdots ,x_k$are not all equal, then the statement would follow easily from Tao’s slice rank polynomial method. However, handling the distinctness condition is much harder, and requires a new approach. While all previous combinatorial applications of the slice rank polynomial method have relied on the slice rank of diagonal tensors, we use a slice rank argument for a non-diagonal tensor in combination with combinatorial and probabilistic arguments. 

   more » « less
4. Property G and the 4-genus

   https://doi.org/10.1090/btran/153  

   Ni, Yi (January 2024, Transactions of the American Mathematical Society, Series B)

   We say a null-homologous knot $K$in a $3$-manifold $Y$has Property G, if the Thurston norm and fiberedness of the complement of $K$is preserved under the zero surgery on $K$. In this paper, we will show that, if the smooth $4$-genus of $K\times <\#comment/>\left\{0\right\}$(in a certain homology class) in $(Y\times <\#comment/>[0,1\left]\right)\mathrm{\#<\#comment/>}N\stackrel{¯<\#comment/>}{\mathbb{C}{P}^2}$, where $Y$is a rational homology sphere, is smaller than the Seifert genus of $K$, then $K$has Property G. When the smooth $4$-genus is $0$, $Y$can be taken to be any closed, oriented $3$-manifold. 

   more » « less
5. Dataset of theoretical multinary perovskite oxides

   https://doi.org/10.1038/s41597-023-02127-w  

   Bare, Zachary J.; Morelock, Ryan J.; Musgrave, Charles B. (December 2023, Scientific Data)

   Abstract Perovskite oxides (ternary chemical formula ABO₃) are a diverse class of materials with applications including heterogeneous catalysis, solid-oxide fuel cells, thermochemical conversion, and oxygen transport membranes. However, their multicomponent (chemical formula$${A}_{x}{A}_{1-x}^{\text{'}}{B}_{y}{B}_{1-y}^{\text{'}}{O}_{3}$$ $A_x{A}_{1-x}^{\text{'}}{B}_y{B}_{1-y}^{\text{'}}{O}_3$) chemical space is underexplored due to the immense number of possible compositions. To expand the number of computed$${A}_{x}{A}_{1-x}^{{\prime} }{B}_{y}{B}_{1-y}^{{\prime} }{O}_{3}$$ $A_x{A}_{1-x}^{\prime }{B}_y{B}_{1-y}^{\prime }{O}_3$compounds we report a dataset of 66,516 theoretical multinary oxides, 59,708 of which are perovskites. First, 69,407$${A}_{0.5}{A}_{0.5}^{{\prime} }{B}_{0.5}{B}_{0.5}^{{\prime} }{O}_{3}$$ $A_{0.5}{A}_{0.5}^{\prime }{B}_{0.5}{B}_{0.5}^{\prime }{O}_3$compositions were generated in thea⁻b⁺a⁻Glazer tilting mode using the computationally-inexpensive Structure Prediction and Diagnostic Software (SPuDS) program. Next, we optimized these structures with density functional theory (DFT) using parameters compatible with the Materials Project (MP) database. Our dataset contains these optimized structures and their formation (ΔH_f) and decomposition enthalpies (ΔH_d) computed relative to MP tabulated elemental references and competing phases, respectively. This dataset can be mined, used to train machine learning models, and rapidly and systematically expanded by optimizing more SPuDS-generated$${A}_{0.5}{A}_{0.5}^{{\prime} }{B}_{0.5}{B}_{0.5}^{{\prime} }{O}_{3}$$ $A_{0.5}{A}_{0.5}^{\prime }{B}_{0.5}{B}_{0.5}^{\prime }{O}_3$perovskite structures using MP-compatible DFT calculations. 

   more » « less