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. L-Systems and the Lovász Number

   https://doi.org/10.1007/s00493-025-00136-4  

   Linz, William (April 2025, Combinatorica)

   Abstract Given integers$$n> k > 0$$ $n>k>0$, and a set of integers$$L \subset [0, k-1]$$ $L\subset [0,k-1]$, anL-systemis a family of sets$$\mathcal {F}\subset \left( {\begin{array}{c}[n]\\ k\end{array}}\right) $$ $F\subset \left(\begin{array}{c}\left[n\right]\\ k\end{array}\right)$such that$$|F \cap F'| \in L$$ $|F\cap F^{\prime }|\in L$for distinct$$F, F'\in \mathcal {F}$$ $F,F^{\prime }\in F$.L-systems correspond to independent sets in a certain generalized Johnson graphG(n, k, L), so that the maximum size of anL-system is equivalent to finding the independence number of the graphG(n, k, L). TheLovász number$$\vartheta (G)$$ $\vartheta \left(G\right)$is a semidefinite programming approximation of the independence number$$\alpha $$ $\alpha$of a graphG. In this paper, we determine the leading order term of$$\vartheta (G(n, k, L))$$ $\vartheta \left(G\right(n,k,L\left)\right)$of any generalized Johnson graph withkandLfixed and$$n\rightarrow \infty $$ $n\to \infty$. As an application of this theorem, we give an explicit construction of a graphGonnvertices with a large gap between the Lovász number and the Shannon capacityc(G). Specifically, we prove that for any$$\epsilon > 0$$ $ϵ>0$, for infinitely manynthere is a generalized Johnson graphGonnvertices which has ratio$$\vartheta (G)/c(G) = \Omega (n^{1-\epsilon })$$ $\vartheta \left(G\right)/c\left(G\right)=\Omega \left(n^{1-ϵ}\right)$, which improves on all known constructions. The graphGa fortiorialso has ratio$$\vartheta (G)/\alpha (G) = \Omega (n^{1-\epsilon })$$ $\vartheta \left(G\right)/\alpha \left(G\right)=\Omega \left(n^{1-ϵ}\right)$, which greatly improves on the best known explicit construction. 

   more » « less
3. Better Hardness Results for the Minimum Spanning Tree Congestion Problem

   https://doi.org/10.1007/s00453-024-01278-5  

   Luu, Huong; Chrobak, Marek (January 2025, Algorithmica)

   Abstract In the spanning tree congestion problem, given a connected graphG, the objective is to compute a spanning treeTinGthat minimizes its maximum edge congestion, where the congestion of an edgeeofTis the number of edges inGfor which the unique path inTbetween their endpoints traversese. The problem is known to be$$\mathbb{N}\mathbb{P}$$ $NP$-hard, but its approximability is still poorly understood, and it is not even known whether the optimum solution can be efficiently approximated with ratioo(n). In the decision version of this problem, denoted$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$, we need to determine ifGhas a spanning tree with congestion at mostK. It is known that$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$is$$\mathbb{N}\mathbb{P}$$ $NP$-complete for$$K\ge 8$$ $K\ge 8$, and this implies a lower bound of 1.125 on the approximation ratio of minimizing congestion. On the other hand,$${\varvec{3}-\textsf {STC}}$$ $3-\mathrm{STC}$can be solved in polynomial time, with the complexity status of this problem for$$K\in { \left\{ 4,5,6,7 \right\} }$$ $K\in \left(4,,,5,,,6,,,7\right)$remaining an open problem. We substantially improve the earlier hardness results by proving that$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$is$$\mathbb{N}\mathbb{P}$$ $NP$-complete for$$K\ge 5$$ $K\ge 5$. This leaves only the case$$K=4$$ $K=4$open, and improves the lower bound on the approximation ratio to 1.2. Motivated by evidence that minimizing congestion is hard even for graphs of small constant radius, we also consider$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$restricted to graphs of radius 2, and we prove that this variant is$$\mathbb{N}\mathbb{P}$$ $NP$-complete for all$$K\ge 6$$ $K\ge 6$. 

   more » « less
4. Higher arity stability and the functional order property

   https://doi.org/10.1007/s00029-025-01055-4  

   Abd_Aldaim, A; Conant, G; Terry, C (July 2025, Selecta Mathematica)

   Abstract Thek-dimensional functional order property ($$\operatorname {FOP}_k$$ ${FOP}_k$) is a combinatorial property of a$$(k+1)$$ $(k+1)$-partitioned formula. This notion arose in work of Terry and Wolf [59, 60], which identified$$\operatorname {NFOP}_2$$ ${NFOP}_2$as a ternary analogue of stability in the context of two finitary combinatorial problems related to hypergraph regularity and arithmetic regularity. In this paper we show$$\operatorname {NFOP}_k$$ ${NFOP}_k$has equally strong implications in model-theoretic classification theory, where its behavior as a$$(k+1)$$ $(k+1)$-ary version of stability is in close analogy to the behavior ofk-dependence as a$$(k+1)$$ $(k+1)$-ary version of$$\operatorname {NIP}$$ $NIP$. Our results include several new characterizations of$$\operatorname {NFOP}_k$$ ${NFOP}_k$, including a characterization in terms of collapsing indiscernibles, combinatorial recharacterizations, and a characterization in terms of type-counting when$$k=2$$ $k=2$. As a corollary of our collapsing theorem, we show$$\operatorname {NFOP}_k$$ ${NFOP}_k$is closed under Boolean combinations, and that$$\operatorname {FOP}_k$$ ${FOP}_k$can always be witnessed by a formula where all but one variable have length 1. When$$k=2$$ $k=2$, we prove a composition lemma analogous to that of Chernikov and Hempel from the setting of 2-dependence. Using this, we provide a new class of algebraic examples of$$\operatorname {NFOP}_2$$ ${NFOP}_2$theories. Specifically, we show that ifTis the theory of an infinite dimensional vector space over a fieldK, equipped with a bilinear form satisfying certain properties, thenTis$$\operatorname {NFOP}_2$$ ${NFOP}_2$if and only ifKis stable. Along the way we provide a corrected and reorganized proof of Granger’s quantifier elimination and completeness results for these theories. 

   more » « less
5. CscK metrics near the canonical class

   https://doi.org/10.1515/crelle-2024-0096  

   Guo, Bin; Jian, Wangjian; Shi, Yalong; Song, Jian (January 2025, Journal für die reine und angewandte Mathematik (Crelles Journal))

   Abstract Let 𝑋 be a Kähler manifold with semiample canonical bundle $K_X$K_{X}.It is proved in [W. Jian, Y. Shi and J. Song, A remark on constant scalar curvature Kähler metrics on minimal models,Proc. Amer. Math. Soc.147(2019), 8, 3507–3513] that, for any Kähler class 𝛾, there exists $\delta >0$\delta>0such that, for all $t\in (0,\delta )$t\in(0,\delta), there exists a unique cscK metric $g_t$g_{t}in $K_X+t\gamma$K_{X}+t\gamma.In this paper, we prove that ${\left\{(X,g_t)\right\}}_{t\in (0,\delta )}$\{(X,g_{t})\}_{t\in(0,\delta)}have uniformly bounded Kähler potentials, volume forms and diameters.As a consequence, these metric spaces are pre-compact in the Gromov–Hausdorff sense. 

   more » « less