1 citations · 2 across the 30 of their papers we have counts for
12 papers · 1 filter
Perfect matchings in hypergraphs and Feige's inequality
Aleksa Milojević, Benny Sudakov
How large of a minimum degree does an -vertex graph need before we are sure that it contains a perfect matching? Dirac's theorem states that a graph on an even number of vertice…
Sharp bounds for off-diagonal and tripartite canonical Ramsey numbers
Strahinja Gvozdić, Zach Hunter, Aleksa Milojević +1
The canonical Ramsey theorem establishes that for every positive integer , there is a sufficiently large such that every edge-colouring of a complete graph contains a…
Thinning and sprinkling: from robust sampling to almost Hamiltonicity
Micha Christoph, Zach Hunter, Benny Sudakov
We develop the thinning--sprinkling technique, a general method for proving robustness of graph properties under random vertex sampling. Using it, we show that random induced subgr…
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…
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…
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…
Communication Complexity of Disjointness under Product Distributions
Zach Hunter, Aleksa Milojević, Benny Sudakov +1
Determining the randomized (or distributional) communication complexity of disjointness is a central problem in communication complexity, having roots in the foundational work of B…
Supercritical sharpness of percolation
Sahar Diskin, Philip Easo, Ritvik Ramanan Radhakrishnan +2
We prove that for supercritical percolation on every infinite transitive graph, the probability that the origin belongs to a finite cluster of size at least decays exponentiall…
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…
Color-avoiding directed paths in tournaments
Jacob Fox, Benny Sudakov, Yuval Wigderson
We study the following Ramsey-theoretic question: given a -coloring of the edges of a tournament, how long of a directed path can we guarantee whose edges avoid one of the color…
Set mappings for general graphs
Lior Gishboliner, Zhihan Jin, Benny Sudakov
The study of extremal problems for set mappings has a long history. It was introduced in 1958 by Erdős and Hajnal, who considered the case of cliques in graphs and hypergraphs. Rec…