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. Algorithms for covering multiple submodular constraints and applications

   https://doi.org/10.1007/s10878-022-00874-x  

   Chekuri, Chandra; Inamdar, Tanmay; Quanrud, Kent; Varadarajan, Kasturi; Zhang, Zhao (June 2022, Journal of Combinatorial Optimization)

   Abstract We consider the problem of covering multiple submodular constraints. Given a finite ground setN, a weight function$$w: N \rightarrow \mathbb {R}_+$$ $w:N\to R_{+}$,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$ $f_1,f_2,\dots ,f_r$overNand requirements$$k_1,k_2,\ldots ,k_r$$ $k_1,k_2,\dots ,k_r$the goal is to find a minimum weight subset$$S \subseteq N$$ $S\subseteq N$such that$$f_i(S) \ge k_i$$ $f_i\left(S\right)\ge k_i$for$$1 \le i \le r$$ $1\le i\le r$. We refer to this problem asMulti-Submod-Coverand it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$ $r=1$Multi-Submod-Covergeneralizes the well-known Submodular Set Cover problem (Submod-SC), and it can also be easily reduced toSubmod-SC. A simple greedy algorithm gives an$$O(\log (kr))$$ $O(log(kr\left)\right)$approximation where$$k = \sum _i k_i$$ $k={\sum }_i{k}_i$and this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm forMulti-Submod-Coverthat covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$ $(1-1/e-\epsilon )$while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$ $O(\frac{1}{ϵ}logr)$in the cost. Second, we consider the special case when each$$f_i$$ $f_i$is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (Partial-SC), covering integer programs (CIPs) and multiple vertex cover constraints Bera et al. (Theoret Comput Sci 555:2–8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems. 

   more » « less
3. Lower bounds for incidences

   https://doi.org/10.1007/s00222-025-01331-2  

   Cohen, Alex; Pohoata, Cosmin; Zakharov, Dmitrii (March 2025, Inventiones mathematicae)

   Abstract Let$$p_{1},\ldots ,p_{n}$$ $p_1,\dots ,p_n$be a set of points in the unit square and let$$T_{1},\ldots ,T_{n}$$ $T_1,\dots ,T_n$be a set of$$\delta $$ $\delta$-tubes such that$$T_{j}$$ $T_j$passes through$$p_{j}$$ $p_j$. We prove a lower bound for the number of incidences between the points and tubes under a natural regularity condition (similar to Frostman regularity). As a consequence, we show that in any configuration of points$$p_{1},\ldots , p_{n} \in [0,1]^{2}$$ $p_1,\dots ,p_n\in {[0,1]}^2$along with a line$$\ell _{j}$$ ${\ell }_j$through each point$$p_{j}$$ $p_j$, there exist$$j\neq k$$ $j\ne k$for which$$d(p_{j}, \ell _{k}) \lesssim n^{-2/3+o(1)}$$ $d(p_j,{\ell }_k)\lesssim n^{-2/3+o\left(1\right)}$. It follows from the latter result that any set of$$n$$ $n$points in the unit square contains three points forming a triangle of area at most$$n^{-7/6+o(1)}$$ $n^{-7/6+o\left(1\right)}$. This new upper bound for Heilbronn’s triangle problem attains the high-low limit established in our previous work arXiv:2305.18253. 

   more » « less
4. VC-Dimension of Hyperplanes Over Finite Fields

   https://doi.org/10.1007/s00373-025-02909-6  

   Ascoli, Ruben; Betti, Livia; Cheigh, Justin; Iosevich, Alex; Jeong, Ryan; Liu, Xuyan; McDonald, Brian; Milgrim, Wyatt; Miller, Steven_J; Romero_Acosta, Francisco; et al (March 2025, Graphs and Combinatorics)

   Abstract Let$$\mathbb {F}_q^d$$ $F_q^d$be thed-dimensional vector space over the finite field withqelements. For a subset$$E\subseteq \mathbb {F}_q^d$$ $E\subseteq F_q^d$and a fixed nonzero$$t\in \mathbb {F}_q$$ $t\in F_q$, let$$\mathcal {H}_t(E)=\{h_y: y\in E\}$$ $H_t\left(E\right)=\{h_y:y\in E\}$, where$$h_y:E\rightarrow \{0,1\}$$ $h_y:E\to \{0,1\}$is the indicator function of the set$$\{x\in E: x\cdot y=t\}$$ $\{x\in E:x·y=t\}$. Two of the authors, with Maxwell Sun, showed in the case$$d=3$$ $d=3$that if$$|E|\ge Cq^{\frac{11}{4}}$$ $\left|E\right|\ge C{q}^{\frac{11}{4}}$andqis sufficiently large, then the VC-dimension of$$\mathcal {H}_t(E)$$ $H_t\left(E\right)$is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of$$\mathcal {H}_t(E)$$ $H_t\left(E\right)$isdwhenever$$E\subseteq \mathbb {F}_q^d$$ $E\subseteq F_q^d$with$$|E|\ge C_d q^{d-\frac{1}{d-1}}$$ $\left|E\right|\ge C_d{q}^{d-\frac{1}{d-1}}$. 

   more » « less
5. The immersion poset on partitions

   https://doi.org/10.1007/s10801-025-01380-z  

   Johnston, Lisa; Kenepp, David; Nguyen, Evuilynn; Paul, Digjoy; Schilling, Anne; Simone, Mary_Claire; Zhou, Regina (February 2025, Journal of Algebraic Combinatorics)

   Abstract We introduce the immersion poset$$({\mathcal {P}}(n), \leqslant _I)$$ $(P\left(n\right),{⩽}_I)$on partitions, defined by$$\lambda \leqslant _I \mu $$ $\lambda {⩽}_I\mu$if and only if$$s_\mu (x_1, \ldots , x_N) - s_\lambda (x_1, \ldots , x_N)$$ $s_{\mu }(x_1,\dots ,x_N)-s_{\lambda }(x_1,\dots ,x_N)$is monomial-positive. Relations in the immersion poset determine when irreducible polynomial representations of$$GL_N({\mathbb {C}})$$ $G{L}_N\left(C\right)$form an immersion pair, as defined by Prasad and Raghunathan [7]. We develop injections$$\textsf{SSYT}(\lambda , \nu ) \hookrightarrow \textsf{SSYT}(\mu , \nu )$$ $\mathrm{SSYT}(\lambda ,\nu )\hookrightarrow \mathrm{SSYT}(\mu ,\nu )$on semistandard Young tableaux given constraints on the shape of$$\lambda $$ $\lambda$, and present results on immersion relations among hook and two column partitions. The standard immersion poset$$({\mathcal {P}}(n), \leqslant _{std})$$ $(P\left(n\right),{⩽}_{\mathrm{std}})$is a refinement of the immersion poset, defined by$$\lambda \leqslant _{std} \mu $$ $\lambda {⩽}_{\mathrm{std}}\mu$if and only if$$\lambda \leqslant _D \mu $$ $\lambda {⩽}_D\mu$in dominance order and$$f^\lambda \leqslant f^\mu $$ $f^{\lambda }⩽f^{\mu }$, where$$f^\nu $$ $f^{\nu }$is the number of standard Young tableaux of shape$$\nu $$ $\nu$. We classify maximal elements of certain shapes in the standard immersion poset using the hook length formula. Finally, we prove Schur-positivity of power sum symmetric functions on conjectured lower intervals in the immersion poset, addressing questions posed by Sundaram [12]. 

   more » « less