Approximate convexity and an edge-isoperimetric estimate

2013/11/23 by Vsevolod F. lev, lev, Vsevolod F.
Mathematics · #05C35 #05D99 #Combinatorics (math.CO) #FOS: Mathematics #Functional Analysis (math.FA) #Primary: 39B62 #math.CO #math.FA #msc:05C35 #msc:05D99 #msc:26A51 #msc:39B62 #secondary: 26A51

paper · pdf · doi:10.48550/arxiv.1311.5986

arxiv created 2013/11/23 · arxiv updated 2013/11/26

Abstract

We study extremal properties of the function F(x) := min\k‖x‖^1-1/k\colon k≥ 1\, x∈[0,1], where ‖x‖=min\x,1-x\. In particular, we show that F is the pointwise largest function of the class of all real-valued functions f defined on the interval [0,1], and satisfying the relaxed convexity condition f(tx₁+(1-t)x₂) ≤ tf(x₁)+(1-t)f(x₂)+|x₂-x₁|, x₁,x₂,t∈[0,1] and the boundary condition max\f(0),f(1)\≤ 0. As an application, we prove that if A and S are subsets of a finite abelian group G, such that S is generating and all of its elements have order at most m, then the number of edges from A to its complement G∖ A in the directed Cayley graph induced by S on G is ∂_S(A) ≥ (1)/(m) |G| F(|A|/|G|).

Related

• Edge-isoperimetric problem for Cayley graphs and generalized Takagi function
• Extremal Approximately Convex Functions and the Best Constants in a Theorem of Hyers and Ulam
• On the structure of subsets of the discrete cube with small edge\n boundary
• Edge isoperimetry of lattices
• Monotonicity of the optimal perimeter in isoperimetric problems on ℤ^k × ℕ^d