More Like this

1. A Refutation of the Pach-Tardos Conjecture for 0–1 Matrices

   https://doi.org/10.1007/s00493-025-00187-7  

   Pettie, Seth; Tardos, Gábor (December 2025, Combinatorica)

   Abstract The theory of forbidden 0–1 matrices generalizes Turán-style (bipartite) subgraph avoidance, Davenport-Schinzel theory, and Zarankiewicz-type problems, and has been influential in many areas, such as discrete and computational geometry, the analysis of self-adjusting data structures, and the development of the graph parametertwin width. The foremost open problem in this area is to resolve thePach-Tardos conjecturefrom 2005, which states that if a forbidden pattern$$P\in \{0,1\}^{k\times l}$$ $P\in {\{0,1\}}^{k\times l}$isacyclic, meaning it is the bipartite incidence matrix of a forest, then$$\operatorname {Ex}(P,n) = O(n\log ^{C_P} n)$$ $Ex(P,n)=O\left(n{log}^{C_P}n\right)$, where$$\operatorname {Ex}(P,n)$$ $Ex(P,n)$is the maximum number of 1s in aP-free$$n\times n$$ $n\times n$0–1 matrix and$$C_P$$ $C_P$is a constant depending only onP. This conjecture has been confirmed on many small patterns, specifically allPwith weight at most 5, and all but two with weight 6. The main result of this paper is a clean refutation of the Pach-Tardos conjecture. Specifically, we prove that$$\operatorname {Ex}(S_0,n),\operatorname {Ex}(S_1,n) \ge n2^{\Omega (\sqrt{\log n})}$$ $Ex(S_0,n),Ex(S_1,n)\ge n{2}^{\Omega \left(\sqrt{logn}\right)}$, where$$S_0,S_1$$ $S_0,S_1$are the outstanding weight-6 patterns. We also prove sharp bounds on the entire class ofalternatingpatterns$$(P_t)$$ $\left(P_t\right)$, specifically that for every$$t\ge 2$$ $t\ge 2$,$$\operatorname {Ex}(P_t,n)=\Theta (n(\log n/\log \log n)^t)$$ $Ex(P_t,n)=\Theta \left(n{(logn/loglogn)}^t\right)$. This is the first proof of an asymptotically sharp bound that is$$\omega (n\log n)$$ $\omega (nlogn)$. 

   more » « less
2. Carleson’s $$\varepsilon ^{2}$$ conjecture in higher dimensions

   https://doi.org/10.1007/s00222-025-01337-w  

   Fleschler, Ian; Tolsa, Xavier; Villa, Michele (July 2025, Inventiones mathematicae)

   Abstract In this paper we prove a higher dimensional analogue of Carleson’s$$\varepsilon ^{2}$$ ${\epsilon }^2$conjecture. Given two arbitrary disjoint Borel sets$$\Omega ^{+},\Omega ^{-}\subset \mathbb{R}^{n+1}$$ ${\Omega }^{+},{\Omega }^{-}\subset R^{n+1}$, and$$x\in \mathbb{R}^{n+1}$$ $x\in R^{n+1}$,$$r>0$$ $r>0$, we denote$$ \varepsilon _{n}(x,r) := \frac{1}{r^{n}}\, \inf _{H^{+}} \mathcal{H}^{n} \left ( ((\partial B(x,r)\cap H^{+}) \setminus \Omega ^{+}) \cup (( \partial B(x,r)\cap H^{-}) \setminus \Omega ^{-})\right ), $$ ${\epsilon }_n(x,r):=\frac{1}{r^n}\underset{H^{+}}{inf}{H}^n\left(\right(\left(\partial B\right(x,r)\cap H^{+})\setminus {\Omega }^{+})\cup (\left(\partial B\right(x,r)\cap H^{-})\setminus {\Omega }^{-}\left)\right),$where the infimum is taken over all open affine half-spaces$$H^{+}$$ $H^{+}$such that$$x \in \partial H^{+}$$ $x\in \partial H^{+}$and we define$$H^{-}= \mathbb{R}^{n+1} \setminus \overline{H^{+}}$$ $H^{-}=R^{n+1}\setminus \overline{H^{+}}$. Our first main result asserts that the set of points$$x\in \mathbb{R}^{n+1}$$ $x\in R^{n+1}$where$$ \int _{0}^{1} \varepsilon _{n}(x,r)^{2} \, \frac{dr}{r}< \infty $$ ${\int }_0^1{\epsilon }_n{(x,r)}^2\frac{dr}{r}<\infty$is$$n$$ $n$-rectifiable. For our second main result we assume that$$\Omega ^{+}$$ ${\Omega }^{+}$,$$\Omega ^{-}$$ ${\Omega }^{-}$are open and that$$\Omega ^{+}\cup \Omega ^{-}$$ ${\Omega }^{+}\cup {\Omega }^{-}$satisfies the capacity density condition. For each$$x \in \partial \Omega ^{+} \cup \partial \Omega ^{-}$$ $x\in \partial {\Omega }^{+}\cup \partial {\Omega }^{-}$and$$r>0$$ $r>0$, we denote by$$\alpha ^{\pm }(x,r)$$ ${\alpha }^{\pm }(x,r)$the characteristic constant of the (spherical) open sets$$\Omega ^{\pm }\cap \partial B(x,r)$$ ${\Omega }^{\pm }\cap \partial B(x,r)$. We show that, up to a set of$$\mathcal{H}^{n}$$ $H^n$measure zero,$$x$$ $x$is a tangent point for both$$\partial \Omega ^{+}$$ $\partial {\Omega }^{+}$and$$\partial \Omega ^{-}$$ $\partial {\Omega }^{-}$if and only if$$ \int _{0}^{1} \min (1,\alpha ^{+}(x,r) + \alpha ^{-}(x,r) -2) \frac{dr}{r} < \infty . $$ ${\int }_0^{1}min(1,{\alpha }^{+}(x,r)+{\alpha }^{-}(x,r)-2)\frac{dr}{r}<\infty .$The first result is new even in the plane and the second one improves and extends to higher dimensions the$$\varepsilon ^{2}$$ ${\epsilon }^2$conjecture of Carleson. 

   more » « less
