6 papers · 1 filter
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…
From small eigenvalues to large cuts, and Chowla's cosine problem
Zhihan Jin, Aleksa Milojević, István Tomon +1
We prove that every graph with average degree and smallest adjacency eigenvalue contains a clique of size . A simple corollary of this yields the fi…
Cyclic subsets of tournaments
Zach Hunter, Teng Liu, Aleksa Milojević +1
Let be a Dirac graph, and let be a vertex subset of , chosen uniformly at random. How likely is the induced subgraph to be Hamiltonian? This question, proposed by…
Beyond the MaxCut problem in -free graphs
Zhihan Jin, Aleksa Milojević, István Tomon
In a recent breakthrough, Zhang proves that if is an -free graph with edges, then has a cut of size at least , making a significant step towards a…
-free subgraphs of high degree with geometric applications
Zach Hunter, Aleksa Milojević, Istvan Tomon +1
The Zarankiewicz problem, a cornerstone problem in extremal graph theory, asks for the maximum number of edges in an -vertex graph that does not contain the complete bipartite g…
Universality for transversal Hamilton cycles in random graphs
Micha Christoph, Anders Martinsson, Aleksa Milojević
A tuple of graphs on the same vertex set of size is said to be Hamilton-universal if for every map there exists a Hamilton cycle whose -th e…