A relative Szemerédi theorem

详细信息    查看全文

• 作者：David Conlon ; Jacob Fox ; Yufei Zhao
• 刊名：Geometric And Functional Analysis
• 出版年：2015
• 出版时间：June 2015
• 年：2015
• 卷：25
• 期：3
• 页码：733-762
• 全文大小：777 KB
• 参考文献：BMS.J. Balogh, R. Morris, and W. Samotij. Independent sets in hypergraphs. J. Amer. Math. Soc., to appear.
  BB.P. Bennett and T. Bohman. A note on the random greedy independent set?algorithm. arXiv:-308.-732 .
  BR09.B. Bollobás and O. Riordan. Metrics for sparse graphs. In: Surveys in combinatorics 2009, London Math. Soc. Lecture Note Ser., vol. 365, Cambridge University Press, Cambridge, 2009, pp. 211-87.
  BCLSV08.C. Borgs, J.T. Chayes, L. Lovász, V.T. Sós, and K. Vesztergombi. Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing. Adv. Math., 219 (2008), 1801-851.
  CGW89.Chung F.R.K., Graham R.L., Wilson R.M.: Quasi-random graphs. Combinatorica 9, 345-62 (1989)MATH MathSciNet View Article
  CCF09.A. Coja-Oghlan, C. Cooper, and A. Frieze. An efficient sparse regularity concept. SIAM J. Discrete Math., 23 (2009/10), 2000-034.
  CFZ14.D. Conlon, J. Fox, and Y. Zhao. Extremal results in sparse pseudorandom graphs. Adv. Math., 256 (2014), 206-90.
  CFZ.D. Conlon, J. Fox, and Y. Zhao. Linear forms from the Gowers uniformity norm. Unpublished companion note.
  CG.D. Conlon and W.T. Gowers, Combinatorial theorems in sparse random sets. arXiv:-011.-310 .
  CGSS14.D. Conlon, W.T. Gowers, W. Samotij, and M. Schacht. On the K?R conjecture in random graphs. Israel J. Math., 203 (2014), 535-80.
  CM12.B. Cook and A. Magyar. Constellations in \({{\mathbb{P}}^d}\) . Int. Math. Res. Not., 2012 (2012), 2794-816.
  CMT.B. Cook, A. Magyar, and T. Titichetrakun. A multidimensional Szemerédi theorem in the primes. arXiv:-306.-025 .
  FZ.J. Fox and Y. Zhao. A short proof of the multidimensional Szemerédi theorem in the primes. Amer. J. Math., to appear.
  FR02.P. Frankl and V. R?dl. Extremal problems on set systems. Random Structures Algorithms, 20 (2002), 131-64.
  FK99.Frieze A., Kannan R.: Quick approximation to matrices and applications. Combinatorica 19, 175-20 (1999)MATH MathSciNet View Article
  FK78.H. Furstenberg and Y. Katznelson. An ergodic Szemerédi theorem for commuting transformations. J. Analyse Math., 34 (1978), 275-91.
  GY03.D.A. Goldston and C.Y. Y?ld?r?m. Higher correlations of divisor sums related to primes. I. Triple correlations. Integers, 3 (2003), A5, 66.
  Gow01.W.T. Gowers. A new proof of Szemerédi’s theorem. Geom. Funct. Anal. 11 (2001), 465-88.
  Gow07.W.T. Gowers. Hypergraph regularity and the multidimensional Szemerédi theorem. Ann. of Math., 166 (2007), 897-46.
  Gow10.W.T. Gowers. Decompositions, approximate structure, transference, and the Hahn-Banach theorem. Bull. Lond. Math. Soc., 42 (2010), 573-06. arXiv:-811.-103 .
  GreenPC.B. Green. Personal communication.
  Gre05.B. Green. A Szemerédi-type regularity lemma in abelian groups, with applications. Geom. Funct. Anal., 15 (2005), 340-76.
  GT08.B. Green and T. Tao. The primes contain arbitrarily long arithmetic progressions. Ann. of Math., 167 (2008), 481-47.
  GT10.B. Green and T. Tao. Linear equations in primes. Ann. of Math., 171 (2010), 1753-850.
  Koh97.Y. Kohayakawa. Szemerédi’s regularity lemma for sparse graphs. Foundations of computational mathematics (Rio de Janeiro, 1997), Springer, Berlin, 1997, pp. 216-30.
  KSV09.D. Král- O. Serra, and L. Vena. A combinatorial proof of the removal lemma for groups. J. Combin. Theory Ser. A, 116 (2009), 971-78.
  KSV12.D. Král- O. Serra, and L. Vena. A removal lemma for systems of linear equations over finite fields. Israel J. Math. 187 (2012), 193-07.
  Le11.T.H. Lê. Green-Tao theorem in function fields. Acta Arith. 147 (2011), 129-52.
  LS06.L. Lovász and B. Szegedy. Limits of dense graph sequences. J. Combin. Theory Ser. B 96 (2006), 933-57.
  LS07.L. Lovász and B. Szegedy. Szemerédi’s lemma for the analyst. Geom. Funct. Anal. 17 (2007), 252-70.
  Mat12a.L. Matthiesen, Correlations of the divisor function. Proc. Lond. Math. Soc. 104 (2012), 827-58.
  Mat12b.L. Matthiesen. Linear correlations amongst numbers represented by positive definite binary quadratic forms. Acta Arith. 154 (2012), 235-06.
  NRS06.B. Nagle, V. R?dl, and M. Schacht. The counting lemma for regular k-uniform hypergraphs. Random Structures Algorithms 28 (2006), 113-79.
  RTTV08.O. Reingold, L. Trevisan, M. Tulsiani, and S. Vadhan. Dense Subsets of Pseudorandom Sets. In: 49th Annual IEEE symposium on foundations of computer science, IEEE Computer Society (2008), pp. 76-5.
  RS04.V. R?dl and J. Skokan. Regularity lemma for k-uniform hypergraphs. Random Structures Algorithms 25 (2004), 1-2.
  RS06.V. R?dl and J. Skokan. Applications of the regularity lemma for uniform hypergraphs. Random Structures Algorithms. 28 (2006), 180-94.
  RS78.I.Z. Ruzsa and E. Szemerédi. Triple systems with no six points carrying three triangles. In: Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam (1978), pp. 939-45.
  ST.D. Saxton and A. Thom
• 作者单位：David Conlon (1)
  Jacob Fox (2)
  Yufei Zhao (2)
  
  1. Mathematical Institute, Oxford, OX1 3LB, UK
  2. Department of Mathematics, MIT, Cambridge, MA, 02139-4307, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Analysis
  
• 出版者：Birkh盲user Basel
• ISSN：1420-8970

文摘

The celebrated Green-Tao theorem states that there are arbitrarily long arithmetic progressions in the primes. One of the main ingredients in their proof is a relative Szemerédi theorem which says that any subset of a pseudorandom set of integers of positive relative density contains long arithmetic progressions. In this paper, we give a simple proof of a strengthening of the relative Szemerédi theorem, showing that a much weaker pseudorandomness condition is sufficient. Our strengthened version can be applied to give the first relative Szemerédi theorem for k-term arithmetic progressions in pseudorandom subsets of \({\mathbb{Z}_N}\) of density \({N^{-c_k}}\). The key component in our proof is an extension of the regularity method to sparse pseudorandom hypergraphs, which we believe to be interesting in its own right. From this we derive a relative extension of the hypergraph removal lemma. This is a strengthening of an earlier theorem used by Tao in his proof that the Gaussian primes contain arbitrarily shaped constellations and, by standard arguments, allows us to deduce the relative Szemerédi theorem.