26 papers · 1 filter
Sunflowers and Ramsey problems for restricted intersections
Barnabás Janzer, Zhihan Jin, Benny Sudakov +1
Extremal problems on set systems with restricted intersections have been an important part of combinatorics in the last 70 years. In this paper, we study the following Ramsey versi…
Nearly tight bounds for induced subdivisions
Zach Hunter, Aleksa MilojeviÄ, Patryk Morawski +1
Subdivisions of complete graphs play a central role in combinatorics, having deep connections to structural, extremal, and topological aspects of graph theory. A celebrated conject…
Gaussian random graphs and Ramsey numbers
Zach Hunter, Aleksa MilojeviÄ, Benny Sudakov
We give a simple proof of the recent remarkable exponential improvement for Ramsey lower bounds, obtained by Ma, Shen and Xie. Our key ingredient is an alternative construction bas…
The Mihail-Vazirani conjecture and strong edge-expansion in random polytopes
Micha Christoph, Sahar Diskin, Lyuben Lichev +1
We study the edge-expansion of the graph of a random polytope , defined as the convex hull of a random subset of the points in where every point is retaine…
Packing subgraphs in regular graphs
Shoham Letzter, Abhishek Methuku, Benny Sudakov
An \emph{-packing} in a graph is a collection of pairwise vertex-disjoint copies of in . We prove that for every and every bipartite graph , any $\lfloor c…
Coloring small locally sparse degenerate graphs and related problems
Domagoj BradaÄ, Jacob Fox, Raphael Steiner +2
The classic upper bound on the chromatic number of -degenerate graphs is , shown to be tight by complete graphs. A natural question is whether this bound remains tight if o…