7 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…
Minimising the harmonic sum of cycle lengths
Richard Montgomery, Aleksa Milojević, Alexey Pokrovskiy +1
A central theme in extremal graph theory is to understand the relationship between the density of a graph and the richness of its cycle length spectrum, which is the set of distinc…
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…
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…