skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


This content will become publicly available on December 1, 2026

Title: A Refutation of the Pach-Tardos Conjecture for 0–1 Matrices
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 { 0 , 1 } k × 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 ( n log C P n ) , where$$\operatorname {Ex}(P,n)$$ Ex ( P , n ) is the maximum number of 1s in aP-free$$n\times n$$ n × 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 ) n 2 Ω ( log n ) , 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)$$ ( P t ) , specifically that for every$$t\ge 2$$ t 2 ,$$\operatorname {Ex}(P_t,n)=\Theta (n(\log n/\log \log n)^t)$$ Ex ( P t , n ) = Θ ( n ( log n / log log n ) t ) . This is the first proof of an asymptotically sharp bound that is$$\omega (n\log n)$$ ω ( n log n ) more » « less
Award ID(s):
2221980
PAR ID:
10649829
Author(s) / Creator(s):
;
Publisher / Repository:
Springer
Date Published:
Journal Name:
Combinatorica
Volume:
45
Issue:
6
ISSN:
0209-9683
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract We define a type of modulus$$\operatorname {dMod}_p$$ dMod p for Lipschitz surfaces based on$$L^p$$ L p -integrable measurable differential forms, generalizing the vector modulus of Aikawa and Ohtsuka. We show that this modulus satisfies a homological duality theorem, where for Hölder conjugate exponents$$p, q \in (1, \infty )$$ p , q ( 1 , ) , every relative Lipschitzk-homology classchas a unique dual Lipschitz$$(n-k)$$ ( n - k ) -homology class$$c'$$ c such that$$\operatorname {dMod}_p^{1/p}(c) \operatorname {dMod}_q^{1/q}(c') = 1$$ dMod p 1 / p ( c ) dMod q 1 / q ( c ) = 1 and the Poincaré dual ofcmaps$$c'$$ c to 1. As$$\operatorname {dMod}_p$$ dMod p is larger than the classical surface modulus$$\operatorname {Mod}_p$$ Mod p , we immediately recover a more general version of the estimate$$\operatorname {Mod}_p^{1/p}(c) \operatorname {Mod}_q^{1/q}(c') \le 1$$ Mod p 1 / p ( c ) Mod q 1 / q ( c ) 1 , which appears in works by Freedman and He and by Lohvansuu. Our theory is formulated in the general setting of Lipschitz Riemannian manifolds, though our results appear new in the smooth setting as well. We also provide a characterization of closed and exact Sobolev forms on Lipschitz manifolds based on integration over Lipschitzk-chains. 
    more » « less
  2. Abstract We state a general purpose algorithm for quickly finding primes in evenly divided sub-intervals. Legendre’s conjecture claims that for every positive integern, there exists a prime between$$n^2$$ n 2 and$$(n+1)^2$$ ( n + 1 ) 2 . Oppermann’s conjecture subsumes Legendre’s conjecture by claiming there are primes between$$n^2$$ n 2 and$$n(n+1)$$ n ( n + 1 ) and also between$$n(n+1)$$ n ( n + 1 ) and$$(n+1)^2$$ ( n + 1 ) 2 . Using Cramér’s conjecture as the basis for a heuristic run-time analysis, we show that our algorithm can verify Oppermann’s conjecture, and hence also Legendre’s conjecture, for all$$n\le N$$ n N in time$$O( N \log N \log \log N)$$ O ( N log N log log N ) and space$$N^{O(1/\log \log N)}$$ N O ( 1 / log log N ) . We implemented a parallel version of our algorithm and improved the empirical verification of Oppermann’s conjecture from the previous$$N = 2\cdot 10^{9}$$ N = 2 · 10 9 up to$$N = 7.05\cdot 10^{13} > 2^{46}$$ N = 7.05 · 10 13 > 2 46 , so we were finding 27 digit primes. The computation ran for about half a year on each of two platforms: four Intel Xeon Phi 7210 processors using a total of 256 cores, and a 192-core cluster of Intel Xeon E5-2630 2.3GHz processors. 
    more » « less
  3. Abstract The elliptic flow$$(v_2)$$ ( v 2 ) of$${\textrm{D}}^{0}$$ D 0 mesons from beauty-hadron decays (non-prompt$${\textrm{D}}^{0})$$ D 0 ) was measured in midcentral (30–50%) Pb–Pb collisions at a centre-of-mass energy per nucleon pair$$\sqrt{s_{\textrm{NN}}} = 5.02$$ s NN = 5.02  TeV with the ALICE detector at the LHC. The$${\textrm{D}}^{0}$$ D 0 mesons were reconstructed at midrapidity$$(|y|<0.8)$$ ( | y | < 0.8 ) from their hadronic decay$$\mathrm {D^0 \rightarrow K^-\uppi ^+}$$ D 0 K - π + , in the transverse momentum interval$$2< p_{\textrm{T}} < 12$$ 2 < p T < 12  GeV/c. The result indicates a positive$$v_2$$ v 2 for non-prompt$${{\textrm{D}}^{0}}$$ D 0 mesons with a significance of 2.7$$\sigma $$ σ . The non-prompt$${{\textrm{D}}^{0}}$$ D 0 -meson$$v_2$$ v 2 is lower than that of prompt non-strange D mesons with 3.2$$\sigma $$ σ significance in$$2< p_\textrm{T} < 8~\textrm{GeV}/c$$ 2 < p T < 8 GeV / c , and compatible with the$$v_2$$ v 2 of beauty-decay electrons. Theoretical calculations of beauty-quark transport in a hydrodynamically expanding medium describe the measurement within uncertainties. 
    more » « less
  4. Abstract LetXbe ann-element point set in thek-dimensional unit cube$$[0,1]^k$$ [ 0 , 1 ] k where$$k \ge 2$$ k 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 , , x n through thenpoints, such that$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le c_k$$ i = 1 n | x i - x i + 1 | k 1 / k 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 x 1 . From the other direction, for every$$k \ge 2$$ k 2 and$$n \ge 2$$ n 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}$$ i = 1 n | x i - x i + 1 | k 1 / k = 2 1 / k · 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 2 3 1 / k · k for every$$k \ge 3$$ k 3 and conjectured that the best constant is$$c_k = 2^{1/k} \cdot \sqrt{k}$$ c k = 2 1 / k · k , for every$$k \ge 2$$ k 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 5 2 3 1 / k · k or$$c_k = 2.91 \sqrt{k} \ (1+o_k(1))$$ c k = 2.91 k ( 1 + o k ( 1 ) ) . Our bounds are constructive. We also show that$$c_3 \ge 2^{7/6}$$ c 3 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. Abstract LetXbe a compact normal complex space of dimensionnandLbe a holomorphic line bundle onX. Suppose that$$\Sigma =(\Sigma _1,\ldots ,\Sigma _\ell )$$ Σ = ( Σ 1 , , Σ ) is an$$\ell $$ -tuple of distinct irreducible proper analytic subsets ofX,$$\tau =(\tau _1,\ldots ,\tau _\ell )$$ τ = ( τ 1 , , τ ) is an$$\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 p that vanish to order at least$$\tau _jp$$ τ j p along$$\Sigma _j$$ Σ j ,$$1\le j\le \ell $$ 1 j . If$$Y\subset X$$ Y X is an irreducible analytic subset of dimensionm, we consider the space$$H^0_0 (X|Y, L^p)$$ H 0 0 ( X | 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 , Σ , τ ) is big in the sense that$$\dim H^0_0(X,L^p)\sim p^n$$ dim H 0 0 ( X , L p ) 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 ( X | Y , L p ) 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 ( X | 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 ( X | Y , L p ) as$$p\rightarrow \infty $$ p
    more » « less