...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Discrete Mathematics >EDGE-ISOPERIMETRIC PROBLEM FOR CAYLEY GRAPHS AND GENERALIZED TAKAGI FUNCTIONS
【24h】

EDGE-ISOPERIMETRIC PROBLEM FOR CAYLEY GRAPHS AND GENERALIZED TAKAGI FUNCTIONS

机译：Cayley图和广义Takagi函数的边等规问题

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Let G be a finite abelian group of exponent m >= 2. For subsets A, S subset of G, denote by partial derivative(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 nonempty, then partial derivative(S)(A) >= e/m vertical bar A vertical bar ln vertical bar G vertical bar/vertical bar A vertical bar. 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 partial derivative(S)(A) in the case where S is the "standard" generating subset of G, and A is an initial segment of G with respect to the lexicographic order induced by S. Namely, we show that in this situation partial derivative(S)(A) = vertical bar G vertical bar omega(m)(vertical bar A vertical bar/vertical bar G vertical bar), where omega(2) is the Takagi function, and omega(m) for m >= 3 is an appropriate generalization thereof. This particular case is of special interest, since for m is an element of {2, 3, 4} it is known to yield the smallest possible value of partial derivative(S)(A), over all sets A subset of 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 omega(2)(x+y/2) <= omega(2)(x)+omega(2)(y)/2 + 1/2 vertical bar y - x vertical bar, establish an extremal characterization of the Takagi function as the (pointwise) maximal function, satisfying this inequality and the boundary condition max{omega(2)(0), omega(2)(1)} <= 0, and obtain similar results for the 3-adic analogue omega(3) of the Takagi function.
机译：令G为指数m> = 2的有限阿贝尔群。对于G的子集A，S，用偏导数（S）（A）表示，在有向Cayley图中从A到补码GA的边数我们证明如果S生成G，并且A为非空，则偏导数（S）（A）> = e / m垂直线A垂直线ln垂直线G垂直线/垂直线A垂直线。在这里，系数e = 2.718 ...是最好的，不能用大于e的数字代替。对于指数m的同环群G，在S是G的“标准”生成子集，且A是G的初始段的情况下，我们发现了偏导数（S）（A）的显式闭式表达式。 S引起的字典顺序。即，我们表明在这种情况下偏导数（S）（A）=垂直线G垂直线omega（m）（垂直线A垂直线/垂直线G垂直线），其中omega （2）是高木函数，并且m> = 3的omega（m）是其适当的推广。由于m是{2，3，4}的元素，因此已知这种特殊情况特别重要，因为已知在给定G的所有集合A的子集上，偏导数（S）（A）的可能值最小。尺寸。我们为这一经典结果提供了新的证明，与标准的证明有些不同。我们还给出了Boros-Pales不等式的新的简短证明omega（2）（x + y / 2）<= omega（2）（x）+ omega（2）（y）/ 2 + 1/2竖线y-x竖线，建立Takagi函数的极值表征为（逐点）最大值函数，满足该不等式和边界条件max {omega（2）（0），omega（2）（1）} <= 0 ，并对Takagi函数的3-adic类似物omega（3）获得类似的结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号