2012/02/12 by Vsevolod F. Lev, Lev, Vsevolod F. · 1 citation
Mathematics · #05C35 (Primary) 26A30 #26A51 #26B25 #39B62 (Secondary) #Abelian group #Cayley graph #Combinatorics #Combinatorics (math.CO) #Complement (music) #Discrete mathematics #Exponent #FOS: Mathematics #Function (biology) #Graph #Graph theory and applications #Isoperimetric inequality #Lexicographical order #Limits and Structures in Graph Theory #Mathematics #Order (exchange) #Point processes and geometric inequalities #math.CO #msc:05C35 #msc:26A30 #msc:26A51 #msc:26B25 #msc:39B62
paper · pdf · doi:10.48550/arxiv.1202.2566
Minor corrections as compared to the original version. 27 pages, 3 figures
openalex publication_date 2012/02/12 · arxiv created 2012/03/01 · arxiv updated 2012/03/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a finite abelian abelian group of exponent m≥ 2. For subsets A,S⊂ G, denote by ∂S(A) the number of edges from A to its complement G∖ A in the directed Cayley graph, induced by S on G. We show that if S generates G, and A is non-empty, then ∂S(A) ≥ \fracem |A|ln(|G|)/(|A|). Here the coefficient e=2.718... is best possible and cannot be replaced with a number larger than e. For homocyclic groups G of exponent m, we find an explicit closed-form expression for ∂S(A) in the case where S is a "standard" generating subset of G, and A is an initial segment of G with respect to the lexicographic order, induced by S on G. Namely, we show that in this situation ∂S(A) = |G| ωm(|A|/|G|), where ω2 is the Takagi function, and ωm for m≥ 3 is an appropriate generalization thereof. This particular case is of special interest, since for m∈\2,3,4\ it is known to yield the smallest possible value of ∂S(A), over all sets A⊂ G of given size. We give this classical result a new proof, somewhat different from the standard one. We also give a new, short proof of the Boros-Pales inequality ω2(\fracx+y2) ≤ \fracω2(x) + ω2(y)2 + \frac12 |y-x|, establish an extremal characterization of the Takagi function as the (pointwise) maximal function, satisfying this inequality and the boundary condition max\ω2(0),ω2(1)\≤ 0, and obtain similar results for the 3-adic analog ω3 of the Takagi function.