22 papers
Distinguishability threshold for random geometric graphs
Zach Hunter, Aleksa MilojeviÄ, Benny Sudakov
The spherical random geometric graph is obtained by sampling independent points uniformly on the unit sphere and joining pair…
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…
On the Probability a Weighted Bernoulli Sum Exceeds Its Mean
Aleksa Milojevic, Benny Sudakov
Let be positive real weights whose sum is , and let be i.i.d. Bernoulli random variables. If we let , then we co…
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…