Metric Geometry
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Wednesday 22 April
The medial axis of a closed set is well established tool in pattern recognition, cherished for its power of reconstruction of domains. In this article we fill this gap answering the question which sets precisely are reconstructible from the medial axis information. We do not assume any additional structure of considered sets besides them being closed in n-dimensional Euclidean space.
Analysis of PDEs
Global spherically symmetric solutions to the isothermal compressible Navier-Stokes equations with far-field vacuum
In this paper, we consider the global spherically symmetric strong solutions to the compressible Navier-Stokes equations with far-field vacuum and density-dependent degenerate viscosity, following the framework proposed by Bresch-Vasseur-Yu \cite{B-V-Y 2021}. For the 1D Navier-Stokes equations, Wen-Zhang \cite{W-Z SIAM 2025} considered the Cauchy problem which established the dependence relationship $\gamma-\delta-\frac{1}{p}\ge0$ within the $W^{2,p}(\mathbb{R})$ and $p\ge 2$. In this paper, we establish the global existence and uniqueness of strong solutions in $H^2([a,+\infty))$, $a>0$. In particular, we remove the restriction relating ($\gamma$, $\delta$, $p$), and instead assume that $\delta > 0.7427$. This result can be regarded as the first one on spherically symmetric strong solutions to the 3D Navier-Stokes equations with density-dependent viscosity proposed in \cite{B-V-Y 2021} and far-field vacuum.
Read the full abstract
Combinatorics
On the structural growth of bipartite Ramsey numbers
Bipartite Ramsey numbers is the smallest size of a complete bipartite graph $K_{N,N}$ such that every edge-coloring with a given number of colors inevitably yields a monochromatic copy of a prescribed bipartite graph. While exact values have been determined for certain specific graphs, the general asymptotic behavior of these numbers in terms of structural graph parameters remains poorly understood. In this paper, we investigate structure-dependent growth phenomena in bipartite Ramsey theory. For a fixed bipartite graph $G$ with $p$ vertices and $q$ edges, we first establish a lower bound of the form $\operatorname{br}(G,K_{n,n}) > C \bigl(\frac{n}{\log n}\bigr)^{(q-1)/(p-2)}$. As a corollary, we show that sufficiently dense bipartite graphs fail to be bipartite Ramsey size linear. Turning to even cycles and complete bipartite graphs, we obtain an upper bound on the multicolor bipartite Ramsey number $\operatorname{br}_k(C_{2t};K_{n,n}) \le c_{t,k}\, n^2/\log^2 n$, which follows from classical estimates for Zarankiewicz numbers together with a double-counting argument. Building on this result, we further derive a refined linear upper bound of the form $\operatorname{br}(C_{2t},G) \le \frac{m}{2} + \frac{29t\sqrt{m}}{2}$, valid for any connected bipartite graph $G$ with $m$ edges and no isolated vertices.
Read the full abstract
Number Theory
p-adic elliptic polylogarithms and cubic Chabauty
The Chabauty–Coleman–Kim method, under favourable circumstances, describes the set of integral points of a hyperelliptic curve inside the $p$-adic zeroes of certain transcendental functions. For an elliptic curve of Mordell–Weil rank one, the Chabauty–Coleman–Kim set in depth 2 is given by the zeroes of a (finite union of) quadratic polynomial(s) in the $p$-adic logarithm of the elliptic curve and the local $p$-adic height at $p$. Here, we give an explicit formula for a finite set containing the Chabauty–Coleman–Kim set in depth 3 for an elliptic curve of rank at most 2 under an assumption on non-vanishing of a special value of a $p$-adic $L$-function. The finite set is given by the zeroes of a polynomial in $p$-adic elliptic polylogarithms. We use these formulas to verify new instances of Kim's conjecture.
Read the full abstract
Probability
The Legendre structure of the TAP complexity for the Ising spin glass
We study the complexity of the Thouless-Anderson-Palmer (TAP) free energy for Ising spin glasses with a general mixed p-spin covariance, working with the generalized TAP functional of Chen, Panchenko, and Subag. We formulate three conjectures about the complexity (i.e. number of critical points). First, the annealed complexity is given by the Legendre transform of a variational functional constructed from the Parisi formula subject to a constraint on the overlap mass at zero, thereby establishing a precise link between the enumeration of TAP states and the large-deviation rate function of the partition function. Second, the quenched complexity is governed by the Legendre transform of a closely related functional in which the mass up to – but not including – the supremum of the support is constrained. Third, TAP states at any non-equilibrium free-energy level are organized into an ultrametric hierarchy, with ancestor states at other levels appearing only in subexponential number. Using a Kac-Rice computation combined with a supersymmetric ansatz, we establish a lower bound on the annealed complexity that matches the prediction of the first conjecture. We further extend the analysis to a conditional setting in which a hierarchical "skeleton" of ancestors is prescribed, providing additional evidence in support of the second and third conjectures.
Read the full abstract
Optimization and Control
Importance Sampling in Expensive Finite-Sum Optimization via Contextual Bandit Methods
In computational science workflows, it is often the case that 1) objective functions for optimization involve multiple simulation outputs, and 2) those simulations can be performed (at least partially) in parallel. In this work, we reexamine past work on a class of randomized algorithms, stochastic average model (SAM) methods. SAM methods are conceptually similar to stochastic average gradient methods, and effectively require that only randomized subsets of simulation outputs be locally modeled in each iteration of a model-based optimization method. This work focuses on the question of how best to perform this randomization of subset selection, especially in settings where there exists useful side information such as alternative lower-fidelity simulations, pre-trained emulators or domain expertise from humans or AI models. In particular, we consider the problem of generating sampling distributions for SAM methods as a contextual bandit problem and we apply the Exponential weights algorithm for Exploration and Exploitation with Experts (Exp4). We provide some preliminary numerical results on synthetic problems.
Read the full abstract
Mathematical Physics
Absence of Ballistic Transport in Quantum Walks with Asymptotically Reflecting Sites
We prove general sufficient conditions for zero velocity in position dependent one-dimensional quantum walks, and hence for the absence of ballistic transport. Our starting point is a general a priori upper bound on the velocity, formulated in terms of sparse bi-infinite sequences of sites, their gap structure, and the corresponding local coin parameters. This estimate yields several deterministic criteria for zero velocity that depend only on the behavior of suitable coin entries along selected subsequences and are independent of the values of the coins elsewhere. We also discuss the random case as an application of the general approach. All of our results remain valid in the CMV setting.
Read the full abstract
Number Theory
On sums of two squares and a basis of order $2$
Let $\mathcal{R}$ denote the set of integers $n$ that can be represented as the sum $n = x^2 + y^2$ with $(x,y) = 1$. Let $a$ and $b$ be integers with $a>0$, $a \nmid b$. We show that for sufficiently large positive integer $N$ there are two strings of consecutive positive integers $I_{1}=\{n_1-m,\ldots, n_1+m\}$ and $I_{2}=\{n_2-m, \ldots, n_2+m\}$ such that $m = [(\log N) (\log \log N)^{1/325565}]$, $I_{1}\cup I_{2} \subset [1, N]$, $N = n_1 + n_2$, and for any $n\in I_{1}\cup I_{2}$ at least one of $n$ or $an+b$ does not lie in $\mathcal{R}$. In particular, we have $n(an+b)\notin \mathcal{R}$ for all $n\in I_{1}\cup I_{2}$.
Read the full abstract
Rings and Algebras
Trivial extensions of Koszul Artin-Schelter regular algebras
Let $S$ be an $\mathbb N$-graded Koszul Artin-Schelter regular algebra and let $\sigma$ be a graded algebra automorphism of $S$. We study the stable category of graded maximal Cohen-Macaulay modules over the trivial extension algebra $S\ltimes S_\sigma(-1)$. We show that this category is triangle equivalent to the bounded derived category of finitely generated (ungraded) modules over the Koszul dual algebra of the Zhang twist $S^{\sigma^{-1}}$. In the connected graded case, we also obtain a criterion for when two such stable categories are triangle equivalent, and show that such an equivalence induces an equivalence between the categories of graded modules over the original algebras.
Read the full abstract
Commutative Algebra
Multiple Tor modules: rigidity and Mayer-Vietoris spectral sequences
We extend some properties of a pair of ideals described in terms of Tor modules to any number of ideals, including the well-known rigidity property. Those extensions require the development of a homological theory for spectral sequences arising from multiple complexes. Out of this theory, two new complexes associated with quotients by sums and quotients by products of the given ideals emerge, and their homologies are related via the Tor-independence property. In the multigraded setting, we describe the support regions of Tor modules for quotients by sums and products of ideals generated by variables in terms of each other.
Read the full abstract
Information Theory
Minimum Energy per Bit of Unsourced Multiple Access with Location-Based Codebook Partitioning
We derive finite-blocklength bounds on the minimum achievable energy per bit over a Gaussian unsourced multiple access (UMA) channel in the presence of heterogeneous path-loss conditions. We consider a setting in which the path loss is known to the users, which enables the use of location-based codebook partitioning [Çakmak et al., 2025]. Through numerical simulations and a large-system analysis based on the replica method, we quantify the performance gain of this strategy relative to the conventional UMA approach in which all users employ a common codebook.
Read the full abstract
Algebraic Geometry
Interacting Multi-Node Conifold Light Sectors
We study finite-node conifold degenerations of Calabi–Yau threefolds from the point of view of interacting light sectors. Although each ordinary double point contributes a rank-one local vanishing sector, the corrected global object need not assemble as a freely independent sum of nodewise pieces. Using the corrected perverse and mixed-Hodge-module degeneration package, the global gluing law for corrected extension classes, and the rigid-flexible atom decomposition on the \(F\)-bundle side, we define an interacting multi-node light-sector package and prove a block-reduced structure theorem. In the block-separated cycle family, the finite-node package separates into two logically distinct layers: relation collapse, controlled by a common relation lattice on the corrected-extension, smoothing, and resolution sides, and residual interaction among the surviving global sectors, controlled by a reduced block interaction matrix on the transport and atom sides. The result isolates the geometric and Hodge-theoretic precursor of coupled conifold light states and provides the mathematical input for a later multi-node reformulation of Strominger's conifold mechanism.
Read the full abstract
Mathematical Physics
Variational Principles for Shock Dynamics in Compressible Euler Flows
Hamilton's principle plays a central role in fluid mechanics as a fundamental tool for deriving governing equations, analyzing conservation laws, and designing structure-preserving numerical schemes. However, its classical formulation is restricted to smooth solutions and does not directly accommodate shock discontinuities. Addressing this limitation within a variational framework has long been a challenging issue. In this paper, we develop a variational framework that extends Hamilton's principle to shock solutions in compressible fluid dynamics. For the barotropic Euler equations, we introduce a modified action principle that incorporates additional contributions localized at discontinuities. This allows the Rankine–Hugoniot conditions for mass and momentum to emerge directly from unrestricted variations, without imposing continuity across shocks. The additional term admits a natural interpretation as a dissipation potential, linking the variational structure to energy loss at shocks. We then extend the approach to the full compressible Euler equations. Using a variational formulation of nonequilibrium thermodynamics together with suitable variational and phenomenological constraints, we recover the Rankine–Hugoniot relations for mass, momentum, and energy. This yields a unified variational description of shock dynamics in compressible fluids and highlights a fundamental distinction between barotropic and full compressible models in the treatment of energy and entropy at discontinuities.
Read the full abstract
Probability
Distributional Statistical Models: Weak Moments, Cumulants, and a Central Limit Theorem
Many important statistical models fall outside classical moment-based methods due to the non-existence of moments or moment generating functions. We propose a generalised probabilistic framework in which a probability law is represented by a tempered distribution $T \in \mathcal{S}'$, on the same footing as a density, a distribution function, or a characteristic function. Information about the law is extracted by evaluating $T$ on test functions regularised by a given positive Schwartz kernel $\varphi \in \mathcal{S}$ – the kernel serving as a probe, not as part of the law. Expectations are defined via the action of distributions on regularised test functions, yielding well-defined weak moments, weak characteristic functions, and weak cumulants of all orders. These extend classical quantities and retain key algebraic properties such as additivity under independence and natural affine transformation rules. The main results are: (i) a systematic algebra of weak cumulants; (ii) a weak moment problem where existence of all moments holds unconditionally and uniqueness depends on the kernel, with uniqueness results under Gaussian kernels (via Hermite completeness), positive Schwartz kernels with an exponential tail bound and square-integrable densities (via a Carleman-type criterion), and kernels with exponential decay (via Denjoy-Carleman quasi-analyticity); and (iii) a weak central limit theorem formulated as convergence of weak characteristic functions to a Gaussian limit, covering cases where the classical theorem fails. The framework is illustrated with Student's $t$, stable, and hyperbolic distributions. As a statistical consequence, the weak first moment yields a consistent estimator of the location parameter in the Cauchy model, where no classical moment-based estimator exists. A full statistical treatment is given in a companion paper.
Read the full abstract
Metric Geometry
A weighted angle distance on strings
We define a multi-scale metric $d_\rho$ on strings by aggregating angle distances between all $n$-gram count vectors with exponential weights $\rho^n$. We benchmark $d_\rho$ in DBSCAN clustering against edit and $n$-gram baselines, give a linear-time suffix-tree algorithm for evaluation, prove metric and stability properties (including robustness under tandem-repeat stutters), and characterize isometries.
Read the full abstract
Probability
The Ising Model on a Two-Community Stochastic Block Model
We study the Ising model on a two-community stochastic block model, where $n$ spins are split into two equal groups with inter-community interaction parameter $\alpha_n\in[0,1]$. We provide a complete characterization of the phase diagram and show that, almost surely with respect to the graph realization, the model undergoes a uniqueness/non-uniqueness phase transition of the Gibbs measure. In particular, in the supercritical regime, the law of the magnetization vector of the two communities converges to a mixture of Dirac measures that, depending on whether $\alpha_n\gg 1/n$ or $\alpha_n\lesssim1/n$, is supported on two or four points, with possibly different weights. In the uniqueness region, we further analyze the fluctuations of the magnetization vector in the subcritical regime and we prove a quenched central limit theorem.
Read the full abstract
Probability
Rates of forgetting for the sequentially Markov coalescent
The sequentially Markov coalescent (SMC) is a Markov jump process which models correlations in local genealogies across a chromosome. It has been used as a theoretical tool for studying linkage disequilibrium and identity-by-descent, and it also forms the basis of a class of statistical procedures for estimating population history and inferring ancestry. In this paper, we study the rate at which SMC forgets its initial condition in the pairwise setting. For the embedded jump chain, we prove geometric ergodicity in total variation, with explicit constants. For the continuous process, by contrast, the total variation distance from stationarity decays as $\asymp 1/\ell$ in genetic distance $\ell$. We obtain analogous results for the closely related SMC' process using a novel time-change argument. One application of these results is to justify heuristic approximations used in the literature that treat distant loci as evolving independently.
Read the full abstract
Symplectic Geometry
A note on the cardinality of Lagrangian packings
Given a symplectic manifold, can one pack uncountably many Lagrangian submanifolds in a given Hamiltonian isotopy class of this symplectic manifold? We address $C^\infty$ and $C^0$ versions of this question.
Probability
Structured perturbations of tridiagonal twisted Toeplitz matrices
Twisted Toeplitz matrices constitute a generalization of Toeplitz matrices in the sense that the entries on each diagonal no longer need to be constant, but are given by the values of a continuous function on a partition of $[0,1]$. We study the limiting statistical distribution of the eigenvalues of matrices of the form $R_n(a) = T_n(a) + \sigma_n X_n$, where $T_n(a)$ is a sequence of non-Hermitian tridiagonal twisted Toeplitz matrices, $X_n$ is a sequence of tridiagonal random matrices whose entries have mean $0$ and finite variance, and $\sigma_n\to0$. The limiting distribution turns out to be a two-dimensional measure which is in general different from the push-forward of the Lebesgue measure by the symbol. We also explain how the results could extend to banded non-Hermitian twisted Toeplitz matrices.
Read the full abstract
Dynamical Systems · Cross-listed from cs.LG
Too Sharp, Too Sure: When Calibration Follows Curvature
Modern neural networks can achieve high accuracy while remaining poorly calibrated, producing confidence estimates that do not match empirical correctness. Yet calibration is often treated as a post-hoc attribute. We take a different perspective: we study calibration as a training-time phenomenon on small vision tasks, and ask whether calibrated solutions can be obtained reliably by intervening on the training procedure. We identify a tight coupling between calibration, curvature, and margins during training of deep networks under multiple gradient-based methods. Empirically, Expected Calibration Error (ECE) closely tracks curvature-based sharpness throughout optimization. Mathematically, we show that both ECE and Gauss–Newton curvature are controlled, up to problem-specific constants, by the same margin-dependent exponential tail functional along the trajectory. Guided by this mechanism, we introduce a margin-aware training objective that explicitly targets robust-margin tails and local smoothness, yielding improved out-of-sample calibration across optimizers without sacrificing accuracy.
Read the full abstract
Statistics Theory
E-values and sequential power-one tests for monotonicity and unimodality
We develop e-values and e-processes testing the null hypothesis that a distribution over nonnegative integers is monotone, and that a distribution over integers is unimodal given a certain mode. Our e-processes lead to tests of power one under any non-null distribution with a sequence of i.i.d. observations, and consistent set-valued mode estimators that eventually equal the true set of modes. Additionally, we characterize the set of all e-values, and therefore the set of all valid tests, with one monotone and unimodal observation, as well as the most powerful e-value for a fixed alternative. We then show that many of our results can be generalized to continuous random variables, relating them to the existing results in the shape-constrained inference literature.
Read the full abstract
Information Theory · Cross-listed from eess.SY
Model Predictive Communication for Timely Status Updates in Low-Altitude Networks
Timely information delivery in low-altitude networks is critical for many time-sensitive applications, such as unmanned aerial vehicle (UAV) navigation, inspection, and surveillance. The key challenge lies in balancing three competing factors: stringent data freshness requirements, UAV onboard energy consumption, and interference with terrestrial services. Addressing this challenge requires not only efficient power and channel allocation strategies but also effective communication timing over the entire operation horizon. In this work, we propose a model predictive communication (MPComm) framework, enabled by advanced channel sensing techniques, in which the channel conditions that the UAV will experience are largely predictable. Within this framework, we formulate a constrained bi-objective optimization problem to achieve a desired trade-off between energy consumption and terrestrial channel occupation, subject to a strict timeliness constraint. We solve this problem using Pareto analysis and show that the original non-convex, mixed-integer problem can be decomposed into a two-layer structure: the outer layer determines the optimal communication timing, while the inner layer determines the optimal power and channel allocation for each communication interval. An efficient algorithm for the inner problem is developed using non-convex analysis, with asymptotic optimality guarantees, while the outer problem is solved optimally via a simple graph search, with edges characterized by inner solutions. The proposed approach applies to a broad class of problem variants, including objective transformations and single-objective specializations. Numerical results demonstrate the efficiency of the proposed solution, achieving up to a six-fold reduction in terrestrial channel occupation and a 6dB energy saving compared to benchmark schemes.
Read the full abstract
Numerical Analysis
Admissible Lax-Wendroff Flux Reconstruction Method with Automatic Differentiation on Adaptive Curved Meshes for Relativistic Hydrodynamics
The relativistic hydrodynamics (RHD) equations can give rise to solutions which have shocks, contact discontinuities, and other sharp structures, which interact and evolve over time. Capturing these sharp waves effectively requires a mesh with high resolution, making the scheme computationally expensive. In this work, adaptive mesh refinement is used with the high-order Lax-Wendroff flux reconstruction (LWFR) method to solve the system of RHD equations, which is closed with general Synge-type equations of state. To make the scheme Jacobian-free, the idea of automatic differentiation is incorporated for computing the temporal derivatives in the time average flux approximations. The high-order method is blended with an admissible low-order method at the subcell level to control the Gibbs oscillations and maintain the physical admissibility of the solution. Finally, several test cases involving high Lorentz factors, low densities, low pressures, strong shock waves, and other discontinuities are used to demonstrate the robustness, accuracy, and effectiveness of the proposed method. These simulations are performed with AMR using various linear and curved meshes to show the scheme's efficiency and ability to handle complex geometries.
Read the full abstract
Representation Theory
Almost finitary birepresentation theory and applications to affine Soergel bimodules
In this article, we develop a generalization of finitary birepresentation theory applicable to Soergel bimodules for infinite Coxeter groups. We establish a reduction process for the classification of simple birepresentations of almost finitary bicategories, and consider in detail the case of Soergel bimodules in extended affine type A.
Read the full abstract
Category Theory
Topological Dualities for Modal Algebras
We display a family of Stone-type dualities linking categories of frames carrying pairs of modal operators to categories of spaces carrying a binary relation. Different notions of morphism used on the relational side lead to significant variations in the point construction. We show how the situation simplifies in the case of semicontinuous relations, allowing for straightforward correspondences between modal axioms and relational properties.
Read the full abstract
Functional Analysis
Geometric properties of Euclidean domains supporting trace inequalities
We investigate the geometric behavior of $\tau(E)$ for bounded finite-perimeter sets $E \subset \mathbb R^n$, where $\tau(E)$ is the trace constant introduced by Figalli–Maggi–Pratelli [Invent. Math. 2010]. This quantity is a key ingredient in proving a quantitative isoperimetric inequality with the optimal exponent. We first show that for every $\epsilon>0$ one can find a bounded open set $\Omega \subset \mathbb R^n$ that is very close to the unit ball $\mathbb B^n$ in the sense that $$ \tau(\mathbb B^n)>\tau(\Omega)>\tau(\mathbb B^n)-\epsilon \quad \text{and} \quad P(\Omega \Delta \mathbb B^n)\le C(n)\epsilon, $$ while at the same time the complement of $\Omega$ has infinitely many connected components. Thus, $\tau(\Omega)$ can be made arbitrarily close to $\tau(\mathbb B^n)$ even when $\Omega$ has highly intricate geometry. We then establish, under a mild additional hypothesis, the equivalence between a condition formulated in terms of $\tau$ and two classical criteria from the literature for open sets that admit trace inequalities. As a consequence, we obtain the John-type characterization of domains that support a trace inequality, assuming the ball separation property.
Read the full abstract
Analysis of PDEs
Widely degenerate anisotropic diffusion: local boundedness and semicontinuity
We investigate the regularity of local weak solutions to evolution equations of the form \[ \partial_{t}u\,=\,\sum_{i=1}^{n}\,\partial_{x_{i}}\left[a_{i}(x,t)\,(\vert\partial_{x_{i}}u\vert-\delta_{i})_{+}^{p_{i}-1}\,\frac{\partial_{x_{i}}u}{\vert\partial_{x_{i}}u\vert}\right]\,\,\,\,\,\,\,\,\,\,\mathrm{in}\,\,\,\Omega_{T}\,=\,\Omega\times(0,T)\,, \] where $\Omega$ is a bounded domain in $\mathbb{R}^{n}$ with $n\geq2$, the coefficients $a_{i}$ are measurable and bounded, $p_{i}>1$ and $\delta_{i}\geq0$ are fixed parameters. Under suitable assumptions on the exponents $p_{i}$, we first show that the local boundedness of weak solutions follows from their membership in an appropriate non-homogeneous parabolic De Giorgi class. We then establish the existence of semicontinuous representatives for local weak sub(super)-solutions. Our analysis extends analogous results available for less degenerate operators and generalizes the local boundedness results obtained in [7] to fully anisotropic, widely degenerate parabolic PDEs with non-smooth coefficients depending additionally on the space-time variables $(x,t)$, whose growth is governed by a family of exponents $p_{i}$ rather than by a single exponent.
Read the full abstract
Group Theory
Enumeration of skew morphisms of cyclic $2$-groups
A skew morphism of a finite group $B$ is a permutation of $B$ fixing the identity and satisfying $\varphi(xy) = \varphi(x)\varphi^{i_x}(y)$ for some integers $i_x$ indexed by $x \in B$. The enumeration of skew morphisms of finite cyclic groups remains an open problem. The most substantial progress to date concerns cyclic $p$-groups with $p$ odd, for which a full classification and enumeration was obtained by Kovács and Nedela. In this paper we treat the remaining case $p = 2$, giving a complete classification and enumeration of skew morphisms of finite cyclic $2$-groups. Writing $\mathrm{Skew}(n)$ for the number of skew morphisms of $\mathbb{Z}_n$, we prove that $\mathrm{Skew}(2^e) = 4\,\mathrm{Skew}(2^{e-1}) - 4$ for each $e \geq 4$, and that $\mathrm{Skew}(2^e) = (7 \cdot 4^{e-2} + 8)/6$ for each $e \geq 3$. This completes the enumeration of skew morphisms for all cyclic $p$-groups.
Read the full abstract
Combinatorics
The Mihail-Vazirani conjecture and strong edge-expansion in random $0/1$ polytopes
We study the edge-expansion of the graph of a random $0/1$ polytope $P^d_p$, defined as the convex hull of a random subset of the points in $\{0,1\}^d$ where every point is retained independently and with probability $p$. This problem was introduced more than twenty years ago in a work of Gillmann and Kaibel, and has been extensively studied ever since. We prove that, for every fixed $\varepsilon>0$ and every $p\in(0,1-\varepsilon]$, with high probability the graph of $P^d_p$ has edge-expansion $\Theta(d)$. This improves the previously best known bound due to Ferber, Krivelevich, Sales and Samotij, and verifies, in a strong form, the celebrated Mihail-Vazirani conjecture for random $0/1$ polytopes. Although the expansion factor $\Theta(d)$ is typically best possible for $p\ge 1/2+\varepsilon$, we also show that the behaviour changes drastically at $p=1/2$. Namely, for every fixed $\varepsilon>0$ and every integer $k\ge 2$, if $p\le 1/2-\varepsilon$, then with high probability the graph of $P^d_p$ has edge-expansion $\Omega(d^k)$. Thus, random $0/1$ polytopes exhibit an interesting phase transition at $p=1/2$.
Read the full abstract
Combinatorics
A resolution of Erdős Problem #190 via Erdős-Lovász, BCT, and Baker-Harman-Pintz
Let H(k) be the smallest N such that every finite coloring of [N] contains a monochromatic or rainbow k-term arithmetic progression. Erdős and Graham asked whether $H(k)^{1/k}/k \to \infty$ (Problem #190 of the Erdős Problems database). We prove that there is an absolute constant $k_0 \ge 2$ such that for all $k \ge k_0$, \[ H(k)^{1/k}/k \ge (1/e - \varepsilon(k)) \cdot k/\log k, \qquad \varepsilon(k) = O(k^{-0.475} \log k) \to 0 \text{ as } k \to \infty; \] in particular $H(k)^{1/k}/k = \Omega(k/\log k)$ and $\lim_{k\to\infty} H(k)^{1/k}/k = \infty$, resolving the positive direction of the Erdős-Graham question. The argument combines three standard ingredients – the symmetric Lovász Local Lemma applied to the k-AP hypergraph on $[N]$, the restricted form of the Blankenship-Cummings-Taranchuk recurrence, and the Baker-Harman-Pintz prime-gap theorem – together with the pigeonhole reduction $H(k) \ge W(k-1,k)$, and uses BHP as the only analytic black box. Previous applications of Erdős-Lovász had fixed $r$; the improvement here is that the $r^{k-1}$ base dominates once one allows the color count $r_0 = \lfloor k / \log k \rfloor$ to grow with $k$. No matching upper bound on $H(k)^{1/k}/k$ is known.