More Like this

1. Quantitative Rigidity of Differential Inclusions in Two Dimensions

   https://doi.org/10.1093/imrn/rnad108  

   Lamy, Xavier ; Lorent, Andrew ; Peng, Guanying ( May 2023 , International Mathematics Research Notices)

   Abstract For any compact connected one-dimensional submanifold $K\subset \mathbb R^{2\times 2}$ without boundary that has no rank-one connection and is elliptic, we prove the quantitative rigidity estimate $$\begin{align*} \inf_{M\in K}\int_{B_{1/2}}| Du -M |^2\, \textrm{d}x \leq C \int_{B_1} \operatorname{dist}^2(Du, K)\, \textrm{d}x, \qquad\forall u\in H^1(B_1;\mathbb R^2). \end{align*}$$This is an optimal generalization, for compact connected submanifolds of $\mathbb R^{2\times 2}$ without boundary, of the celebrated quantitative rigidity estimate of Friesecke, James, and Müller for the approximate differential inclusion into $SO(n)$. The proof relies on the special properties of elliptic subsets $K\subset{{\mathbb{R}}}^{2\times 2}$ with respect to conformal–anticonformal decomposition, which provide a quasilinear elliptic partial differential equation satisfied by solutions of the exact differential inclusion $Du\in K$. We also give an example showing that no analogous result can hold true in $\mathbb R^{n\times n}$ for $n\geq 3$. 

   more » « less
2. Harmonic Measure Is Absolutely Continuous with Respect to the Hausdorff Measure on All Low-Dimensional Uniformly Rectifiable Sets

   https://doi.org/10.1093/imrn/rnac109  

   David, G ; Mayboroda, S ( May 2022 , International Mathematics Research Notices)

   Abstract It was recently shown that the harmonic measure is absolutely continuous with respect to the Hausdorff measure on a domain with an $n-1$ dimensional uniformly rectifiable boundary, in the presence of now well-understood additional topological constraints. The topological restrictions, while mild, are necessary, as the counterexamples of Bishop and Jones show, and no analogues of these results have been available for higher co-dimensional sets. In the present paper, we show that for any $d<n-1$ and for any domain with a $d$-dimensional uniformly rectifiable boundary the elliptic measure of an appropriate degenerate elliptic operator is absolutely continuous with respect to the Hausdorff measure of the boundary. There are no topological or dimensional restrictions contrary to the aforementioned results. Résumé en Français. On sait que la mesure harmonique associée à un domaine de ${\mathbb {R}}^n$ dont la frontière est uniformément rectifiable de dimension $n-1$ est absolument continue par rapport à la mesure de surface, sous des conditions topologiques récemment bien comprises. Ces conditions, bien que faibles, sont nécessaires, comme l’ont montré des contre exemples de C. Bishop and P. Jones. On ne disposait pas jusqu’ici de résultats analogues lorsque la frontière est de codimension plus grande. On démontre dans cet article que lorsque la frontière est uniformément rectifiable de dimension $d < n-1$, la mesure elliptique associée à des opérateurs elliptiques dégénérés appropriés est absolument continue par rapport à la mesure de Hausdorff, sans avoir besoin de condition topologique supplémentaire. 

   more » « less
3. Green function estimates on complements of low-dimensional uniformly rectifiable sets

   https://doi.org/10.1007/s00208-022-02379-8  

   David, Guy ; Feneuil, Joseph ; Mayboroda, Svitlana ( March 2022 , Mathematische Annalen)

   It has been recently established in David and Mayboroda (Approximation of green functions and domains with uniformly rectifiable boundaries of all dimensions.arXiv:2010.09793) that on uniformly rectifiable sets the Green function is almost affine in the weak sense, and moreover, in some scenarios such Green function estimates are equivalent to the uniform rectifiability of a set. The present paper tackles a strong analogue of these results, starting with the “flagship degenerate operators on sets with lower dimensional boundaries. We consider the elliptic operators$$L_{\beta ,\gamma } =- {\text {div}}D^{d+1+\gamma -n} \nabla $$$L_{\beta ,\gamma }=-\text{div}{D}^{d+1+\gamma -n}\nabla$associated to a domain$$\Omega \subset {\mathbb {R}}^n$$$\Omega \subset R^n$with a uniformly rectifiable boundary$$\Gamma $$$\Gamma$of dimension$$d < n-1$$$d<n-1$, the now usual distance to the boundary$$D = D_\beta $$$D=D_{\beta }$given by$$D_\beta (X)^{-\beta } = \int _{\Gamma } |X-y|^{-d-\beta } d\sigma (y)$$$D_{\beta }{\left(X\right)}^{-\beta }={\int }_{\Gamma }{|X-y|}^{-d-\beta }d\sigma \left(y\right)$for$$X \in \Omega $$$X\in \Omega$, where$$\beta >0$$$\beta >0$and$$\gamma \in (-1,1)$$$\gamma \in (-1,1)$. In this paper we show that the Green functionGfor$$L_{\beta ,\gamma }$$$L_{\beta ,\gamma }$, with pole at infinity, is well approximated by multiples of$$D^{1-\gamma }$$$D^{1-\gamma }$, in the sense that the function$$\big | D\nabla \big (\ln \big ( \frac{G}{D^{1-\gamma }} \big )\big )\big |^2$$$|D\nabla (ln(\frac{G}{D^{1-\gamma }})){|}^2$satisfies a Carleson measure estimate on$$\Omega $$$\Omega$. We underline that the strong and the weak results are different in nature and, of course, at the level of the proofs: the latter extensively used compactness arguments, while the present paper relies on some intricate integration by parts and the properties of the “magical distance function from David et al. (Duke Math J, to appear).

    

   more » « less
