Skip to Main Content

Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6834 (online) ISSN 0894-0347 (print)

The 2020 MCQ for Journal of the American Mathematical Society is 4.79.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Independent sets in hypergraphs
HTML articles powered by AMS MathViewer

by József Balogh, Robert Morris and Wojciech Samotij PDF
J. Amer. Math. Soc. 28 (2015), 669-709 Request permission

Abstract:

Many important theorems and conjectures in combinatorics, such as the theorem of Szemerédi on arithmetic progressions and the Erdős–Stone Theorem in extremal graph theory, can be phrased as statements about families of independent sets in certain uniform hypergraphs. In recent years, an important trend in the area has been to extend such classical results to the so-called ‘sparse random setting’. This line of research has recently culminated in the breakthroughs of Conlon and Gowers and of Schacht, who developed general tools for solving problems of this type. Although these two articles solved very similar sets of longstanding open problems, the methods used are very different from one another and have different strengths and weaknesses.

In this article, we provide a third, completely different, approach to proving extremal and structural results in sparse random sets that also yields their natural ‘counting’ counterparts. We give a structural characterization of the independent sets in a large class of uniform hypergraphs by showing that every independent set is almost contained in one of a small number of relatively sparse sets. We then derive many interesting results as fairly straightforward consequences of this abstract theorem. In particular, we prove the well-known conjecture of Kohayakawa, Łuczak, and Rödl, a probabilistic embedding lemma for sparse graphs. We also give alternative proofs of many of the results of Conlon and Gowers and of Schacht, such as sparse random versions of Szemerédi’s theorem, the Erdős–Stone Theorem, and the Erdős–Simonovits Stability Theorem, and obtain their natural ‘counting’ versions, which in some cases are considerably stronger. For example, we show that for each positive $\beta$ and integer $k$, there are at most $\binom {\beta n}{m}$ sets of size $m$ that contain no $k$-term arithmetic progression, provided that $m \geqslant Cn^{1-1/(k-1)}$, where $C$ is a constant depending only on $\beta$ and $k$. We also obtain new results, such as a sparse version of the Erdős–Frankl–Rödl Theorem on the number of $H$-free graphs and, as a consequence of the KŁR conjecture, we extend a result of Rödl and Ruciński on Ramsey properties in sparse random graphs to the general, non-symmetric setting.

References
Similar Articles
Additional Information
  • József Balogh
  • Affiliation: Department of Mathematics, University of Illinois, 1409 W. Green Street, Urbana, IL 61801
  • Email: jobal@math.uiuc.edu
  • Robert Morris
  • Affiliation: IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ, Brasil
  • MR Author ID: 777846
  • Email: rob@impa.br
  • Wojciech Samotij
  • Affiliation: School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel and Trinity College, Cambridge CB2 1TQ, UK
  • MR Author ID: 871997
  • Email: ws299@cam.ac.uk
  • Received by editor(s): June 16, 2012
  • Received by editor(s) in revised form: March 21, 2014
  • Published electronically: August 7, 2014
  • Additional Notes: The first author was supported in part by NSF Career Grant DMS-0745185, UIUC Campus Research Board Grant 11067, and OTKA Grant K76099.
    The second author was supported in part by CNPq bolsa de Produtivdade em Pesquisa.
    The third author was supported in part by ERC Advanced Grant DMMCA and a Trinity College JRF
  • © Copyright 2014 American Mathematical Society
  • Journal: J. Amer. Math. Soc. 28 (2015), 669-709
  • MSC (2010): Primary 05D40; Secondary 05C30, 05C35, 05C65
  • DOI: https://doi.org/10.1090/S0894-0347-2014-00816-X
  • MathSciNet review: 3327533