 Award ID(s):
 1700147
 NSFPAR ID:
 10096799
 Date Published:
 Journal Name:
 Annals of mathematics
 Volume:
 189
 Issue:
 2
 ISSN:
 0003486X
 Page Range / eLocation ID:
 605652
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

null (Ed.)Abstract One of the oldest outstanding problems in dynamical algebraic combinatorics is the following conjecture of P. Cameron and D. FonDerFlaass (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+c1$ is prime, Cameron and FonDerFlaass 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 FonDerFlaass (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

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

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 set
V . 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 fixedL such that if, for a given , admits withand (a.k.a. is weakly 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. 
We prove the endpoint case of a conjecture of Khot and Moshkovitz related to the unique games conjecture, less a small error. Let
n ≥ 2. Suppose a subset Ω ofn ‐dimensional Euclidean spacesatisfies −Ω = Ω^{c}and Ω + v = Ω^{c}(up to measure zero sets) for every standard basis vector. For any and for any q ≥ 1, letand let . For any x ∈∂ Ω, letN (x ) denote the exterior normal vector atx such that ‖N (x )‖_{2} = 1. Let. Our main result shows that B has 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^{−9}would 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. 
We prove that every connected P5free graph has cop number at most two, solving a conjecture of Sivaraman. In order to do so, we first prove that every connected P5free graph G with independence number at least three contains a threevertex induced path with vertices abc in order, such that every neighbor of c is also adjacent to one of a,b.more » « less