Table of contents for this issue | Previous article | Next article
Yahya O. Hamidoune
Some additive applications of the isoperimetric approach
(Quelques applications additives de la méthode isopérimétrique)
Annales de l'institut Fourier, 58 no. 6 (2008), p. 2007-2036, doi: 10.5802/aif.2404
Article: subscription required (your ip address: 107.21.156.140) | Reviews MR 2473627 | Zbl 1173.05019
Class. Math.: 05C25, 20D60, 11B75, 05C40
Keywords: Addition theorem, Cayley graph, inverse additive theory
[1] Z. Arad & M. Muzychuk, “Order evaluation of products of subsets in finite groups and its applications. II.”, Trans. Amer. Math. Soc. 349 (1997) no. 11, p. 4401-4414
Article | MR 1407477 | Zbl 0895.20022
[2] E. Balandraud, “Un nouveau point de vue isopérimétrique appliqué au théorème de Kneser”, Preprint, 2005
[3] L. V. Brailowski & G. A. Freiman, “On a product of finite subsets in a torsion free group”, J. Algebra 130 (1990), p. 462-476
Article | MR 1051314 | Zbl 0697.20019
[4] A. Cauchy, “Recherches sur les nombres”, J. École polytechnique 9 (1813), p. 99-116
Article
[5] S. Chowla, “A theorem on the addition of residue classes: applications to the number $\Gamma (k)$ in Waring’s problem”, Proc. Indian Acad. Sc. 2 (1935), p. 242-243 JFM 61.0149.03
[6] H. Davenport, “On the addition of residue classes”, J. London Math. Soc. 10 (1935), p. 30-32
Article | JFM 61.0149.02
[7] J. M. Deshouillers & G. A. Freiman, “A step beyond Kneser’s Theorem”, Proc. London Math. Soc. 86 (2003) no. 3, p. 1-28
Article | Zbl 1032.11009
[8] G. T. Diderrich, “On Kneser’s addition theorem in groups”, Proc. Amer. Math. Soc. (1973), p. 443-451 Zbl 0266.20041
[9] G. A. Dirac, “Extensions of Menger’s theorem”, J. Lond. Math. Soc. 38 (1963)
Article | Zbl 0112.38606
[10] J. Dixmier, “Proof of a conjecture by Erdös, Graham concerning the problem of Frobenius”, J. number Theory 34 (1990), p. 198-209
Article | MR 1042493 | Zbl 0695.10012
[11] F. J. Dyson, “A theorem on the densities of sets of integers”, J. London Math. Soc. 20 (1945), p. 8-14
Article | MR 15074 | Zbl 0061.07408
[12] P. Erdős & H. Heilbronn, “On the Addition of residue classes mod $p$”, Acta Arith. 9 (1964), p. 149-159
Article | MR 166186 | Zbl 0156.04801
[13] B. Green & I. Z. Ruzsa, “Sets with small sumset and rectification”, Bull. London Math. Soc. 38 (2006) no. 1, p. 43-52
Article | MR 2201602 | Zbl pre05014332
[14] Y. O. Hamidoune, “Beyond Kemperman’s Structure Theory: The isoperimetric approach”, In preparation
[15] Y. O. Hamidoune, “Sur les atomes d’un graphe orienté”, C.R. Acad. Sc. Paris A 284 (1977), p. 1253-1256 Zbl 0352.05035
[16] Y. O. Hamidoune, “An application of connectivity theory in graphs to factorizations of elements in groups”, Europ. J. of Combinatorics 2 (1981), p. 349-355 MR 638410 | Zbl 0473.05032
[17] Y. O. Hamidoune, “Quelques problèmes de connexité dans les graphes orientés”, J. Comb. Theory B 30 (1981), p. 1-10 MR 609588 | Zbl 0475.05039
[18] Y. O. Hamidoune, “On the connectivity of Cayley digraphs”, Europ. J. Combinatorics 5 (1984), p. 309-312 MR 782052 | Zbl 0561.05028
[19] Y. O. Hamidoune, “On a subgroup contained in words with a bounded length”, Discrete Math. 103 (1992), p. 171-176
Article | MR 1171314 | Zbl 0773.20004
[20] Y. O. Hamidoune, “An isoperimetric method in additive theory”, J. Algebra 179 (1996) no. 2, p. 622-630
Article | MR 1367866 | Zbl 0842.20029
[21] Y. O. Hamidoune, “On subsets with a small sum in abelian groups I: The Vosper property”, Europ. J. of Combinatorics 18 (1997), p. 541-556
Article | MR 1455186 | Zbl 0883.05065
[22] Y. O. Hamidoune, “On small subset product in a group. Structure Theory of set-addition”, Astérisque 258 (1999), p. 281-308, xiv-xv MR 1701204 | Zbl 0945.20011
[23] Y. O. Hamidoune, “Some results in Additive number Theory I: The critical pair Theory”, Acta Arith. 96 (2000) no. 2, p. 97-119
Article | MR 1814447 | Zbl 0985.11011
[24] Y. O. Hamidoune, “Hyper-atoms and the Kemperman’s critical pair Theory”, Preprint, 2007
arXiv
[25] Y. O. Hamidoune & Ø. J. Rødseth, “On bases for $\sigma $-finite groups”, Math. Sc. 78 (1996) no. 2, p. 246-254
Article | MR 1414651 | Zbl 0877.11007
[26] Y. O. Hamidoune & Ø. J. Rødseth, “An inverse theorem modulo $p$”, Acta Arithmetica 92 (2000), p. 251-262
Article | MR 1752029 | Zbl 0945.11003
[27] Y. O. Hamidoune, O. Serra & G. Zémor, “On the critical pair theory in Abelian groups: Beyond Chowla’s Theorem”, Preprint, 2006
[28] Y. O. Hamidoune, O. Serra & G. Zémor, “On the critical pair theory in $\mathbb{Z}/p\mathbb{Z}$”, Acta Arith. 121 (2006) no. 2, p. 99-115
Article | MR 2216136 | Zbl pre05024060
[29] N. Hegyvári, “On iterated difference sets in groups”, Period. Math. Hungar. 43 (2001) no. 1-2, p. 105-110 MR 1830569 | Zbl 0980.11016
[30] R. Jin, “Solution to the inverse problem for upper asymptotic density”, J. Reine Angew. Math. 595 (2006), p. 121-165
Article | MR 2244800 | Zbl 1138.11045
[31] V. Jungić, J. Licht, M. Mahdian, J. Nešetřil, R. Jaroslav & R. Radoičić, “Rainbow arithmetic progressions and anti-Ramsey results. Special issue on Ramsey theory”, Combin. Probab. Comput. 12 (2003) no. 5-6, p. 599-620
Article | MR 2037073 | Zbl 1128.11305
[32] G. Károlyi, “Cauchy-Davenport theorem in group extensions”, Enseign. Math. (2)51 (2005) no. 3-4, p. 239-254 MR 2214888 | Zbl 1111.20026
[33] J. H. B. Kemperman, “On complexes in a semigroup”, Nederl. Akad. Wetensch. Proc. Ser. A 59 (1956) no. 18, p. 247-254, Indag. Math. MR 85263 | Zbl 0072.25605
[34] J. H. B. Kemperman, “On small sumsets in Abelian groups”, Acta Math. 103 (1960), p. 66-88
Article | MR 110747 | Zbl 0108.25704
[35] M. Kneser, “Abschätzung der asymptotischen Dichte von Summenmengen”, Math. Z. 58 (1953), p. 459-484
Article | MR 56632 | Zbl 0051.28104
[36] M. Kneser, “Summenmengen in lokalkompakten abelesche Gruppen”, Math. Zeit. 66 (1956), p. 88-110
Article | MR 81438 | Zbl 0073.01702
[37] H. B. Mann, “An addition theorem for sets of elements of an Abelian group”, Proc. Amer. Math. Soc. 4 (1953) MR 55334 | Zbl 0050.25703
[38] H. B. Mann, Addition Theorems, R.E. Krieger, 1976 MR 424744
[39] K. Menger, “Zur allgemeinen Kurventhoerie”, Fund. Math. 10 Karl (1927), p. 96-115
Article | JFM 53.0561.01
[40] M. B. Nathanson, Additive Number Theory. Inverse problems and the geometry of sumsets, in Springer, ed., Grad. Texts in Math., 1996 MR 1477155 | Zbl 0859.11003
[41] N. Nikolov & D. Segal, “On finitely generated profinite groups. I. Strong completeness and uniform bounds”, Ann. of Math. (2) 165 (2007) no. 1, p. 171-238
Article | MR 2276769 | Zbl 1126.20018
[42] N. Nikolov & D. Segal, “On finitely generated profinite groups. II. Products in quasisimple groups”, Ann. of Math. (2) 165 (2007) no. 1, p. 239-273
Article | MR 2276770 | Zbl 1126.20018
[43] J. E. Olson, “Sums of sets of group elements”, Acta Arith. 28 (1975/76) no. 2, p. 147-156
Article | MR 382215 | Zbl 0318.10035
[44] J. E. Olson, “On the sum of two sets in a group”, J. Number Theory 18 (1984), p. 110-120
Article | MR 734442 | Zbl 0524.10043
[45] J. E. Olson, “On the symmetric difference of two sets in a group”, Europ. J. Combinatorics (1986), p. 43-54 MR 850143 | Zbl 0597.05012
[46] A. Plagne, “$(k,l)$-free sets in $\mathbb{Z}/p\mathbb{Z}$ are arithmetic progressions”, Bull. Austral. Math. Soc. 65 (2002) no. 1, p. 137-144
Article | MR 1889388 | Zbl 1034.11057
[47] L. Pyber, “Bounded generation and subgroup growth”, Bull. London Math. Soc. 34 (2002) no. 1, p. 55-60
Article | MR 1866428 | Zbl 1041.20016
[48] Ø. J. Rødseth, “Two remarks on linear forms in non-negative integers”, Math. Scand. 51 (1982), p. 193-198 MR 690524 | Zbl 0503.10035
[49] I. Ruzsa, “An application of graph theory to additive number theory”, Scientia, Ser. A 3 (1989) MR 2314377 | Zbl 0743.05052
[50] O. Serra, An isoperimetric method for the small sumset problem, Surveys in combinatorics, Cambridge Univ. Press, 2005, p. 119–152 MR 2187737 | Zbl pre05117215
[51] O. Serra & G. Zémor, “On a generalization of a theorem by Vosper”, Integers, 0, A10, (electronic), 2000 MR 1771980 | Zbl 0953.11031
[52] J. C. Shepherdson, “On the addition of elements of a sequence”, J. London Math Soc. 22 (1947), p. 85-88
Article | MR 22866 | Zbl 0029.34402
[53] E. Szemerédi, “On a conjecture of Erdös and Heilbronn”, Acta Arithmetica 17 (1970), p. 227-229
Article | MR 268159 | Zbl 0222.10055
[54] T. Tao & V. H. Vu, Additive Combinatorics, Cambridge Studies in Advanced Mathematics, Cambridge University Press, 2006 MR 2289012 | Zbl 1127.11002
[55] G. Vosper, “Addendum to: The critical pairs of subsets of a group of prime order”, J. London Math. Soc. 31 (1956), p. 280-282
Article | MR 78368 | Zbl 0072.03402
[56] G. Vosper, “The critical pairs of subsets of a group of prime order”, J. London Math. Soc. 31 (1956), p. 200-205
Article | MR 77555 | Zbl 0072.03402
[57] G. Zémor, “On positive and negative atoms of Cayley digraphs”, Discrete Appl. Math. 23 (1989) no. 2, p. 193-195
Article | MR 996549 | Zbl 0674.05032
Yahya O. Hamidoune
Some additive applications of the isoperimetric approach
(Quelques applications additives de la méthode isopérimétrique)
Annales de l'institut Fourier, 58 no. 6 (2008), p. 2007-2036, doi: 10.5802/aif.2404
Article: subscription required (your ip address: 107.21.156.140) | Reviews MR 2473627 | Zbl 1173.05019
Class. Math.: 05C25, 20D60, 11B75, 05C40
Keywords: Addition theorem, Cayley graph, inverse additive theory
Résumé - Abstract
Let $G$ be a group and let $X$ be a finite subset. The isoperimetric method investigates the objective function $|(XB)\setminus X|$, defined on the subsets $X$ with $|X|\ge k$ and $|G\setminus (XB)|\ge k$, where $XB$ is the product of $X$ by $B$.
In this paper we present all the basic facts about the isoperimetric method. We improve some of our previous results and obtain generalizations and short proofs for several known results. We also give some new applications.
Some of the results obtained here will be used in coming papers to improve Kempermann structure Theory.
Bibliography
Article | MR 1407477 | Zbl 0895.20022
[2] E. Balandraud, “Un nouveau point de vue isopérimétrique appliqué au théorème de Kneser”, Preprint, 2005
[3] L. V. Brailowski & G. A. Freiman, “On a product of finite subsets in a torsion free group”, J. Algebra 130 (1990), p. 462-476
Article | MR 1051314 | Zbl 0697.20019
[4] A. Cauchy, “Recherches sur les nombres”, J. École polytechnique 9 (1813), p. 99-116
Article
[5] S. Chowla, “A theorem on the addition of residue classes: applications to the number $\Gamma (k)$ in Waring’s problem”, Proc. Indian Acad. Sc. 2 (1935), p. 242-243 JFM 61.0149.03
[6] H. Davenport, “On the addition of residue classes”, J. London Math. Soc. 10 (1935), p. 30-32
Article | JFM 61.0149.02
[7] J. M. Deshouillers & G. A. Freiman, “A step beyond Kneser’s Theorem”, Proc. London Math. Soc. 86 (2003) no. 3, p. 1-28
Article | Zbl 1032.11009
[8] G. T. Diderrich, “On Kneser’s addition theorem in groups”, Proc. Amer. Math. Soc. (1973), p. 443-451 Zbl 0266.20041
[9] G. A. Dirac, “Extensions of Menger’s theorem”, J. Lond. Math. Soc. 38 (1963)
Article | Zbl 0112.38606
[10] J. Dixmier, “Proof of a conjecture by Erdös, Graham concerning the problem of Frobenius”, J. number Theory 34 (1990), p. 198-209
Article | MR 1042493 | Zbl 0695.10012
[11] F. J. Dyson, “A theorem on the densities of sets of integers”, J. London Math. Soc. 20 (1945), p. 8-14
Article | MR 15074 | Zbl 0061.07408
[12] P. Erdős & H. Heilbronn, “On the Addition of residue classes mod $p$”, Acta Arith. 9 (1964), p. 149-159
Article | MR 166186 | Zbl 0156.04801
[13] B. Green & I. Z. Ruzsa, “Sets with small sumset and rectification”, Bull. London Math. Soc. 38 (2006) no. 1, p. 43-52
Article | MR 2201602 | Zbl pre05014332
[14] Y. O. Hamidoune, “Beyond Kemperman’s Structure Theory: The isoperimetric approach”, In preparation
[15] Y. O. Hamidoune, “Sur les atomes d’un graphe orienté”, C.R. Acad. Sc. Paris A 284 (1977), p. 1253-1256 Zbl 0352.05035
[16] Y. O. Hamidoune, “An application of connectivity theory in graphs to factorizations of elements in groups”, Europ. J. of Combinatorics 2 (1981), p. 349-355 MR 638410 | Zbl 0473.05032
[17] Y. O. Hamidoune, “Quelques problèmes de connexité dans les graphes orientés”, J. Comb. Theory B 30 (1981), p. 1-10 MR 609588 | Zbl 0475.05039
[18] Y. O. Hamidoune, “On the connectivity of Cayley digraphs”, Europ. J. Combinatorics 5 (1984), p. 309-312 MR 782052 | Zbl 0561.05028
[19] Y. O. Hamidoune, “On a subgroup contained in words with a bounded length”, Discrete Math. 103 (1992), p. 171-176
Article | MR 1171314 | Zbl 0773.20004
[20] Y. O. Hamidoune, “An isoperimetric method in additive theory”, J. Algebra 179 (1996) no. 2, p. 622-630
Article | MR 1367866 | Zbl 0842.20029
[21] Y. O. Hamidoune, “On subsets with a small sum in abelian groups I: The Vosper property”, Europ. J. of Combinatorics 18 (1997), p. 541-556
Article | MR 1455186 | Zbl 0883.05065
[22] Y. O. Hamidoune, “On small subset product in a group. Structure Theory of set-addition”, Astérisque 258 (1999), p. 281-308, xiv-xv MR 1701204 | Zbl 0945.20011
[23] Y. O. Hamidoune, “Some results in Additive number Theory I: The critical pair Theory”, Acta Arith. 96 (2000) no. 2, p. 97-119
Article | MR 1814447 | Zbl 0985.11011
[24] Y. O. Hamidoune, “Hyper-atoms and the Kemperman’s critical pair Theory”, Preprint, 2007
arXiv
[25] Y. O. Hamidoune & Ø. J. Rødseth, “On bases for $\sigma $-finite groups”, Math. Sc. 78 (1996) no. 2, p. 246-254
Article | MR 1414651 | Zbl 0877.11007
[26] Y. O. Hamidoune & Ø. J. Rødseth, “An inverse theorem modulo $p$”, Acta Arithmetica 92 (2000), p. 251-262
Article | MR 1752029 | Zbl 0945.11003
[27] Y. O. Hamidoune, O. Serra & G. Zémor, “On the critical pair theory in Abelian groups: Beyond Chowla’s Theorem”, Preprint, 2006
[28] Y. O. Hamidoune, O. Serra & G. Zémor, “On the critical pair theory in $\mathbb{Z}/p\mathbb{Z}$”, Acta Arith. 121 (2006) no. 2, p. 99-115
Article | MR 2216136 | Zbl pre05024060
[29] N. Hegyvári, “On iterated difference sets in groups”, Period. Math. Hungar. 43 (2001) no. 1-2, p. 105-110 MR 1830569 | Zbl 0980.11016
[30] R. Jin, “Solution to the inverse problem for upper asymptotic density”, J. Reine Angew. Math. 595 (2006), p. 121-165
Article | MR 2244800 | Zbl 1138.11045
[31] V. Jungić, J. Licht, M. Mahdian, J. Nešetřil, R. Jaroslav & R. Radoičić, “Rainbow arithmetic progressions and anti-Ramsey results. Special issue on Ramsey theory”, Combin. Probab. Comput. 12 (2003) no. 5-6, p. 599-620
Article | MR 2037073 | Zbl 1128.11305
[32] G. Károlyi, “Cauchy-Davenport theorem in group extensions”, Enseign. Math. (2)51 (2005) no. 3-4, p. 239-254 MR 2214888 | Zbl 1111.20026
[33] J. H. B. Kemperman, “On complexes in a semigroup”, Nederl. Akad. Wetensch. Proc. Ser. A 59 (1956) no. 18, p. 247-254, Indag. Math. MR 85263 | Zbl 0072.25605
[34] J. H. B. Kemperman, “On small sumsets in Abelian groups”, Acta Math. 103 (1960), p. 66-88
Article | MR 110747 | Zbl 0108.25704
[35] M. Kneser, “Abschätzung der asymptotischen Dichte von Summenmengen”, Math. Z. 58 (1953), p. 459-484
Article | MR 56632 | Zbl 0051.28104
[36] M. Kneser, “Summenmengen in lokalkompakten abelesche Gruppen”, Math. Zeit. 66 (1956), p. 88-110
Article | MR 81438 | Zbl 0073.01702
[37] H. B. Mann, “An addition theorem for sets of elements of an Abelian group”, Proc. Amer. Math. Soc. 4 (1953) MR 55334 | Zbl 0050.25703
[38] H. B. Mann, Addition Theorems, R.E. Krieger, 1976 MR 424744
[39] K. Menger, “Zur allgemeinen Kurventhoerie”, Fund. Math. 10 Karl (1927), p. 96-115
Article | JFM 53.0561.01
[40] M. B. Nathanson, Additive Number Theory. Inverse problems and the geometry of sumsets, in Springer, ed., Grad. Texts in Math., 1996 MR 1477155 | Zbl 0859.11003
[41] N. Nikolov & D. Segal, “On finitely generated profinite groups. I. Strong completeness and uniform bounds”, Ann. of Math. (2) 165 (2007) no. 1, p. 171-238
Article | MR 2276769 | Zbl 1126.20018
[42] N. Nikolov & D. Segal, “On finitely generated profinite groups. II. Products in quasisimple groups”, Ann. of Math. (2) 165 (2007) no. 1, p. 239-273
Article | MR 2276770 | Zbl 1126.20018
[43] J. E. Olson, “Sums of sets of group elements”, Acta Arith. 28 (1975/76) no. 2, p. 147-156
Article | MR 382215 | Zbl 0318.10035
[44] J. E. Olson, “On the sum of two sets in a group”, J. Number Theory 18 (1984), p. 110-120
Article | MR 734442 | Zbl 0524.10043
[45] J. E. Olson, “On the symmetric difference of two sets in a group”, Europ. J. Combinatorics (1986), p. 43-54 MR 850143 | Zbl 0597.05012
[46] A. Plagne, “$(k,l)$-free sets in $\mathbb{Z}/p\mathbb{Z}$ are arithmetic progressions”, Bull. Austral. Math. Soc. 65 (2002) no. 1, p. 137-144
Article | MR 1889388 | Zbl 1034.11057
[47] L. Pyber, “Bounded generation and subgroup growth”, Bull. London Math. Soc. 34 (2002) no. 1, p. 55-60
Article | MR 1866428 | Zbl 1041.20016
[48] Ø. J. Rødseth, “Two remarks on linear forms in non-negative integers”, Math. Scand. 51 (1982), p. 193-198 MR 690524 | Zbl 0503.10035
[49] I. Ruzsa, “An application of graph theory to additive number theory”, Scientia, Ser. A 3 (1989) MR 2314377 | Zbl 0743.05052
[50] O. Serra, An isoperimetric method for the small sumset problem, Surveys in combinatorics, Cambridge Univ. Press, 2005, p. 119–152 MR 2187737 | Zbl pre05117215
[51] O. Serra & G. Zémor, “On a generalization of a theorem by Vosper”, Integers, 0, A10, (electronic), 2000 MR 1771980 | Zbl 0953.11031
[52] J. C. Shepherdson, “On the addition of elements of a sequence”, J. London Math Soc. 22 (1947), p. 85-88
Article | MR 22866 | Zbl 0029.34402
[53] E. Szemerédi, “On a conjecture of Erdös and Heilbronn”, Acta Arithmetica 17 (1970), p. 227-229
Article | MR 268159 | Zbl 0222.10055
[54] T. Tao & V. H. Vu, Additive Combinatorics, Cambridge Studies in Advanced Mathematics, Cambridge University Press, 2006 MR 2289012 | Zbl 1127.11002
[55] G. Vosper, “Addendum to: The critical pairs of subsets of a group of prime order”, J. London Math. Soc. 31 (1956), p. 280-282
Article | MR 78368 | Zbl 0072.03402
[56] G. Vosper, “The critical pairs of subsets of a group of prime order”, J. London Math. Soc. 31 (1956), p. 200-205
Article | MR 77555 | Zbl 0072.03402
[57] G. Zémor, “On positive and negative atoms of Cayley digraphs”, Discrete Appl. Math. 23 (1989) no. 2, p. 193-195
Article | MR 996549 | Zbl 0674.05032
© Annales de L'Institut Fourier - ISSN (électronique) : 1777-5310