3. Uniform stabilization in Besov spaces with arbitrary decay rates of the magnetohydrodynamic system by finite-dimensional interior localized static feedback controllers

   https://doi.org/10.1007/s40687-024-00490-7  

   Lasiecka, Irena; Priyasad, Buddhika; Triggiani, Roberto (December 2024, Research in the Mathematical Sciences)

   Abstract We consider thed-dimensional MagnetoHydroDynamics (MHD) system defined on a sufficiently smooth bounded domain,$$d = 2,3$$ $d=2,3$with homogeneous boundary conditions, and subject to external sources assumed to cause instability. The initial conditions for both fluid and magnetic equations are taken of low regularity. We then seek to uniformly stabilize such MHD system in the vicinity of an unstable equilibrium pair, in the critical setting of correspondingly low regularity spaces, by means of explicitly constructed, static, feedback controls, which are localized on an arbitrarily small interior subdomain. In additional, they will be minimal in number. The resulting space of well-posedness and stabilization is a suitable product space$$\displaystyle \widetilde{\textbf{B}}^{2- ^{2}\!/_{p}}_{q,p}(\Omega )\times \widetilde{\textbf{B}}^{2- ^{2}\!/_{p}}_{q,p}(\Omega ), \, 1< p < \frac{2q}{2q-1}, \, q > d,$$ ${\tilde{B}}_{q,p}^{2{-}^2{/}_p}\left(\Omega \right)\times {\tilde{B}}_{q,p}^{2{-}^2{/}_p}\left(\Omega \right),1<p<\frac{2q}{2q-1},q>d,$of tight Besov spaces for the fluid velocity component and the magnetic field component (each “close” to$$\textbf{L}^3(\Omega )$$ $L^3\left(\Omega \right)$for$$d = 3$$ $d=3$). Showing maximal$$L^p$$ $L^p$-regularity up to$$T = \infty $$ $T=\infty$for the feedback stabilized linear system is critical for the analysis of well-posedness and stabilization of the feedback nonlinear problem. 

   more » « less
4. Counting imaginary quadratic fields with an ideal class group of 5-rank at least 2

   https://doi.org/10.1007/s11139-025-01184-6  

   Bartz, Kollin; Levin, Aaron; Thamminana, Aman_Dhruva (August 2025, The Ramanujan Journal)

   Abstract We prove that there are$$\gg \frac{X^{\frac{1}{3}}}{(\log X)^2}$$ $\gg \frac{X^{\frac{1}{3}}}{{(logX)}^2}$imaginary quadratic fieldskwith discriminant$$|d_k|\le X$$ $|d_k|\le X$and an ideal class group of 5-rank at least 2. This improves a result of Byeon, who proved the lower bound$$\gg X^{\frac{1}{4}}$$ $\gg X^{\frac{1}{4}}$in the same setting. We use a method of Howe, Leprévost, and Poonen to construct a genus 2 curveCover$$\mathbb {Q}$$ $Q$such thatChas a rational Weierstrass point and the Jacobian ofChas a rational torsion subgroup of 5-rank 2. We deduce the main result from the existence of the curveCand a quantitative result of Kulkarni and the second author. 

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