More Like this

1. 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
2. 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
3. Transversality of holomorphic maps into hyperquadrics

   https://doi.org/10.1007/s00208-025-03134-5  

   Huang, Xiaojun; Zhu, Weixia (March 2025, Mathematische Annalen)

   Abstract We study holomorphic mapsFfrom a smooth Levi non-degenerate real hypersurface$$ M_{\ell }\subset {\mathbb {C}}^n $$ $M_{\ell }\subset C^n$into a hyperquadric$$ {\mathbb {H}}_{\ell '}^N $$ $H_{{\ell }^{\prime }}^N$with signatures$$ \ell \le (n-1)/2 $$ $\ell \le (n-1)/2$and$$ \ell '\le (N-1)/2,$$ ${\ell }^{\prime }\le (N-1)/2,$respectively. Assuming that$$ N - n < n - 1,$$ $N-n<n-1,$we prove that if$$ \ell = \ell ',$$ $\ell ={\ell }^{\prime },$thenFis either CR transversal to$$ {\mathbb {H}}_{\ell }^N $$ $H_{\ell }^N$at every point of$$ M_{\ell },$$ $M_{\ell },$or it maps a neighborhood of$$ M_{\ell } $$ $M_{\ell }$in$$ {\mathbb {C}}^n $$ $C^n$into$$ {\mathbb {H}}_{\ell }^N.$$ $H_{\ell }^N.$Furthermore, in the case where$$ \ell ' > \ell ,$$ ${\ell }^{\prime }>\ell ,$we show that ifFis not CR transversal at$$0\in M_\ell ,$$ $0\in M_{\ell },$then it must be transversally flat. The latter is best possible. 

   more » « less
4. 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
5. Wreath Macdonald polynomials as eigenstates

   https://doi.org/10.1007/s00029-025-01059-0  

   Wen, Joshua Jeishing (July 2025, Selecta Mathematica)

   Abstract We show that the wreath Macdonald polynomials for$$\mathbb {Z}/\ell \mathbb {Z}\wr \Sigma _n$$ $Z/\ell Z\wr {\Sigma }_n$, when naturally viewed as elements in the vertex representation of the quantum toroidal algebra$$U_{\mathfrak {q},\mathfrak {d}}(\ddot{\mathfrak {sl}}_\ell )$$ $U_{q,d}\left({\ddot{\mathrm{sl}}}_{\ell }\right)$, diagonalize its horizontal Heisenberg subalgebra. Our proof makes heavy use of shuffle algebra methods, and we also obtain a new proof of existence of wreath Macdonald polynomials. 

   more » « less