4. From approximate to exact integer programming

   https://doi.org/10.1007/s10107-024-02084-1  

   Dadush, Daniel ; Eisenbrand, Friedrich ; Rothvoss, Thomas ( April 2024 , Mathematical Programming)

   Approximate integer programming is the following: For a given convex body$$K \subseteq {\mathbb {R}}^n$$$K\subseteq R^n$, either determine whether$$K \cap {\mathbb {Z}}^n$$$K\cap Z^n$is empty, or find an integer point in the convex body$$2\cdot (K - c) +c$$$2·(K-c)+c$which isK, scaled by 2 from its center of gravityc. Approximate integer programming can be solved in time$$2^{O(n)}$$$2^{O\left(n\right)}$while the fastest known methods for exact integer programming run in time$$2^{O(n)} \cdot n^n$$$2^{O\left(n\right)}·n^n$. So far, there are no efficient methods for integer programming known that are based on approximate integer programming. Our main contribution are two such methods, each yielding novel complexity results. First, we show that an integer point$$x^* \in (K \cap {\mathbb {Z}}^n)$$$x^{\ast }\in (K\cap Z^n)$can be found in time$$2^{O(n)}$$$2^{O\left(n\right)}$, provided that theremaindersof each component$$x_i^* \mod \ell $$$x_i^{\ast }mod\ell$for some arbitrarily fixed$$\ell \ge 5(n+1)$$$\ell \ge 5(n+1)$of$$x^*$$$x^{\ast }$are given. The algorithm is based on acutting-plane technique, iteratively halving the volume of the feasible set. The cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a$$2^{O(n)}n^n$$$2^{O\left(n\right)}{n}^n$algorithm for general integer programming. This matches the current best bound of an algorithm by Dadush (Integer programming, lattice algorithms, and deterministic, vol. Estimation. Georgia Institute of Technology, Atlanta, 2012) that is considerably more involved. Our algorithm also relies on a newasymmetric approximate Carathéodory theoremthat might be of interest on its own. Our second method concerns integer programming problems in equation-standard form$$Ax = b, 0 \le x \le u, \, x \in {\mathbb {Z}}^n$$$Ax=b,0\le x\le u,x\in Z^n$. Such a problem can be reduced to the solution of$$\prod _i O(\log u_i +1)$$${\prod }_{i}O(log{u}_i+1)$approximate integer programming problems. This implies, for example thatknapsackorsubset-sumproblems withpolynomial variable range$$0 \le x_i \le p(n)$$$0\le x_i\le p\left(n\right)$can be solved in time$$(\log n)^{O(n)}$$${(logn)}^{O\left(n\right)}$. For these problems, the best running time so far was$$n^n \cdot 2^{O(n)}$$$n^n·2^{O\left(n\right)}$.

    

   more » « less
5. Generalized Parking Function Polytopes

   https://doi.org/10.1007/s00026-023-00671-1  

   Hanada, Mitsuki ; Lentfer, John ; Vindas-Meléndez, Andrés R. ( November 2023 , Annals of Combinatorics)

   A classical parking function of lengthnis a list of positive integers$$(a_1, a_2, \ldots , a_n)$$$(a_1,a_2,\dots ,a_n)$whose nondecreasing rearrangement$$b_1 \le b_2 \le \cdots \le b_n$$$b_1\le b_2\le \cdots \le b_n$satisfies$$b_i \le i$$$b_i\le i$. The convex hull of all parking functions of lengthnis ann-dimensional polytope in$${\mathbb {R}}^n$$$R^n$, which we refer to as the classical parking function polytope. Its geometric properties have been explored in Amanbayeva and Wang (Enumer Combin Appl 2(2):Paper No. S2R10, 10, 2022) in response to a question posed by Stanley (Amer Math Mon 127(6):563–571, 2020). We generalize this family of polytopes by studying the geometric properties of the convex hull of$${\textbf{x}}$$$x$-parking functions for$${\textbf{x}}=(a,b,\dots ,b)$$$x=(a,b,\cdots ,b)$, which we refer to as$${\textbf{x}}$$$x$-parking function polytopes. We explore connections between these$${\textbf{x}}$$$x$-parking function polytopes, the Pitman–Stanley polytope, and the partial permutahedra of Heuer and Striker (SIAM J Discrete Math 36(4):2863–2888, 2022). In particular, we establish a closed-form expression for the volume of$${\textbf{x}}$$$x$-parking function polytopes. This allows us to answer a conjecture of Behrend et al. (2022) and also obtain a new closed-form expression for the volume of the convex hull of classical parking functions as a corollary.

    

   more » « less