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. Sunflowers in Set Systems with Small VC-Dimension

   https://doi.org/10.1007/s00493-025-00186-8  

   Balogh, József; Bernshteyn, Anton; Delcourt, Michelle; Ferber, Asaf; Pham, Huy Tuan (December 2025, Combinatorica)

   Abstract A family ofrdistinct sets$$\{A_1,\ldots , A_r\}$$ $\{A_1,\dots ,A_r\}$is anr-sunflower if for all$$1 \leqslant i < j\leqslant r$$ $1⩽i<j⩽r$and$$1 \leqslant i' < j'\leqslant r$$ $1⩽i^{\prime }<j^{\prime }⩽r$, we have$$A_i\cap A_j = A_{i'}\cap A_{j'}$$ $A_i\cap A_j=A_{i^{\prime }}\cap A_{j^{\prime }}$. Erdős and Rado conjectured in 1960 that every family$$\mathcal {H}$$ $H$of$$\ell $$ $\ell$-element sets of size at least$$K(r)^\ell $$ $K{\left(r\right)}^{\ell }$contains anr-sunflower, whereK(r) is some function that depends only onr. We prove that if$$\mathcal {H}$$ $H$is a family of$$\ell $$ $\ell$-element sets of VC-dimension at mostdand$$|\mathcal H| > (C r(\log d+\log ^*\ell ))^\ell $$ $\left|H\right|>{\left(Cr(logd+{log}^{\ast }\ell )\right)}^{\ell }$for some absolute constant$$C > 0$$ $C>0$, then$$\mathcal {H}$$ $H$contains anr-sunflower. This improves a recent result of Fox, Pach, and Suk. When$$d=1$$ $d=1$, we obtain a sharp bound, namely that$$|\mathcal H| > (r-1)^\ell $$ ${\left|H\right|>(r-1)}^{\ell }$is sufficient. Along the way, we establish a strengthening of the Kahn–Kalai conjecture for set families of bounded VC-dimension, which is of independent interest. 

   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)

   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
5. Restricted spaces of holomorphic sections vanishing along subvarieties

   https://doi.org/10.1007/s00209-025-03706-w  

   Coman, Dan; Marinescu, George; Nguyên, Viêt-Anh (May 2025, Mathematische Zeitschrift)

   Abstract LetXbe a compact normal complex space of dimensionnandLbe a holomorphic line bundle onX. Suppose that$$\Sigma =(\Sigma _1,\ldots ,\Sigma _\ell )$$ $\Sigma =({\Sigma }_1,\dots ,{\Sigma }_{\ell })$is an$$\ell $$ $\ell$-tuple of distinct irreducible proper analytic subsets ofX,$$\tau =(\tau _1,\ldots ,\tau _\ell )$$ $\tau =({\tau }_1,\dots ,{\tau }_{\ell })$is an$$\ell $$ $\ell$-tuple of positive real numbers, and let$$H^0_0(X,L^p)$$ $H_0^0(X,L^p)$be the space of holomorphic sections of$$L^p:=L^{\otimes p}$$ $L^p:=L^{\otimes p}$that vanish to order at least$$\tau _jp$$ ${\tau }_{j}p$along$$\Sigma _j$$ ${\Sigma }_j$,$$1\le j\le \ell $$ $1\le j\le \ell$. If$$Y\subset X$$ $Y\subset X$is an irreducible analytic subset of dimensionm, we consider the space$$H^0_0 (X|Y, L^p)$$ $H_0^0\left(X\right|Y,L^p)$of holomorphic sections of$$L^p|_Y$$ $L^p{|}_Y$that extend to global holomorphic sections in$$H^0_0(X,L^p)$$ $H_0^0(X,L^p)$. Assuming that the triplet$$(L,\Sigma ,\tau )$$ $(L,\Sigma ,\tau )$is big in the sense that$$\dim H^0_0(X,L^p)\sim p^n$$ $dim{H}_0^0(X,L^p)\sim p^n$, we give a general condition onYto ensure that$$\dim H^0_0(X|Y,L^p)\sim p^m$$ $dim{H}_0^0\left(X\right|Y,L^p)\sim p^m$. WhenLis endowed with a continuous Hermitian metric, we show that the Fubini-Study currents of the spaces$$H^0_0(X|Y,L^p)$$ $H_0^0\left(X\right|Y,L^p)$converge to a certain equilibrium current onY. We apply this to the study of the equidistribution of zeros inYof random holomorphic sections in$$H^0_0(X|Y,L^p)$$ $H_0^0\left(X\right|Y,L^p)$as$$p\rightarrow \infty $$ $p\to \infty$. 

   more » « less