skip to main content

Attention:

The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 11:00 PM ET on Thursday, October 10 until 2:00 AM ET on Friday, October 11 due to maintenance. We apologize for the inconvenience.

Explore Research Products in the NSF-PAR

Title: A proof of a sumset conjecture of Erdős
In this paper we show that every set A⊂ℕ with positive density contains B+C for some pair B,C of infinite subsets of ℕ, settling a conjecture of Erd\H os. The proof features two different decompositions of an arbitrary bounded sequence into a structured component and a pseudo-random component. Our methods are quite general, allowing us to prove a version of this conjecture for countable amenable groups.  more » « less
Award ID(s):
1700147
NSF-PAR ID:
10096799
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Annals of mathematics
Volume:
189
Issue:
2
ISSN:
0003-486X
Page Range / eLocation ID:
605-652
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ( , Forum of Mathematics, Sigma)
    null (Ed.)
    Abstract One of the oldest outstanding problems in dynamical algebraic combinatorics is the following conjecture of P. Cameron and D. Fon-Der-Flaass (1995): consider a plane partition P in an $a \times b \times c$ box ${\sf B}$ . Let $\Psi (P)$ denote the smallest plane partition containing the minimal elements of ${\sf B} - P$ . Then if $p= a+b+c-1$ is prime, Cameron and Fon-Der-Flaass conjectured that the cardinality of the $\Psi $ -orbit of P is always a multiple of p . This conjecture was established for $p \gg 0$ by Cameron and Fon-Der-Flaass (1995) and for slightly smaller values of p in work of K. Dilks, J. Striker and the second author (2017). Our main theorem specializes to prove this conjecture in full generality. 
    more » « less
  2. ; ; ( , Combinatorica)
    A “pure pair” in a graph G is a pair A, B of disjoint subsets of V(G) such that A is complete or anticomplete to B. Jacob Fox showed that for all ε>0, there is a comparability graph G with n vertices, where n is large, in which there is no pure pair A, B with |A|,|B|≥εn. He also proved that for all c>0 there exists ε>0 such that for every comparability graph G with n>1 vertices, there is a pure pair A, B with |A|,|B|≥εn1−c; and conjectured that the same holds for every perfect graph G. We prove this conjecture and strengthen it in several ways. In particular, we show that for all c>0, and all ℓ1,ℓ2≥4/c+9, there exists ε>0 such that, if G is an (n>1)-vertex graph with no hole of length exactly ℓ1 and no antihole of length exactly ℓ2, then there is a pure pair A, B in G with |A|≥εn and |B|≥εn1−c. This is further strengthened, replacing excluding a hole by excluding some “long” subdivision of a general graph. 
    more » « less
  3. ; ; ( , Random Structures & Algorithms)
    Abstract

    We address a special case of a conjecture of M. Talagrand relating two notions of “threshold” for an increasing family of subsets of a finite setV. The full conjecture implies equivalence of the “Fractional Expectation‐Threshold Conjecture,” due to Talagrand and recently proved by the authors and B. Narayanan, and the (stronger) “Expectation‐Threshold Conjecture” of the second author and G. Kalai. The conjecture under discussion here says there is a fixedLsuch that if, for a given , admits withand(a.k.a.  isweakly p‐small), then admits such a taking values in ( is‐small). Talagrand showed this when is supported on singletons and suggested, as a more challenging test case, proving it when is supported on pairs. The present work provides such a proof.

     
    more » « less
  4. ( , Random Structures & Algorithms)

    We prove the endpoint case of a conjecture of Khot and Moshkovitz related to the unique games conjecture, less a small error. Letn ≥ 2. Suppose a subset Ω ofn‐dimensional Euclidean spacesatisfies −Ω = Ωcand Ω + v = Ωc(up to measure zero sets) for every standard basis vector. For anyand for anyq ≥ 1, letand let. For anyx ∈ ∂Ω, letN(x) denote the exterior normal vector atxsuch that ‖N(x)‖2 = 1. Let. Our main result shows thatBhas the smallest Gaussian surface area among all such subsets Ω, less a small error:In particular,Standard arguments extend these results to a corresponding weak inequality for noise stability. Removing the factor 6 × 10−9would prove the endpoint case of the Khot‐Moshkovitz conjecture. Lastly, we prove a Euclidean analogue of the Khot and Moshkovitz conjecture. The full conjecture of Khot and Moshkovitz provides strong evidence for the truth of the unique games conjecture, a central conjecture in theoretical computer science that is closely related to the P versus NP problem. So, our results also provide evidence for the truth of the unique games conjecture. Nevertheless, this paper does not prove any case of the unique games conjecture.

     
    more » « less
  5. ; ; ; ( , SIAM Journal on Discrete Mathematics)
    We prove that every connected P5-free graph has cop number at most two, solving a conjecture of Sivaraman. In order to do so, we first prove that every connected P5-free graph G with independence number at least three contains a three-vertex induced path with vertices a-b-c in order, such that every neighbor of c is also adjacent to one of a,b. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email