More Like this

1. 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
2. Polynomial Bounds for Chromatic Number. IV: A Near-polynomial Bound for Excluding the Five-vertex Path

   https://doi.org/10.1007/s00493-023-00015-w  

   Scott, Alex ; Seymour, Paul ; Spirkl, Sophie ( October 2023 , Combinatorica)

   A graphGisH-freeif it has no induced subgraph isomorphic toH. We prove that a$$P_5$$$P_5$-free graph with clique number$$\omega \ge 3$$$\omega \ge 3$has chromatic number at most$$\omega ^{\log _2(\omega )}$$${\omega }^{{log}_2\left(\omega \right)}$. The best previous result was an exponential upper bound$$(5/27)3^{\omega }$$$(5/27)3^{\omega }$, due to Esperet, Lemoine, Maffray, and Morel. A polynomial bound would imply that the celebrated Erdős-Hajnal conjecture holds for$$P_5$$$P_5$, which is the smallest open case. Thus, there is great interest in whether there is a polynomial bound for$$P_5$$$P_5$-free graphs, and our result is an attempt to approach that.

    

   more » « less
3. Undecidable Translational Tilings with Only Two Tiles, or One Nonabelian Tile

   https://doi.org/10.1007/s00454-022-00426-4  

   Greenfeld, Rachel ; Tao, Terence ( January 2023 , Discrete & Computational Geometry)

   We construct an example of a group$$G = \mathbb {Z}^2 \times G_0$$$G=Z^2\times G_0$for a finite abelian group $$G_0$$$G_0$, a subsetEof $$G_0$$$G_0$, and two finite subsets$$F_1,F_2$$$F_1,F_2$of G, such that it is undecidable in ZFC whether$$\mathbb {Z}^2\times E$$$Z^2\times E$can be tiled by translations of$$F_1,F_2$$$F_1,F_2$. In particular, this implies that this tiling problem isaperiodic, in the sense that (in the standard universe of ZFC) there exist translational tilings ofEby the tiles$$F_1,F_2$$$F_1,F_2$, but no periodic tilings. Previously, such aperiodic or undecidable translational tilings were only constructed for sets of eleven or more tiles (mostly in $$\mathbb {Z}^2$$$Z^2$). A similar construction also applies for$$G=\mathbb {Z}^d$$$G=Z^d$for sufficiently large d. If one allows the group$$G_0$$$G_0$to be non-abelian, a variant of the construction produces an undecidable translational tiling with only one tile F. The argument proceeds by first observing that a single tiling equation is able to encode an arbitrary system of tiling equations, which in turn can encode an arbitrary system of certain functional equations once one has two or more tiles. In particular, one can use two tiles to encode tiling problems for an arbitrary number of tiles.

    

   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)

   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. Comparing solution paths of sparse quadratic minimization with a Stieltjes matrix

   https://doi.org/10.1007/s10107-023-01966-0  

   He, Ziyu ; Han, Shaoning ; Gómez, Andrés ; Cui, Ying ; Pang, Jong-Shi ( May 2023 , Mathematical Programming)

   This paper studies several solution paths of sparse quadratic minimization problems as a function of the weighing parameter of the bi-objective of estimation loss versus solution sparsity. Three such paths are considered: the “$$\ell _0$$${\ell }_0$-path” where the discontinuous$$\ell _0$$${\ell }_0$-function provides the exact sparsity count; the “$$\ell _1$$${\ell }_1$-path” where the$$\ell _1$$${\ell }_1$-function provides a convex surrogate of sparsity count; and the “capped$$\ell _1$$${\ell }_1$-path” where the nonconvex nondifferentiable capped$$\ell _1$$${\ell }_1$-function aims to enhance the$$\ell _1$$${\ell }_1$-approximation. Serving different purposes, each of these three formulations is different from each other, both analytically and computationally. Our results deepen the understanding of (old and new) properties of the associated paths, highlight the pros, cons, and tradeoffs of these sparse optimization models, and provide numerical evidence to support the practical superiority of the capped$$\ell _1$$${\ell }_1$-path. Our study of the capped$$\ell _1$$${\ell }_1$-path is interesting in its own right as the path pertains to computable directionally stationary (= strongly locally minimizing in this context, as opposed to globally optimal) solutions of a parametric nonconvex nondifferentiable optimization problem. Motivated by classical parametric quadratic programming theory and reinforced by modern statistical learning studies, both casting an exponential perspective in fully describing such solution paths, we also aim to address the question of whether some of them can be fully traced in strongly polynomial time in the problem dimensions. A major conclusion of this paper is that a path of directional stationary solutions of the capped$$\ell _1$$${\ell }_1$-regularized problem offers interesting theoretical properties and practical compromise between the$$\ell _0$$${\ell }_0$-path and the$$\ell _1$$${\ell }_1$-path. Indeed, while the$$\ell _0$$${\ell }_0$-path is computationally prohibitive and greatly handicapped by the repeated solution of mixed-integer nonlinear programs, the quality of$$\ell _1$$${\ell }_1$-path, in terms of the two criteria—loss and sparsity—in the estimation objective, is inferior to the capped$$\ell _1$$${\ell }_1$-path; the latter can be obtained efficiently by a combination of a parametric pivoting-like scheme supplemented by an algorithm that takes advantage of the Z-matrix structure of the loss function.

    

   more » « less