Establishes the first exponential improvement since 1947 to the lower bound on off-diagonal Ramsey numbers r(ℓ, Cℓ) for constant C > 1.
Title resolution pending
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
verdicts
UNVERDICTED 5representative citing papers
This work charts a nuanced complexity landscape for diameter computation on 2D intersection graphs, delivering new subquadratic algorithms for some object types and diameter values while proving hardness for others under fine-grained assumptions.
Proves that graphs on N ≥ 2n vertices with δ(G) ≥ ⌊3N/4⌋ have every 2-edge-coloring containing a monochromatic copy of every n-vertex tree with max degree ≤ Δ.
Establishes that the 2-color Ramsey number for sufficiently many vertex-disjoint copies of H remains asymptotically the same in the random graph G(n,p) for appropriate p.
Simplified proof of exponential Ramsey lower bound improvements via Gaussian random graphs, with better quantitative constants than prior work.
citing papers explorer
-
Charting the Diameter Computation Landscape on Intersection Graphs in the Plane
This work charts a nuanced complexity landscape for diameter computation on 2D intersection graphs, delivering new subquadratic algorithms for some object types and diameter values while proving hardness for others under fine-grained assumptions.
-
A degree version of the Burr-Erd\H{o}s conjecture on trees
Proves that graphs on N ≥ 2n vertices with δ(G) ≥ ⌊3N/4⌋ have every 2-edge-coloring containing a monochromatic copy of every n-vertex tree with max degree ≤ Δ.
-
A random version of the Burr-Erd\H{o}s-Spencer theorem
Establishes that the 2-color Ramsey number for sufficiently many vertex-disjoint copies of H remains asymptotically the same in the random graph G(n,p) for appropriate p.