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.


Title: An Isoperimetric Inequality for Hamming Balls and Local Expansion in Hypercubes
We prove a vertex isoperimetric inequality for the $$n$$-dimensional Hamming ball $$\mathcal{B}_n(R)$$ of radius $$R$$. The isoperimetric inequality is sharp up to a constant factor for sets that are comparable to $$\mathcal{B}_n(R)$$ in size. A key step in the proof is a local expansion phenomenon in hypercubes.  more » « less
Award ID(s):
1953946 2127650
PAR ID:
10405332
Author(s) / Creator(s):
;
Date Published:
Journal Name:
The Electronic Journal of Combinatorics
Volume:
29
Issue:
1
ISSN:
1077-8926
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract We prove an inequality that unifies previous works of the authors on the properties of the Radon transform on convex bodies including an extension of the Busemann–Petty problem and a slicing inequality for arbitrary functions. Let $$K$$ and $$L$$ be star bodies in $${\mathbb R}^n,$$ let $0<k<n$ be an integer, and let $f,g$ be non-negative continuous functions on $$K$$ and $$L$$, respectively, so that $$\|g\|_\infty =g(0)=1.$$ Then $$\begin{align*} & \frac{\int_Kf}{\left(\int_L g\right)^{\frac{n-k}n}|K|^{\frac kn}} \le \frac n{n-k} \left(d_{\textrm{ovr}}(K,\mathcal{B}\mathcal{P}_k^n)\right)^k \max_{H} \frac{\int_{K\cap H} f}{\int_{L\cap H} g}, \end{align*}$$where $|K|$ stands for volume of proper dimension, $$C$$ is an absolute constant, the maximum is taken over all $(n-k)$-dimensional subspaces of $${\mathbb R}^n,$$ and $$d_{\textrm{ovr}}(K,\mathcal{B}\mathcal{P}_k^n)$$ is the outer volume ratio distance from $$K$$ to the class of generalized $$k$$-intersection bodies in $${\mathbb R}^n.$$ Another consequence of this result is a mean value inequality for the Radon transform. We also obtain a generalization of the isomorphic version of the Shephard problem. 
    more » « less
  2. Abstract For every$$n\ge 2$$ n 2 , thesurface Houghton group$${\mathcal {B}}_n$$ B n is defined as the asymptotically rigid mapping class group of a surface with exactlynends, all of them non-planar. The groups$${\mathcal {B}}_n$$ B n are analogous to, and in fact contain, the braided Houghton groups. These groups also arise naturally in topology: every monodromy homeomorphism of a fibered component of a depth-1 foliation of closed 3-manifold is conjugate into some$${\mathcal {B}}_n$$ B n . As countable mapping class groups of infinite type surfaces, the groups$$\mathcal {B}_n$$ B n lie somewhere between classical mapping class groups and big mapping class groups. We initiate the study of surface Houghton groups proving, among other things, that$$\mathcal {B}_n$$ B n is of type$$\text {F}_{n-1}$$ F n - 1 , but not of type$$\text {FP}_{n}$$ FP n , analogous to the braided Houghton groups. 
    more » « less
  3. We investigate the behavior of higher-form symmetries at variousquantum phase transitions. We consider discrete 1-form symmetries, whichcan be either part of the generalized concept “categorical symmetry”(labelled as \tilde{Z}_N^{(1)} Z ̃ N ( 1 ) )introduced recently, or an explicit Z_N^{(1)} Z N ( 1 ) 1-form symmetry. We demonstrate that for many quantum phase transitionsinvolving a Z_N^{(1)} Z N ( 1 ) or \tilde{Z}_N^{(1)} Z ̃ N ( 1 ) symmetry, the following expectation value \langle \left( O_\mathcal{C}\right)^2 \rangle ⟨ ( O 𝒞 ) 2 ⟩ takes the form \langle \left( \log O_\mathcal{C} \right)^2 \rangle \sim - \frac{A}{\epsilon} P + b \log P ⟨ ( log O 𝒞 ) 2 ⟩ ∼ − A ϵ P + b log P , where O_\mathcal{C} O 𝒞 is an operator defined associated with loop \mathcal{C} 𝒞 (or its interior \mathcal{A} 𝒜 ),which reduces to the Wilson loop operator for cases with an explicit Z_N^{(1)} Z N ( 1 ) 1-form symmetry. P P is the perimeter of \mathcal{C} 𝒞 ,and the b \log P b log P term arises from the sharp corners of the loop \mathcal{C} 𝒞 ,which is consistent with recent numerics on a particular example. b b is a universal microscopic-independent number, which in (2+1)d ( 2 + 1 ) d is related to the universal conductivity at the quantum phasetransition. b b can be computed exactly for certain transitions using the dualitiesbetween (2+1)d ( 2 + 1 ) d conformal field theories developed in recent years. We also compute the"strange correlator" of O_\mathcal{C} O 𝒞 : S_{\mathcal{C}} = \langle 0 | O_\mathcal{C} | 1 \rangle / \langle 0 | 1 \rangle S 𝒞 = ⟨ 0 | O 𝒞 | 1 ⟩ / ⟨ 0 | 1 ⟩ where |0\rangle | 0 ⟩ and |1\rangle | 1 ⟩ are many-body states with different topological nature. 
    more » « less
  4. Abstract Persistent Betti numbers are a major tool in persistent homology, a subfield of topological data analysis. Many tools in persistent homology rely on the properties of persistent Betti numbers considered as a two-dimensional stochastic process$$ (r,s) \mapsto n^{-1/2} (\beta^{r,s}_q ( \mathcal{K}(n^{1/d} \mathcal{X}_n))-\mathbb{E}[\beta^{r,s}_q ( \mathcal{K}( n^{1/d} \mathcal{X}_n))])$$. So far, pointwise limit theorems have been established in various settings. In particular, the pointwise asymptotic normality of (persistent) Betti numbers has been established for stationary Poisson processes and binomial processes with constant intensity function in the so-called critical (or thermodynamic) regime; see Yogeshwaranet al.(Prob. Theory Relat. Fields167, 2017) and Hiraokaet al.(Ann. Appl. Prob.28, 2018). In this contribution, we derive a strong stabilization property (in the spirit of Penrose and Yukich,Ann. Appl. Prob.11, 2001) of persistent Betti numbers, and we generalize the existing results on their asymptotic normality to the multivariate case and to a broader class of underlying Poisson and binomial processes. Most importantly, we show that multivariate asymptotic normality holds for all pairs (r,s),$$0\le r\le s<\infty$$, and that it is not affected by percolation effects in the underlying random geometric graph. 
    more » « less
  5. Using harmonic mean curvature flow, we establish a sharp Minkowski-type lower bound for total mean curvature of convex surfaces with a given area in Cartan-Hadamard $$3$$-manifolds. This inequality also improves the known estimates for total mean curvature in hyperbolic $$3$$-space. As an application, we obtain a Bonnesen-style isoperimetric inequality for surfaces with convex distance function in nonpositively curved $$3$$-spaces, via monotonicity results for total mean curvature. This connection between the Minkowski and isoperimetric inequalities is extended to Cartan–Hadamard manifolds of any dimension. 
    more » « less